I'm asked to build a DFA A and NFA B such that L(D) = L(N) with some specific conditions. I'm not asking for solutions or answers; I just wanted to make sure I have the right method to attack this problem.

First off, I'm a bit confused by the wording "build". Do they just want an automaton drawn? Would that be considered "built"?

I'm thinking of drawing the NFA B that fits that condition. Then using the drawing, I'll construct an equivalent DFA A. There's a theorem somewhere that says equivalent automatas have the same language. So I don't have to do anything further to show L(A) = L(B) right?


  • 3
    $\begingroup$ That’s how I’d approach it: there’s an actual algorithm for converting an NFA into an equivalent DFA. Exactly what is meant by build depends on the course: drawing the digraph could well be sufficient, but it’s also possible that a more formal description (state set, transitions, etc.) is wanted. $\endgroup$ Jul 19 '12 at 8:16

The way I've seen it used "building", especially in the context of automata theory, is just a somewhat quaint way of saying "proving existence by explicit construction" (rather than, for example, proving existence using a proof by contradiction and double negation).



Let's assume that the DFA $D$ has the state set $Q = \{q_0, q_1, ..., q_n\}$.

Now, we "build" the NFA $N$ as follows:

($1$.) Start with the DFA $D$.

($2$.) Add an additional accepting state for the NFA $N$, such that $N$ will have $n + 1$ total number of states.

Let's call the new accepting state $q_{n + 1}$.

($3$.) Now, add an epsilon $\epsilon$ transition from all accepting states to the new accepting state $q_{n + 1}$, and make all the original accepting states just normal states.


Now, we have an NFA $N$ such that $L(N) = L(D)$.

Note: Any of the states in the set $Q$ could be an accepting state. By making them regular states and adding epsilon $\epsilon$ transitions from them to our created accepting state, we have successfully built an NFA. This construction can work for any DFA.

Additional note: One variation of the above construction would be to add an additional start state as well, and make an epsilon $\epsilon$ transition from the new start state to the original start state.


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.