Automa a stati finiti non deterministico generalizzato

Un automa a stati finiti non deterministico generalizzato, in breve GNFA, è un automa non deterministico che sulle transizioni non ha necessariamente soltanto simboli dell’alfabeto, ma può avere un’espressione regolare.

Definizione

Il GNFA ci servirà nell’algoritmo di conversione di un automa a stati finiti in un’espressione regolare. Un GNFA è quindi un NFA le cui transizioni sono definite da espressioni regolari. Un esempio di GNFA:

Vediamo che, per esempio, dallo stato q₂ parte una transizione verso lo stato q_f etichettata con l’espressione regolare a^∗ b. Altri requisiti per un GNFA:

• Lo stato iniziale q₀ deve avere una transizione verso tutti gli altri stati. In figura vediamo che dallo stato q₀ partono transizioni verso tutti gli altri stati.
• In un GNFA esiste un solo stato finale e tutti gli altri stati hanno una transizione verso questo stato. Come si vede in figura, tutti gli stati hanno una freccia diretta verso q_f.
• Lo stato iniziale non può coincidere con lo stato finale. Un GNFA ha quindi almeno due stati.
• Tutti gli altri stati, tranne quello iniziale e quello finale, devono avere transizioni verso tutti gli altri stati, tranne quello iniziale e quello finale. Compresi i cappi (transizione dallo stato q_i allo stato q_i).

Conversione di un NFA ordinario in GNFA

Se abbiamo un NFA, la conversione in GNFA è semplice.

1. Creiamo un nuovo stato iniziale q_s e una ε-transizione verso il vecchio stato iniziale.
2. Creiamo un nuovo stato finale q_f e da tutti i vecchi stati finali tracciamo ε-transizioni verso q_f. I vecchi stati finali diventano stati normali.
3. Se da qualche parte esiste una transizione multipla (cioè se dallo stato q₁ si arriva allo stato q₂ sia con il simbolo 0 sia con il simbolo 1), uniamo queste regole in un’unica espressione regolare e colleghiamo tutti i simboli originali con l’operatore di unione (cioè etichettiamo la freccia con l’espressione regolare 0|1).
4. Se nell’automa manca una transizione che secondo la definizione dovrebbe esserci, la creiamo e la etichettiamo con l’espressione regolare ∅. Così non cambiamo il linguaggio accettato dall’automa, perché una transizione del genere non verrà mai eseguita.

Possiamo usare questo automa per convertire un automa in un’espressione regolare.