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



No comments:

Post a Comment