NFA to DFA final states proof

Question

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?

Answer 1

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.