NFA umum (GNFA)

NFA umum, disingkat GNFA (generalized nondeterministic finite automaton), adalah otomaton nondeterministik yang transisinya tidak hanya boleh berupa simbol alfabet, tetapi juga ekspresi reguler.

Definisi

GNFA akan kita perlukan dalam algoritma konversi otomaton hingga menjadi ekspresi reguler. Jadi, GNFA adalah NFA yang transisinya didefinisikan dengan ekspresi reguler. Contoh GNFA seperti itu:

Terlihat, misalnya, bahwa dari state q₂ ada transisi ke state q_f yang diberi label ekspresi reguler a^∗ b. Syarat-syarat lain untuk GNFA:

• State awal q₀ harus memiliki transisi ke semua state lainnya. Pada gambar terlihat bahwa dari state q₀ ada transisi ke semua state lainnya.
• GNFA hanya memiliki satu state akhir, dan semua state lainnya memiliki transisi ke state ini. Seperti terlihat pada gambar, semua state memiliki panah yang mengarah ke q_f.
• State awal tidak boleh sama dengan state akhir. Jadi, GNFA memiliki setidaknya dua state.
• Semua state lainnya, selain state awal dan state akhir, harus memiliki transisi ke semua state lainnya, selain state awal dan state akhir, termasuk loop (transisi dari state q_i ke state q_i).

Konversi NFA biasa menjadi GNFA

Jika ada suatu NFA, konversinya menjadi GNFA cukup sederhana.

1. Buat state awal baru q_s dan buat transisi epsilon ke state awal semula.
2. Buat state akhir baru q_f, lalu dari semua state akhir semula buat transisi epsilon ke state q_f. State akhir semula dijadikan state biasa.
3. Jika di suatu tempat ada transisi ganda (misalnya dari state q₁ kita dapat sampai di state q₂ melalui simbol 0 maupun simbol 1), aturan-aturan tersebut kita gabungkan menjadi satu ekspresi reguler, dan semua simbol semula kita sambung dengan operator gabungan (artinya, panah kita beri label ekspresi reguler 0|1).
4. Jika pada otomaton tidak ada transisi yang menurut definisi seharusnya ada, transisi tersebut kita buat dan kita beri label ekspresi reguler ∅. Dengan begitu, bahasa yang diterima otomaton tidak berubah, karena transisi seperti itu tidak pernah dijalankan.

Otomaton ini dapat digunakan untuk mengonversi otomaton menjadi ekspresi reguler.