How do I show that every regular language is a context-free language?
I've been told to construct a Context-Free Grammar by Induction on the number of operators in the regular expression; but I'm still not sure.
$\endgroup$ 12 Answers
$\begingroup$Indeed, what you've been told works. The set of regular expressions is the smallest set containing the letters of the alphabet $\Sigma$, and closed under $+$, $\cdot$ (concatenation) and $(\_)^*$. Then the induction is easy:
If the expression is $a$ (a letter), the language is generated by the grammar $S\rightarrow a$, where $S$ is the axiom. If the expression is $A+B$, by induction you have a grammar which generates $A$ and one that generates $B$, let us call their axioms $S_1$ and $S_2$. Then $S\rightarrow S_1 \mid S_2$ together with the rules of the other grammars generate $A+B$.
Try to do it with the other constructions (concatenation and Kleene star), it is not that difficult to see how it works!
$\endgroup$ 6 $\begingroup$Let $A$ be a regular language.Then there exists a DFA $N=(Q,\Sigma,\delta,q_0,F)$ such that $L(N)=A$. Build a context-free grammar $G=(V,\Sigma,R,S)$ as follows:
Set $V=\{R_i \mid q_i \in Q\}$ (that is, $G$ has a variable for every state of $N$). Now, for every transition $\delta(q_i,a)=q_j$ add a rule $R_i\to aR_j$. For every accepting state $q_i∈F$ add a rule $R_i \to \epsilon$. Finally, make the start variable $S=R_0$.
$\endgroup$
