Automaton terhingga tak berketentuan umum

Automaton terhingga tak berketentuan umum, singkatannya GNFA (generalized nondeterministic finite automaton), ialah automaton tak berketentuan yang peralihannya tidak semestinya berlabel simbol abjad sahaja, tetapi boleh juga berlabel ungkapan nalar.

Takrif

Kita memerlukan GNFA dalam algoritma penukaran automaton terhingga kepada ungkapan nalar. Jadi, GNFA ialah NFA yang peralihannya ditakrifkan dengan ungkapan nalar. Contoh GNFA sebegini:

Kita lihat bahawa, misalnya, dari keadaan q₂ terdapat peralihan ke keadaan q_f yang berlabel ungkapan nalar a^∗ b. Syarat lain bagi GNFA:

• Keadaan awal q₀ mesti mempunyai peralihan ke semua keadaan lain. Dalam rajah kita lihat bahawa dari keadaan q₀ terdapat peralihan ke semua keadaan lain.
• GNFA hanya mempunyai satu keadaan akhir, dan semua keadaan lain mempunyai peralihan ke keadaan ini. Seperti yang ditunjukkan dalam rajah, semua keadaan mempunyai anak panah yang menuju ke q_f.
• Keadaan awal tidak boleh sama dengan keadaan akhir. Oleh itu, GNFA mempunyai sekurang-kurangnya dua keadaan.
• Semua keadaan lain, selain keadaan awal dan keadaan akhir, mesti mempunyai peralihan ke semua keadaan lain, selain keadaan awal dan keadaan akhir. Hal ini termasuk gelung (peralihan dari keadaan q_i ke keadaan q_i).

Penukaran NFA biasa kepada GNFA

Jika kita mempunyai suatu NFA, penukarannya kepada GNFA mudah sahaja.

1. Bina keadaan awal baharu q_s dan peralihan epsilon dari keadaan ini ke keadaan awal asal.
2. Bina keadaan akhir baharu q_f dan lukis peralihan epsilon dari semua keadaan akhir asal ke keadaan q_f. Jadikan keadaan akhir asal keadaan biasa.
3. Jika terdapat peralihan berganda (iaitu jika dari keadaan q₁ kita sampai ke keadaan q₂ melalui simbol 0 dan juga melalui simbol 1), gabungkan peraturan ini menjadi satu ungkapan nalar dan sambungkan semua simbol asal dengan pengendali kesatuan (iaitu labelkan anak panah itu dengan ungkapan nalar 0|1).
4. Jika automaton tiada peralihan yang sepatutnya ada menurut takrif, bina peralihan itu dan labelkannya dengan ungkapan nalar ∅. Hal ini tidak mengubah bahasa yang diterima oleh automaton kerana peralihan sebegini tidak akan pernah diikuti.

Automaton ini boleh digunakan untuk menukarkan automaton kepada ungkapan nalar.