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


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


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}

  • $\begingroup$ Please use MathJax formatting (cs.stackexchange.com/editing-help#latex) instead of code formatting for mathematic formulae. $\endgroup$ – Nathaniel Apr 3 at 20:04
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 4 at 6:24

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 :)

  • $\begingroup$ 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. $\endgroup$ – Legend 7 Apr 3 at 20:11
  • $\begingroup$ @Legend7 i have updated the answer a bit, take a look at it again :) $\endgroup$ – 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 $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.