Write Context-free grammar for union of two language

Question

I have following example:

Create context-free grammar for language $L=L_{1}\cup (L_{2})^{*}$

We work with alphabet $\{a,b\}^{*}$ and

$L_{1} =$ generate words with preffix "aab" or postfix "ba"

$L_{2} =$ generate $b^{n}aaab^{n} |n\ge 0$

I make grammar for $L_{1}$, also for $L_{2}$ a then put together.

$L_{1}\Rightarrow aabA|Aba \\ A\Rightarrow aA|bA|a|b|\varepsilon $

$L_{2}\Rightarrow BaaB\\ B\Rightarrow bB|\varepsilon $

And now make union $L=L_{1}\cup (L_{2})^{*}$

$L\Rightarrow L_{1}L_{2}X \\ X\Rightarrow L_{2}X|\varepsilon \\ L_{1}\Rightarrow aabA|Aba \\ A\Rightarrow aA|bA|a|b|\varepsilon \\ L_{2}\Rightarrow BaaB\\ B\Rightarrow bB|\varepsilon$

Is that process and result correct?

Answer 1

Your grammar for $L$ produces the concatenation, because you have $L_1L_2$ in your first production. If you change it to $$L \rightarrow L_1 | L_2X$$ things look better. However $L_2^*$ also contains the empty word with zero iterations. You need to add this somewhere, for example by using $L \rightarrow L_1 | X$.

This assumes that your CFG definition allows chain rules $A \rightarrow B$, which are sometimes not wanted, because they make derivations longer.