AALL10 · Chapter 10Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 16d7c3b6
In formal language theory, a Pushdown Automaton (PDA) accepts languages generated by:
In formal language theory, a Pushdown Automaton (PDA) accepts languages generated by:
Multiple Choice Options
- A
Type 0 grammar
- B
Type 1 grammar
- C✓ Correct Option
Type 2 grammar (Context-Free Grammar / CFLs)
- D
Type 3 grammar
Detailed Technical Solution & Explanation
In the Chomsky language hierarchy, Pushdown Automata (PDA) (using finite control + single LIFO stack) precisely accept Type 2 Context-Free Languages (CFLs).
Option Analysis:
•
Option A (Type 0): Turing Machines.
•
Option B (Type 1): Linear Bounded Automata.
•
Option C (Type 2 grammar): Correct; recognized by Pushdown Automata.
•
Option D (Type 3): Finite State Automata.
Reference: Mock Test 01NEC Licensure Syllabus