[Math] Every Regular Language is a Context Free Language

Question

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.

Answer 1

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!