Within the three restricted grammar classes of the Chomsky hierarchy, which is…
2010
Within the three restricted grammar classes of the Chomsky hierarchy, which is the most general?
Answer: B. Context-sensitive grammar — ConceptThe Chomsky hierarchy orders restricted grammar classes by expressive power. Relaxing production restrictions enlarges the corresponding language…
- A.
Regular grammar
- B.
Context-sensitive grammar
- C.
Context-free grammar
- D.
None of the above
Attempted by 12 students.
Show answer & explanation
Correct answer: B
Concept
The Chomsky hierarchy orders restricted grammar classes by expressive power. Relaxing production restrictions enlarges the corresponding language family.
Type 3 denotes regular grammar.
Type 2 denotes context-free grammar.
Type 1 denotes context-sensitive grammar.
Type 0 unrestricted grammar lies outside the three restricted classes named in the question.
Application
For the three named classes, the containment order is regular languages ⊂ context-free languages ⊂ context-sensitive languages. The final class in this containment chain is therefore the most general one in the stated comparison.
Comparison
Class | Chomsky type | Production restriction | Recognizing machine |
|---|---|---|---|
Regular grammar | Type 3 | Linear productions | Finite automaton |
Context-free grammar | Type 2 | One nonterminal on the left | Pushdown automaton |
Context-sensitive grammar | Type 1 | Context-dependent, noncontracting productions | Linear-bounded automaton |
Contrast
Regular grammar is the narrowest listed class and is contained in the context-free class.
Context-free grammar is more general than regular grammar but remains contained in the context-sensitive class.
“None of the above” would apply only if no named class met the condition; the containment order identifies a named class.
Cross-check
The recognizing-machine hierarchy gives the same order: finite automata are less powerful than pushdown automata, which are less powerful than linear-bounded automata. Hence the result is context-sensitive grammar.