0
$\begingroup$

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!

  • 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.2012-07-19

2 Answers 2

0

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

0

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.