Teori Bahasa dan Automata - Epsilon-NFA

Finite Automata dengan Epsilon Transition: memungkinkan adanya transisi antara input kosong (empty) dari state Q.

Menggunakan Algoritma Thompson:

Contoh Soal:
Diketahui RE = (a+b)*abb
1. Buat Transition Diagramnya! (dengan algoritma Thompson)
2. Buat DFA-Ekivalennya!

1. Transition diagram:

2. DFA Ekivalen
*anggeplah E = lambang epsilon
E-closure -> sampai state berapa bisa tersambung dengan epsilon

Transition Diagram DFA Ekivalen:

State Table:

YANG PERLU DIINGAT !
RE = (a+b)*abb
Transition diagram:

RE = a(a+b)abb
Transition Diagram:

*Input epsilon setelah q0 dan setelah q6 HANYA dikarenakan ada tanda * setelah (a+b). Jika tidak, maka tidak perlu diberi input epsilon terlebih dahulu.