# How to convert regular expression to CFG?

How can I convert the regular expression (ab*)*b to a context-free grammar?

When I look for examples I keep seeing plus signs in the expression but I don’t have any. Is that just a different way of writing it?

• $r^+$ is just a shorthand for $r^*r$. Oct 2, 2020 at 7:32
• For the general regular expression to contextfree grammar, see this answer Regular Expression to Context-Free Grammar May 29, 2022 at 17:04

There is a simple algorithm to convert regular expressions to context-free grammars. It goes as follows.

Base cases:

• $$\emptyset$$ corresponds to the empty grammar.
• $$\epsilon$$ corresponds to the grammar $$S \to \epsilon$$.
• $$\sigma$$ (where $$\sigma \in \Sigma$$) corresponds to the grammar $$S \to \sigma$$.

Inductive cases:

• $$r = r_1 + r_2$$. Given CFGs for $$r_1,r_2$$ with disjoint nonterminals and starting symbols $$S_1,S_2$$, add rules $$S \to S_1 \mid S_2$$ and make $$S$$ the new starting symbols.
• $$r = r_1r_2$$. Same, adding the rule $$S \to S_1 S_2$$ instead.
• $$r = r_1{}^*$$. Same, adding the rules $$S \to S S_1 \mid \epsilon$$ instead.