ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: e0b29d6f
In the Chomsky hierarchy, Context-Sensitive Grammars (Type-1) are recognized and parsed by:
In the Chomsky hierarchy, Context-Sensitive Grammars (Type-1) are recognized and parsed by:
Multiple Choice Options
- A
Deterministic Pushdown Automata
- B
Non-deterministic Pushdown Automata
- C
Finite State Automata
- D✓ Correct Option
Linear Bounded Automata (LBA)
Detailed Technical Solution & Explanation
Context-Sensitive Languages (Type-1) are precisely characterized and recognized by Linear Bounded Automata (LBA)—non-deterministic Turing Machines whose tape head cannot move beyond the portion of tape occupied by the input string plus endmarkers.
Option Analysis:
•
Option A (Deterministic Pushdown Automata): Recognizes deterministic context-free languages.
•
Option B (Non-deterministic Pushdown Automata): Recognizes general context-free languages.
•
Option C (Finite State Automata): Recognizes regular languages.
•
Option D (Linear Bounded Automata (LBA)): Correct. Recognizes Type-1 context-sensitive languages.
Reference: Mock Test 05NEC Licensure Syllabus