Consider the Nondeterministic Finite State Automaton (NFA) below. State with a…
2023
Consider the Nondeterministic Finite State Automaton (NFA) below. State with a small incoming arrow are initial states while a double circle state denotes a final state.
The number of states in the MINIMAL Deterministic Finite-State Automaton (DFA) for this language is:
- A.
2
- B.
4 - C.
6
- D.
8
Attempted by 70 students.
Show answer & explanation
Correct answer: B
First, analyze the language accepted by the NFA. The automaton starts at an initial state with a self-loop on 'a' and 'b'. To reach the final state (double circle), it must traverse a transition labeled 'b' to an intermediate state, followed by a transition labeled 'a' or 'b'. This means the NFA accepts any string that ends with "ba" or "bb".
To build a minimal DFA, we need to track the suffix of the input string. We require four distinct states:
1. Start State (S0): Strings ending in 'a' or empty. Non-final.
2. State S1: Strings ending in 'b' (but not yet forming a final pattern). Non-final.
3. State S2: Strings ending in "ba". Final.
4. State S3: Strings ending in "bb". Final.
Transitions confirm all four states are necessary (e.g., from S0, 'a' stays in S0 while 'b' goes to S1; from S2 and S3, transitions lead to different states). Thus, the minimal DFA has 4 states.