Un automa finito nondeterministico generalizzato è un NFA con delle espressioni regolari al posto dei semplici membri dell'alfabeto Σ.
Si usa, per prassi:
- Lo stato iniziale ha frecce uscenti verso tutti gli altri stati, ma non ha frecce entranti;
- C'è un solo stato di accettazione, ha solo frecce entranti da ogni altro stato e non ha frecce uscenti. Inoltre non coincide con lo stato iniziale;
- A parte gli stati iniziale e finale, ogni stato ha una freccia che va verso ciascuno degli altri stati e una verso se stesso.
La definizione formale di GNFA è
| Symbol | Meaning |
|---|---|
| Q | finite set called the States |
| Σ | finite state called Alphabet |
| δ:(Q-{qaccept})x(Q-{qstart})→R | transition function (tutte le combinazioni possibili, tranne quelle che partono dallo stato accettato e finiscono nello stato di partenza) |
| qstart∈Q | start state |
| qaccept | accepted states |
La conversione di una GNFA in una DFA consiste in un semplice algoritmo:
CONVERT(G)
- sia k il numero di stati di G
- se k = 2 allora G deve essere uno stato di start, uno stato di accept e una sola freccia contenente un'espressione regolare
- se invece k > 2, allora si calcola Q' = Q - qrip, cioè per ogni stato diverso da start e accept, si convertono le frecce in un equivalente senza lo stato rip:
δ'(qi, qj) = (R1)(R2)*(R3)∪(R4), dove: -
- R1 = δ(qi, qrip)
- R2 = δ(qrip, qrip)
- R3 = δ(qrip, qj)
- R4 = δ(qi, qj)
- si applica CONVERT a G'