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 grammarConcept: The Chomsky hierarchy classifies grammars by the generative power of their production rules. Type-3 (regular) grammars are the most restricted,…

  1. A.

    Context sensitive grammar

  2. B.

    Non context free grammar

  3. C.

    Context free grammar

  4. 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.

  1. A regular expression denotes a regular language, and by Kleene's theorem this is exactly the class of languages accepted by a finite automaton.

  2. Every regular language has an equivalent right-linear (Type-3) grammar, whose productions are restricted to the form A -> aB or A -> a.

  3. 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.

  4. 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

Loading lesson…