Converting a regular expression to a context-free grammar

Does this conversion look right? I am learning conversion from RE to CFG.

RE:

$$(a \cup b)^* \cup ab(a \cup b)^*$$

CFG:

Terminals: $$S_1 \to a \\ S_2 \to b$$

This is for the first $$(a + b)^*$$:

\begin{align} &S_3 \to S_1 \mid S_2 && (a \cup b) \\ &S_4 \to S_3S_4 \mid \epsilon && (a \cup b)^* \end{align}

This is for the $$ab$$ in the middle:

$$S_5 \to a \\ S_6 \to b$$

This is for the second $$(a \cup b)$$ and $$(ab)$$ in the middle:

\begin{align} &S_7 \to S_1 \mid S_2 && (a \cup b) \\ &S_8 \to S_7S_8 \mid \epsilon && (a \cup b)^* \\ &S_9 \to S_5 S_6 && (ab) \end{align}

Concatenated $$ab$$ with the second $$(a \cup b)^*$$:

\begin{align} &S_{10} \to S_8 S_9 && (ab(a \cup b)^*) \end{align}

This the final CFG:

\begin{align} &S_{11} \to S_4 \mid S_{10} && (a \cup b)^* \cup ab(a \cup b)^* \end{align}

• Please use MathJax formatting (cs.stackexchange.com/editing-help#latex) instead of code formatting for mathematic formulae. – Nathaniel Apr 3 at 20:04
• The point of the algorithm for converting a regular expression to a context-free grammar is that it is completely mechanical. A computer could do it, literally. No creativity is required. If you follow its steps, then you have applied it correctly. – Yuval Filmus Apr 4 at 6:24

2 Answers

This CFG is indeed correct, but can be greatly simplified.

• First, there is no need to create a new variable that would derive only a terminal value, that is - $$s_1,s_2,s_5,s_6$$ are not required.
• For a similar reason, we don't need $$s_9$$.
• Another simplification is that $$(a\cup b)^*$$ was already generated by $$s_4$$. There is no need to create $$s_7$$ and $$s_8$$ for this usage

Considering those things, the CFG will be reduced to:

• $$S\rightarrow A\space|\space abA$$
• $$A \rightarrow AB\space|\space\epsilon$$
• $$B \rightarrow a\space |\space b$$

Notice also that $$L(ab(a\cup b)^*)\subseteq L((a\cup b)^*)$$, and thus:

$$L((a\cup b)^*\cup ab(a\cup b)^*) = L((a\cup b)^*) \cup L(ab(a\cup b)^*) = L((a\cup b)^*)$$

And thus an even smaller CFG will be:

• $$S \rightarrow A$$
• $$A \rightarrow AB \space | \space \epsilon$$
• $$B \rightarrow a\space | \space b$$

Essentially we removed one unnecessary derivation rule. This can be simplified a bit further, go ahead and give it a try :)

• thank you. Our professor wants us to do it this way. I did not know I could reuse s4 instead of creating s7 and s8. – Legend 7 Apr 3 at 20:11
• @Legend7 i have updated the answer a bit, take a look at it again :) – nir shahar Apr 3 at 20:13

As @nir_shahar said the mentioned language is equivalent to $$L((a \cup b)^*)$$, hence the grammar may be written much simpler:

$$S \rightarrow aS | bS| \epsilon$$

• I think the idea was for OP to work this out. – Yuval Filmus Apr 4 at 5:58