Consider the following NFA:

Where → denotes the initial state and * denotes the final state.
Which of the following is the set of states in the DFA obtained from the given NFA?

Correct option is C

To convert the given NFA to a DFA, we use the subset construction method. We will list all possible sets of NFA states that can be reached from the DFA states.
1. Start with the initial state: {q0}
2. Compute the closure and transitions for each state:
· From {q0}, on input 'a' and 'b':
· {q0} on 'a' → {q0}
· {q0} on 'b' → {q1}
· {q0, q1}, on input 'a' and 'b':
· {q0, q1} on 'a' → {q0, q2}
· {q0, q1} on 'b' → {q0}
· {q0, q2}, on input 'a' and 'b':
· {q0, q2} on 'a' → {q0, q2}
· {q0, q2} on 'b' → {q0, q1}
· {q0, q1, q2}, on input 'a' and 'b':
· {q0, q1, q2} on 'a' → {q0, q2}
· {q0, q1, q2} on 'b' → {q0, q1}
By enumerating all reachable sets of states, the DFA states are: {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q0, q1, q2}.
Thus, the correct answer is: (c) {q0, q1, q2, {q0, q1}, {q1, q2}, {q0, q2}, {q0, q1, q2}}
Important Key Points:
1. The subset construction method systematically converts an NFA into a DFA by considering all possible combinations of NFA states.
2. In this case, the ε-transitions must also be considered while computing the reachable states.
3. The final state(s) of the DFA are subsets that include the NFA’s final state(s), in this case, {q2}.
Knowledge Booster:
· NFA (Non-deterministic Finite Automaton): Allows multiple transitions for the same input or ε-transitions (transitions without input).
· DFA (Deterministic Finite Automaton): Requires exactly one transition for each input symbol in each state.
· ε-closure: The set of all states reachable from a given state through ε-transitions.