ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: e1caa754
Which type of formal grammar in the Chomsky hierarchy generates languages that can be recognized by Finite Automata?
Which type of formal grammar in the Chomsky hierarchy generates languages that can be recognized by Finite Automata?
Multiple Choice Options
- A✓ Correct Option
Regular Grammar (Type-3)
- B
Context-Free Grammar (Type-2)
- C
Context-Sensitive Grammar (Type-1)
- D
Unrestricted Grammar (Type-0)
Detailed Technical Solution & Explanation
Type-3 grammars (Regular Grammars, containing left-linear or right-linear production rules) generate Regular Languages, which are recognized by Finite Automata (DFA and NFA).
Option Analysis:
•
Option A (Regular Grammar (Type-3)): Correct. Generates regular languages recognized by Finite Automata.
•
Option B (Context-Free Grammar (Type-2)): Recognized by Pushdown Automata.
•
Option C (Context-Sensitive Grammar (Type-1)): Recognized by Linear Bounded Automata.
•
Option D (Unrestricted Grammar (Type-0)): Recognized by Turing Machines.
Reference: Demo2 · Set 1NEC Licensure Syllabus