Általánosított nemdeterminisztikus véges automata

Az általánosított nemdeterminisztikus véges automata, röviden ÁNVA, olyan nemdeterminisztikus automata, amelynek átmenetein nem csak az ábécé szimbólumai állhatnak, hanem reguláris kifejezés is.

Definíció

Az ÁNVA-ra a véges automata reguláris kifejezéssé alakításának algoritmusa során lesz szükségünk. Az ÁNVA tehát olyan NVA, amelynek az átmeneteit reguláris kifejezések határozzák meg. Példa egy ilyen ÁNVA-ra:

Látjuk, hogy például a q₂ állapotból a q_f állapotba vezet átmenet, amelyet az a^∗ b reguláris kifejezés jelöl. További követelmények az ÁNVA-val szemben:

• A q₀ kezdőállapotból minden más állapotba kell vezetnie átmenetnek. Az ábrán látjuk, hogy a q₀ állapotból minden más állapotba vezet átmenet.
• Az ÁNVA-nak csak egy végállapota van, és minden más állapotból vezet átmenet ebbe az állapotba. Ahogy az ábrán látható, minden állapotból nyíl mutat a q_f állapotba.
• A kezdőállapot nem lehet azonos a végállapottal. Az ÁNVA-nak tehát legalább két állapota van.
• Minden más állapotból – a kezdő- és a végállapot kivételével – átmenetnek kell vezetnie minden más állapotba, a kezdő- és a végállapot kivételével. A hurkokat is beleértve (átmenet a q_i állapotból a q_i állapotba).

A közönséges NVA átalakítása ÁNVA-vá

Ha van egy NVA-nk, az ÁNVA-vá alakítás egyszerű.

1. Létrehozunk egy új q_s kezdőállapotot, és epszilon-átmenetet vezetünk belőle az eredeti kezdőállapotba.
2. Létrehozunk egy új q_f végállapotot, és az összes eredeti végállapotból epszilon-átmeneteket vezetünk a q_f állapotba. Az eredeti végállapotokból közönséges állapotokat csinálunk.
3. Ha valahol többszörös átmenet van (vagyis ha a q₁ állapotból a q₂ állapotba a 0 és az 1 szimbólumra is eljutunk), akkor ezeket a szabályokat egyetlen reguláris kifejezésbe vonjuk össze, és az összes eredeti szimbólumot az unió operátorral kapcsoljuk össze (vagyis a nyilat a 0|1 reguláris kifejezéssel jelöljük).
4. Ha az automatából hiányzik valamilyen átmenet, amelynek a definíció szerint ott kellene lennie, létrehozzuk, és az ∅ reguláris kifejezéssel jelöljük. Ezzel nem változtatjuk meg az automata által elfogadott nyelvet, mert az ilyen átmenet soha nem hajtódik végre.

Ezt az automatát felhasználhatjuk az automata reguláris kifejezéssé alakítására.