THEOREMA KLEENE

THEOREMA KLEENE 1
Suatu bahasa yang didefinisikanmelalui Regular Expression (RE)mempunyai bahasa ekuivalen yang digambarkan dalam bentuk Finite Automata (FA), begitu juga sebaliknya


THEOREMA KLEENE 2
PENGGABUNGAN (+) DUA FA
Jika terdapat FA1 yang mewakili bahasa dengan RE=r1 dan terdapat FA2 yang mewakili bahasa dengan RE=r2, maka dapat dibuat FA3 yang mewakili bahasa dengan RE = r1 + r2

Contoh Penggabungan

• #FA1 = menerima semua string yang diakhiri dengan a RE = r1 = (a+b)*a
• #FA2 = menerima semua string yang diakhiri dengan b RE = r2 = (a+b)*b 
• #Jika 2 FA ini digabungkan sesuai Theorema Kleene 2 maka akan didapat FA3 dimana merupakan hasil penggabungan
• # FA3 = FA1 + FA2

THEOREMA KLEENE 3

• FA1: semua string yang diawali oleh a 
• RE1: a(a+b)*
• FA2: semua string yang diakhiri oleh b
• RE2: (a+b)*b
• FA3 = FA1 . FA2
• r3 = r1· r2

NFA To DFA