Equivalenza

NFA e DFA

Si può dimostrare che per ogni NFA $N$ , esiste un DFA $D$ tale che $L (D) = L (N)$ .

Dato $N = (Q, Σ, δ, q_{0}, F)$ con possibili $ϵ$ -transizioni, si vuole costruire $D = (Q^{'}, Σ, δ^{'}, q_{0}^{'}, F^{'})$ :

$Q^{'} = P (Q)$ , per cui ogni stato di $D$ rappresenta un livello dell'albero di computazione di $N$
$q_{0}^{'} = E ({q_{0}})$
$F^{'} = {R \in Q^{'} ∣ \exists r \in R : r \in F}$
$δ^{'} (R, a) = r \in R ⋃ E (δ (r, a))$

dove $E (R)$ è l'insieme degli stati $q$ raggiungibili da qualche $r \in R$ con $0$ o più $ϵ$ -transizioni.

Per esempio, l'NFA

è convertibile nel seguente DFA:

che è il risultato delle seguenti transizioni, che partono da $q_{0}^{'} = E ({1}) = {1, 3}$ :

$δ^{'} ({1, 3}, a) = E (δ (1, a)) \cup E (δ (3, a)) = E (\emptyset) \cup E ({1}) = \emptyset \cup {1, 3} = {1, 3}$
$δ^{'} ({1, 3}, b) = E ({2}) \cup E (\emptyset) = {2} \cup \emptyset = {2}$
$δ^{'} ({2}, a) = E ({2, 3}) = {2, 3}$
$δ^{'} ({2}, b) = E ({3}) = {3}$
$δ^{'} ({2, 3}, a) = E ({2, 3}) \cup E ({1}) = {1, 2, 3}$
$δ^{'} ({2, 3}, b) = E ({3}) \cup E (\emptyset) = {3}$
$δ^{'} ({3}, a) = E ({1}) = {1, 3}$
$δ^{'} ({3}, b) = E (\emptyset) = \emptyset$
$δ^{'} ({1, 2, 3}, a) = E (\emptyset) \cup E ({2, 3}) \cup E ({1}) = {1, 2, 3}$
$δ^{'} ({1, 2, 3}, b) = E ({2}) \cup E ({3}) \cup E (\emptyset) = {2, 3}$

L'equivalenza si dimostra perchè $A$ è regolare sse esiste una regex $R$ tale che $L (R) = A$ :

Condizione necessaria ( $\Leftarrow$ )

Si può dimostrare che $A$ è regolare per induzione sulla struttura di $R$ , infatti:
1. Sia $R = a$ per qualche $a$ allora $L (R) = {a}$ è regolare perchè:
2. Sia $R = ϵ$ allora $L (R) = {ϵ}$ è regolare perchè:
3. Sia $R = \emptyset$ allora $L (R) = \emptyset$ è regolare perchè:
4. Sia $R = R_{1} \cup R_{2}$ allora $L (R) = L (R_{1}) \cup L (R_{2})$ è regolare per ipotesi induttiva, ovvero perchè l'operazione di unione è chiusa e a causa dei casi precedenti $L (R_{1})$ e $L (R_{2})$ sono già regolari
5. Sia $R = R_{1} \circ R_{2}$ allora $L (R) = L (R_{1}) \circ L (R_{2})$ è regolare per ipotesi induttiva
6. Sia $R = R_{1}^{*}$ allora $L (R) = L (R)^{*}$ è regolare per ipotesi induttiva
Condizione sufficiente ( $\Rightarrow$ )

Essendo $A$ regolare, esiste un DFA associato e lo si potrà trasformare in GNFA (o NFA generalizzato):

La riduzione è possibile perchè ogni arco del GNFA è etichettato da regex, e il processo consisterà nel:
1. Aggiungere un nuovo stato iniziale $q_{s}$ che va verso $q_{0}$ con una $ϵ$ -transizione
2. Aggiungere un nuovo stato finale $q_{f}$ verso cui vanno gli stati di $F$ con $ϵ$ -transizioni
3. Modificare il GNFA rimuovendo uno stato di $Q$ e usando le regex perchè riconosca $A$
4. Ripetere l'ultimo punto finchè non rimangono più stati di $Q$
Per esempio, partendo con un DFA: