Equivalenza tra DFA e NFA

<aside> 💡 Due macchine sono equivalenti se riconoscono lo stesso linguaggio

</aside>

<aside> 💡 Ogni NFA $N$ ha un equivalente DFA $M$; cioè, se $N$ è un NFA, allora esiste un DFA $M$ tale che $L(M)=L(N)$

</aside>

• Dimostrazione

Funzione di transizione estesa

La funzione di transizione $\delta$ di un DFA o un NFA può essere estesa per operare direttamente su stringhe (invece che su simboli)

Dato un DFA $M$, definiamo la funzione di transizione estesa $\delta^_M$ in modo che per uno stato $q$ e una stringa $w$, $\delta^_M(q,w)$ sia lo stato raggiungibile quando, partendo da $q$, si abbia $w$ come input

Usando la funzione di transizione estesa, il linguaggio riconosciuto da un DFA $M=(Q_M, \sum, \delta_M, q_M ,F_M)$ diventa: $L(M)= \{ w | \delta^*_M(q_M,w) \in F_M\}$

Dato un NFA $N$, definiamo la funzione di transizione estesa $\delta^_N$ in modo che per uno stato $q$ e una stringa $w$, $\delta^_N(q,w)$ sia l’insieme degli stati raggiungibili quando, partendo da $q$, si abbia $w$ come input

Usando la funzione di transizione estesa, il linguaggio riconosciuto da un NFA $N= (Q_N, \sum, \delta_N, q_N, F_N)$ diventa: $L(N)= \{w| \delta^* (q_N,q) \cap F_N \neq \empty\}$

Definizione ricorsiva

<aside> 💡 Dato un DFA $(Q_M, \sum, \delta_M, q_M, F_M)$, la funzione di transizione estesa $\delta_M^*$ è così definita:

• $\delta_M^* (q, \epsilon) = q$ per ogni $q \in Q_M$
• per ogni stringa $w = xa$, dove $a \in \sum$, $\delta^_M (q, xa) = \delta_M(\delta^_M(q,x),a)$ </aside>

<aside> 💡 Dato un NFA $Q_N, \sum, \delta_N, q_N, F_N)$, la funzione di transizione estesa $\delta_N^*$ è così definita:

• $\delta_N^* (q, \epsilon) = E(\delta_N(q, \epsilon)) = E(\{q\})$ per ogni $q \in Q_N$
• per ogni stringa $w = xa$, dove $a \in \sum$, $\delta^N (q, xa) = \bigcup{r \in \delta^_N (q, x)} E(\delta_N(r,a))$ </aside>

Equivalenza tra DFA e NFA

1. $N = (Q_N, \sum, \delta_N, q_N, F_N)$
2. abbiamo costruito un corrispondente DFA $M= (Q_M, \sum, \delta_M, q_M, F_M)$

• $Q_M = P(Q_N)$
• $\delta_M (R, a) = \bigcup_{r \in R} E(\delta _N (r,a))$
• $q_M = E(\{q_N\})$
• $F_M = \{ R \in Q_M | R \cap F_N \neq \empty \}$