Equivalence Between NFA and DFA: Q, Q` & $\Sigma$

[mathmari]

Heloo!

I am looking at the equivalence between a NFA and a DFA.

NFA: Q={q1,q2}
DFA: Q`=P(Q}

When $a\in \Sigma, Q_I, Q_j \in Q`$ which is sufficient and necessary condition so that $ Q_I \overset{a}{\rightarrow}Q_j$?

 

[Evgeny.Makarov]

When $a\in \Sigma, Q_I, Q_j \in Q`$ which is sufficient and necessary condition so that $ Q_I \overset{a}{\rightarrow}Q_j$?

This is described in the books we talked about. Namely, if $R\in Q'$, i.e., $R\subseteq Q$, let
\[
E(R)=\{q\in Q\mid q\text{ can be reached from }R\text{ by 0 or more }\varepsilon\text{ arrows}\}.
\]
Then $Q_i \overset{a}{\rightarrow}Q_j$ iff $$Q_j=\bigcup_{q\in Q_i}E(\delta(q,a))$$. In other words,
\[
Q_j=\{s\in Q\mid q\overset{a}{\to}r\overset{\varepsilon}{\to}\!\!^*s\text{ for some }q\in Q_i\}.
\]
Here $r\overset{\varepsilon}{\to}\!\!^*s$ means that $s$ can be reached from r by 0 or more $\varepsilon$ arrows.

 

[mathmari]

This is described in the books we talked about. Namely, if $R\in Q'$, i.e., $R\subseteq Q$, let
\[
E(R)=\{q\in Q\mid q\text{ can be reached from }R\text{ by 0 or more }\varepsilon\text{ arrows}\}.
\]
Then $Q_i \overset{a}{\rightarrow}Q_j$ iff $$Q_j=\bigcup_{q\in Q_i}E(\delta(q,a))$$. In other words,
\[
Q_j=\{s\in Q\mid q\overset{a}{\to}r\overset{\varepsilon}{\to}\!\!^*s\text{ for some }q\in Q_i\}.
\]
Here $r\overset{\varepsilon}{\to}\!\!^*s$ means that $s$ can be reached from r by 0 or more $\varepsilon$ arrows.

Ok... Thanks a lot! (Smile)