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}
&amp;S_3 \to S_1 \mid S_2 &amp;&amp; (a \cup b) \\
&amp;S_4 \to S_3S_4 \mid \epsilon &amp;&amp; (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}
&amp;S_7 \to S_1 \mid S_2 &amp;&amp; (a \cup b) \\
&amp;S_8 \to S_7S_8 \mid \epsilon &amp;&amp; (a \cup b)^* \\
&amp;S_9 \to S_5 S_6 &amp;&amp; (ab)
\end{align}
Concatenated $ab$ with the second $(a \cup b)^*$:
\begin{align}
&amp;S_{10} \to S_8 S_9 &amp;&amp; (ab(a \cup b)^*)
\end{align}
This the final CFG:
\begin{align}
&amp;S_{11} \to S_4 \mid S_{10} &amp;&amp; (a \cup b)^* \cup ab(a \cup b)^*
\end{align}
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 :)