ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: ceb795c6
In formal language theory, a Pushdown Automaton (PDA) is the computing model that recognizes which class of languages?
In formal language theory, a Pushdown Automaton (PDA) is the computing model that recognizes which class of languages?
Multiple Choice Options
- A
Regular languages
- B✓ Correct Option
Context-free languages
- C
Context-sensitive languages
- D
Recursively enumerable languages
Detailed Technical Solution & Explanation
By definition in automata theory, a Pushdown Automaton (a finite automaton equipped with a single LIFO stack) exactly recognizes the class of Context-Free Languages (Type-2 in the Chomsky hierarchy).
Option Analysis:
•
Option A (Regular languages): Recognized by Finite Automata (DFA/NFA).
•
Option B (Context-free languages): Correct. Exactly characterized by Pushdown Automata.
•
Option C (Context-sensitive languages): Recognized by Linear Bounded Automata.
•
Option D (Recursively enumerable languages): Recognized by Turing Machines.
Reference: Demo · Set 4NEC Licensure Syllabus