Creating an equivalent DFA for this NFA

Question

I have an NFA and I want to make an equivalent version of it as a DFA. What will the final DFA diagram look like?

This is the NFA I want to find an equivalent DFA for.

My attempt:

I've constructed a transition table:

+-------+----+----+----+
| State | 0  | 1  | Ɛ  |
+-------+----+----+----+
| q0    | q1 | -  | q1 |
| q1    |  - | q2 |  - |
| q2*   | q2 | q2 |  - |
+-------+----+----+----+

Since I have epsilon as a possible input, I'm a bit confused. What would the resulting DFA look like?

score 0 · Answer 1 · answered Apr 19 '21 at 20:02

HINT: Probably the easiest approach is to work out the language accepted by the NFA. The $\epsilon$ transition simply means that it can progress from the initial state to $q_1$ without reading a character, so in effect it can start either at $q_0$ or at $q_1$. Can you now write down a regular expression for the language? There’s a further hint in the spoiler box.

Either the NFA reads a $0$ and moves to $q_1$, or it moves to $q_1$ without reading a character. What must it read then in order for the input to be accepted?

Creating an equivalent DFA for this NFA

1 Answers1