Every regular language is also context-free. The PROOF construction is
ARegular languages cannot be context-free
BMirror DFA as a right-linear grammar
CUse the pumping lemma backwards
DAdd a stack to the DFA, making it a PDA
Answer & Solution
Correct answer: B. Mirror DFA as a right-linear grammar
1. Every regular language IS context-free. Quickest proof: write a RIGHT-LINEAR grammar mirroring the DFA.
2. For DFA $M = (Q, \Sigma, \delta, q_0, F)$:
- Variables: $V = Q$ (one per state)
- Terminals: $\Sigma$
- Start: $q_0$
- Rules: for each $\delta(q, a) = q'$, add $q \to aq'$. For each $q \in F$, add $q \to \varepsilon$.
3. The grammar is RIGHT-LINEAR (every rule's RHS has at most one variable, and it's at the right end). Right-linear grammars generate exactly regular languages.
4. So regular ⊆ context-free, with strict containment (e.g. $\{a^n b^n\}$ is CFG but not regular).
5. Option D would prove a weaker fact (regular ⊆ recognised by PDA, which is also true). Option A is wrong. Option C is unrelated.
_Source: Jeff Erickson, "Models of Computation", §5.13 (Right-linear grammars and regular languages)._
Keep practising Theory of Computation
Browse all Theory of Computation questions for GATE CSE, or explore more Computer Science topics.
Related questions
Which class of grammars generates ALL recursively enumerable languages?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isContext-free languages are RECOGNISED by which type of machine?A CFG is AMBIGUOUS ifConsider the CFG with rule $S \to aSb \mid \varepsilon$. The language generated isWhich of these is an example of an IRREGULAR (non-regular) language?