Consider the following DFA over Σ = {a, b, c}. Start state q0; final states q2, q3, q4, q5. Transitions (any missing transition goes to a dead state):

State	a	b	c
→ q0	q1	–	–
q1	q2	q3	q4
* q2	q2	q3	q4
* q3	q5	–	q3
* q4	q0	–	–
* q5	q1	–	–

Which of the following NFAs is valid (equivalent) for the given DFA?

1. ANFA-A: states q0–q4, start q0, final {q2, q3}. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3, q2 –a→ q4; q4 –c→ q3; q3 –a→ q0
2. BNFA-B: same as NFA-A but final states {q2, q3, q4}
3. CNFA-C: states q0–q3, start q0, final {q3} only. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3; q3 –a→ q0
4. DNFA-D: states q0–q3, start q0, final {q2, q3}. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3; q3 –a→ q0

Pick an option to check yourself, or open the answer below.