Home › GATE CSE › computerscience › Theory of Computation › Every regular language is also context-free. The…
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)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?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$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?Is the language $L = \{a^n b^n c^n \mid n \geq 0\}$ context-free?