ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 59ed3ea2
Can a Deterministic Finite Automaton (DFA) recognize the language ?
Can a Deterministic Finite Automaton (DFA) recognize the language ?
Multiple Choice Options
- A
Yes, using exactly 3 states
- B
Yes, using a state for each alphabet symbol
- C✓ Correct Option
No, because is a non-regular (context-sensitive) language requiring infinite memory
- D
Yes, using -transitions
Detailed Technical Solution & Explanation
The language requires matching three unbounded counts (), which is proven non-regular by the Pumping Lemma (it is in fact context-sensitive and not even context-free). Because a DFA has strictly finite memory (finite states), no DFA can recognize this language.
Option Analysis:
•
Option A (Yes, using exactly 3 states): Incorrect; 3 states can only count modulo 3, not compare arbitrary counts .
•
Option B (Yes, using a state for each alphabet ...): Incorrect; regular languages cannot match independent multiple counts.
•
Option C (No, because L is a non-regular (con...): Correct. DFAs cannot recognize .
•
Option D (Yes, using \varepsilon-transitions): NFA with -transitions is equivalent to DFA in computational power and still regular.
Reference: Mock Test 06NEC Licensure Syllabus