Da DFA a NFA

Si vuole dimostrare che i DFA e gli NFA riconoscono la stessa classe di linguaggi, cioè che la classe dei linguaggi regolari (per definizione, quelli riconosciuti dai DFA) coincide con la classe dei linguaggi riconosciuti dagli NFA.

• Lemma: dato un DFA $D=\lang Q, \Sigma, \delta , q_0, F\rang$, per ogni $w\in \Sigma^*$ si ha che $\hat \delta _N (q_0, w)=\{\hat \delta(q_0, w)\}$.
  • Dimostrazione del lemma
• Teorema: Dato un DFA $D=\lang Q, \Sigma, \delta, q_0, F\rang$, $L(N_D)=L(D)$.
  • Dimostrazione del teorema