Practice free →
HomeGATE CSEcomputerscienceTheory 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)._
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions