Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks!

share|improve this question
3  
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. –  Brian M. Scott Jul 19 '12 at 8:16
add comment

2 Answers 2

up vote 0 down vote accepted

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).

share|improve this answer
add comment

pauliwago,

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.

DONE.

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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