AALL10 · Chapter 10Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 0cb83303
In the Chomsky formal language hierarchy, a Pushdown Automaton (PDA) recognizes which grammar type?
In the Chomsky formal language hierarchy, a Pushdown Automaton (PDA) recognizes which grammar type?
Multiple Choice Options
- A
Type 0 grammar (Unrestricted grammar)
- B
Type 1 grammar (Context-Sensitive grammar)
- C✓ Correct Option
Type 2 grammar (Context-Free grammar)
- D
Type 3 grammar (Regular grammar)
Detailed Technical Solution & Explanation
In the Chomsky Hierarchy:
•
Type 3 (Regular) Finite Automata (FA/DFA/NFA)
•
Type 2 (Context-Free) Pushdown Automata (PDA)
•
Type 1 (Context-Sensitive) Linear Bounded Automata (LBA)
•
Type 0 (Unrestricted) Turing Machines (TM).
Option Analysis:
•
Option A (Type 0): Recognized by Turing Machines.
•
Option B (Type 1): Recognized by Linear Bounded Automata.
•
Option C (Type 2 grammar): Correct; recognized by Pushdown Automata.
•
Option D (Type 3): Recognized by Finite Automata.
Reference: Mock Test 06NEC Licensure Syllabus