3
$\begingroup$

When translating an NFA into an equivalent DFA, we can say that all states that contain the final states of NFA, is the final state of DFA.

What should my arguments be in order to prove this?

$\endgroup$
  • $\begingroup$ What exactly is the property of the NFA-states that are in a DFA-state? $\endgroup$ – Hendrik Jan Jan 25 '14 at 13:34
  • $\begingroup$ The property of the NFA-states that are in the DFA states are final states. $\endgroup$ – user21276 Jan 25 '14 at 13:41
  • 1
    $\begingroup$ This is the way the subset-construction is defined. What one needs to prove is that the subset-construction is correct. That is, that it does not change the language. $\endgroup$ – Shaull Jan 25 '14 at 13:41
  • $\begingroup$ What are you really asking? Do you have to prove correctness of the subset construction or do you not understand that proof? What is your problem with the statement? $\endgroup$ – Raphael Jan 25 '14 at 16:45
2
$\begingroup$

Your statement is incorrect for two reasons.

First, there are in general several final states in the DFA corresponding to an NFA and not a single one. Next a set in the DFA is final if and only if it contains at least one final state of the DNA (and not all of them as you wrote). Furthermore, the initial state of the DFA is the set of all initial states of the DFA.

You can find the formal proof in any textbook on automata, but here is the intuition.

Let $\mathcal{A} = (Q, A, E, I, F)$ be a NFA. Let us call successful a path in $\mathcal{A}$ starting in $I$ and ending in $F$. By definition, a word $u$ is accepted by $\mathcal{A}$ if and only if there exists a successful path with label $u$.

Now, what happens when you use the subset construction to compute a DFA $\mathcal{B}$ equivalent to $\mathcal{A}$? You know that the states of $\mathcal{B}$ are subsets of $Q$. Furthermore, there is a path from $P$ to $R$ with label $u$ (where $P$ and $R$ are subsets of $Q$) if and only if $$ \text{for each $r \in R$, there is a state $p \in P$ and a path in $\mathcal{A}$ from $p$ to $r$ with label $u$.} $$ Thus intuitively, this path $P \xrightarrow{u}_{*} R$ in the DFA encodes all the possible paths in the DNA from a state of $P$ to a state of $R$.

Suppose now that $P = I$ and that $R$ contains a final state of $\mathcal{A}$, say $f$. Then there is a state $p \in I$ and a path in $\mathcal{A}$ from $p$ to $f$ with label $u$. Thus this path is successful and $u$ is accepted by $\mathcal{A}$.

In the opposite direction, suppose that $u$ is accepted by $\mathcal{A}$. Then $u$ is the label of a successful path in $\mathcal{A}$, say from $p \in I$ to $f \in F$. Let $R = I \cdot u$ (in the DFA $\mathcal{B}$). Then $f \in R$ by construction and thus $R$ contains a final state.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.