Teori bahasa dan Otomata (TBO) – NFA dengan ε-Move


Teori bahasa dan Otomata (TBO) – NFA dengan ε-Move

Def 1.  ε-move adalah suatu transisi antara 2 status tanpa adanya input. Contoh gambar : transisi antara status q1 ke q3

NFA dengan e-Move

NFA dengan e-Move

Def 2.  ε-closure adalah himpunan state yang dapat dicapai dari suatu state tanpa adanya input. Contoh gambar :

  • ε-closure(q0) = [q0,q1,q3]
  • ε-closure(q1) = [q1,q3]
  • ε-closure(q3) = [q3]

Ekuivalensi NFA dengan e-move ke NFA tanpa e-move

  • Buat tabel transisi NFA dengan ε-move
  • Tentukan ε-closure setiap state
  • Carilah fungsi transisi /tabel transisi yang baru,  rumus :

d’(state,input)=ε-closure(d(e-closure(state,input))

  • Tentukan state akhir ditambah dengan state yang e-closure nya menuju state akhir, rumusnya

F’ = F È {q | (e-closure(q) Ç F ¹ Æ}

Contoh

Contoh NFA e-Move

Contoh NFA e-Move

Tabel transisi-nya

d 0 1
q0 {} {}
q1 q2 q3
q2 {} {}
q3 {} {}

ε-closure dari FSA tersebut

ε-closure(q0) = [q0,q1]

ε-closure(q1) = [q1]

ε-closure(q2) = [q2]

ε-closure(q3) = [q3]

Cari tabel transisi yang baru  (d’) :

d’ a b
q0 ε-cl(d(e-cl(q0),a))

ε-cl(d({q0,q1},a))

ε-cl(q2)

{q2}

ε-cl(d(e-cl(q0),b))

ε-cl(d({q0,q1},b))

ε-cl(q3)

{q3}

q1 ε-cl(d(ε-cl(q1),a))

ε-cl(d({q1},a))

ε-cl(q2)

{q2}

ε-cl(d(ε-cl(q1),b))

ε-cl(d({q1},b))

e-cl(q3)

{q3}

q2 e-cl(d(e-cl(q2),a))

e-cl(d({q3},a))

e-cl(Æ)

{}

ε-cl(d(ε-cl(q2),b))

e-cl(d({q2},b))

e-cl(Æ)

{}

q3 ε-cl(d(ε-cl(q3),a))

ε-cl(d({q3},a))

e-cl({})

{}

ε-cl(d(ε-cl(q3),b))

ε-cl(d({q3},b))

ε-cl({})

{}

Hasilnya menjadi


Penggabungan FSA

Bila diketahui L1 adalah bahasa yang diterima oleh M1 dan L2 adalah bahasa yang diterima oleh M2 maka

1. FSA M3 yang dapat menerima L1+L2 dibuat dengan cara

¨           Tambahkan state awal untuk M3, hubungkan dengan state awal M1 dan state awal M2 menggunakan transisi e

¨           Tambahkan state akhir untuk M3, hubungkan dengan state-state akhir M1 dan state-state akhir M2 menggunakan transisi e

2. FSA M4 yang dapat menerima L1L2 dibuat dengan cara

¨           State awal M1 menjadi state awal M4

¨           State-state akhir M2 menjadi state-state akhir M4

¨           Hubungkan state-state akhir M1 dengan state awal M2 menggunakan transisi e

Contoh FSA M1 dan M2

FSA M3

FSA M4


Download : NFA-dengan-ε-Move.pdf

About these ads

3 gagasan untuk “Teori bahasa dan Otomata (TBO) – NFA dengan ε-Move

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s