AALL10 · Chapter 10Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 0c0cddfd
A Pushdown Automaton (PDA) that has at most one valid transition for any given state, input symbol, and stack top combination is called a:
A Pushdown Automaton (PDA) that has at most one valid transition for any given state, input symbol, and stack top combination is called a:
Multiple Choice Options
- A
Non-Deterministic Pushdown Automaton (NPDA)
- B✓ Correct Option
Deterministic Pushdown Automaton (DPDA)
- C
Finite State Machine (FSM)
- D
Turing Machine
Detailed Technical Solution & Explanation
A Deterministic Pushdown Automaton (DPDA) possesses at most one transition for every state, input, and stack top combination: . DPDAs recognize Deterministic Context-Free Languages (DCFLs), which form the basis for programming language parsing (LR parsers).
Option Analysis:
•
Option A (NPDA): Can have multiple non-deterministic choice branches.
•
Option B (DPDA): Correct; defines single-transition deterministic pushdown automata.
•
Option C (FSM): Has no stack memory.
•
Option D (Turing Machine): Uses unbounded tape memory.
Reference: Demo2 · Set 2NEC Licensure Syllabus