ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: dbf63f5e
What is the minimum number of states in a Deterministic Finite Automaton (DFA) required to recognize the language ?
What is the minimum number of states in a Deterministic Finite Automaton (DFA) required to recognize the language ?
Multiple Choice Options
- A
3 states
- B
6 states
- C✓ Correct Option
No DFA can recognize this language because is non-regular (context-sensitive)
- D
1 state with 3 self-loops
Detailed Technical Solution & Explanation
The language requires tracking three independent, arbitrarily large counts (), which violates the Pumping Lemma for regular languages. Because DFAs possess strictly finite internal memory, no DFA can recognize this language.
Option Analysis:
•
Option A (3 states): Cannot count beyond 3.
•
Option B (6 states): Insufficient for unbounded memory.
•
Option C (No DFA can recognize this language be...): Correct. Proven non-regular; requires at least a Linear Bounded Automaton.
•
Option D (1 state with 3 self-loops): Regular languages only.
Reference: Mock Test 01NEC Licensure Syllabus