Is this NFA right?

620 Views Asked by At

Create a NFA for the following language $$\{w \mid w \text{ contains an even number of $0$s, or contains exactly two $1$s }\} \enspace.$$ Do it with six states: My NFA

However, I think I made it too hard and the following one is far simpler.

Desired NFA

I don't understand the empty strings of the latter. If a string like 00 is passed in the latter, it wouldn't read it to me because it would get stuck in the first state. There is no edge labeled 0 going out in the first state.

1

There are 1 best solutions below

2
On BEST ANSWER

The $\epsilon$ that labels the transitions out of the initial state "consumes no input." That is, the NFA can move to either successor of the initial state before reading the first letter of the input word.

A way to interpret what happens is this NFA is that the automaton chooses nondeterministically whether to look for an even number of zeros (upper branch) or exactly two ones (lower branch) before it reads the input.

(Formally, this NFA has one or two runs for each word. If at least one run is accepting, the automaton accepts the word.)

It is not essential that the initial state be accepting, but it makes the elimination of the $\epsilon$-transitions marginally easier, because the initial state after removing $\epsilon$-transitions is accepting.