Any syntactic construct that can be described by a regular expression can also…
2009
Any syntactic construct that can be described by a regular expression can also be described by a:
Answer: C. Context free grammar — Concept: The Chomsky hierarchy classifies grammars by the generative power of their production rules. Type-3 (regular) grammars are the most restricted,…
- A.
Context sensitive grammar
- B.
Non context free grammar
- C.
Context free grammar
- D.
None of the above
Attempted by 62 students.
Show answer & explanation
Correct answer: C
Concept: The Chomsky hierarchy classifies grammars by the generative power of their production rules. Type-3 (regular) grammars are the most restricted, permitting only productions of the form A -> aB or A -> a. Type-2 (context-free) grammars are strictly more general: they permit any production A -> alpha with a single non-terminal on the left-hand side and any string alpha of terminals/non-terminals on the right. Because every type in the hierarchy is nested inside the ones above it, any language generated by a lower type is also generated by every higher type.
A regular expression denotes a regular language, and by Kleene's theorem this is exactly the class of languages accepted by a finite automaton.
Every regular language has an equivalent right-linear (Type-3) grammar, whose productions are restricted to the form A -> aB or A -> a.
A context-free (Type-2) grammar allows any production A -> alpha with one non-terminal on the left; the restricted right-linear form is already a special case of this, so no production needs to be rewritten.
Consequently, the same language generated by the right-linear grammar is simultaneously a valid context-free-grammar derivation, so any syntactic construct describable by a regular expression is also describable by a context-free grammar.
Cross-check: this containment also follows from automata equivalence -- a pushdown automaton that never uses its stack behaves exactly like a finite automaton, and every pushdown automaton has an equivalent context-free grammar, so the finite-automaton language is a CFG language too. The reverse containment fails: the language {an bn | n >= 0} is context-free but has no equivalent regular expression, confirming that context-free grammars are a strict superset of regular languages rather than the reverse.
Result: the correct classification is Context free grammar.
Note: because Type-1 (context-sensitive) and Type-0 (unrestricted) grammars also contain every context-free language, a broader class such as context-sensitive grammar is technically also capable of describing the same construct; standard exam convention for grammar-hierarchy classification questions scores the tightest, most specific sufficient class among those offered, which is the context-free grammar.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2