150 views
0 votes
0 votes

Theorem: Let $L$ be the language accepted by a nondeterministic finite accepter $M_N=(Q_N,Σ,δ_N,q_0,F_N)$. Then 
there exists a deterministic finite accepter $M_D=(Q_D,Σ,δ_D,${$q_0$}$,F_D)$ such that 
$L=L(M_D)$.

Prove this Theorem.

Show in detail that if the label of $\delta ^*_D(q_0,w)$ contains $q_f$, then $\delta ^*_N(q_0,w)$ also contains $q_f$.

Please log in or register to answer this question.

Related questions

2 votes
2 votes
0 answers
2
Naveen Kumar 3 asked Mar 30, 2019
483 views
Give a simple verbal description of the language accepted by the dfa in following figure.Use this to find another dfa, equivalent to the given one, but with fewer states....