ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 6842d528
What is the minimum number of states required to construct a minimal DFA for the language ?
What is the minimum number of states required to construct a minimal DFA for the language ?
Multiple Choice Options
- A
9
- B
10
- C
11
- D✓ Correct Option
12
Detailed Technical Solution & Explanation
To track the count of 's: we need 4 conditions (0, 1, 2, and which is a dead/trap state for ).
To track the count of 's: we need 3 conditions (0, 1, and ).
Since the occurrences of and are independent, the DFA state space is the Cartesian product of the state sets: states.
Option Analysis:
•
Option A (9): Insufficient to distinguish the dead state for across all counters.
•
Option B (10): Under-counts the Cartesian product of states.
•
Option C (11): State space reduction cannot eliminate states before trap consolidation.
•
Option D (12): Correct. distinct states.
Reference: Mock Test 03NEC Licensure Syllabus