NFA dengan ε-Move

• ε-move adalah suatu transisi antara 2 status tanpa adanya input. 

Contoh gambar : transisi antara status q1 ke q3

• ε-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 :

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