NDFA (Non Deterministik Finite Automata)
Dari suatu state ada 0, 1 atau lebih state berikutnya
untuk setiap simbol masukan yang diterima.
Non-Deterministic Finite Automata:
-
Otomata berhingga yang tidak pasti untuk setiap pasangan state input, bisa
memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.
-
Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap
simbol input yang ada.
-
Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel simbol input yang sama.
-
Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.
-
Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila
{x | d (S,x) memuat sebuah state di dalam F}
Kedua finite automata di atas mampu mengenali himpunan reguler secara
presisi. Dengan demikian kedua finite automata itu dapat mengenali
string-string yang ditunjukkan dengan ekspresi reguler secara tepat.
DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun
demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya.
Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah
mengimplementasikan DFA dibanding NDFA.
Contoh pengerjaan NDFA :
Diketahui sebuah mesin A =
({q0,q1,q2,q3,q4}, {a,b}, δ,q0,{q0,q2,q3}) dengan dengan
State diagram sebagai berikut: :
Pada gbr di atas bila Mesin A
diinputkan string ababa, maka
(q0,ababa) ├A
(q1,baba)
├A (q2,aba)
├A (q3,ba)
├A (q2,a)
├A (q3,e)
Karena (q0,ababa)├*A (q3,e), maka string ababa diterima oleh mesin A
2. Tabel Transisinya seperti gambar berikut :
3. Pembuktian string
ababaabba :
(q0,ababaabba) ├A (q1,babaabba)
├A (q2,abaabba)
├A (q3,baabba)
├A (q2,aabba)
├A (q3,abba)
├A (q1,bba)
├A (q2,ba)
├A (q4,a)
├A
(q4,e)
Karena (q0,ababa)├*A (q4,e), maka string ababa ditolak oleh mesin A
4. tree path sebagai berikut :