# Write Context-free grammar for union of two language

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?

• Your grammar for $L_2$ generates $\{b^naab^m\mid n\ge 0, m\ge 0\}$ -- there's nothing in it to force the two sequences of $b$s to have the same length. – Henning Makholm Dec 7 '17 at 17:54

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.
• Sorry, I was wrong write assignment. Instead of $\cup$ there should be chaining. So there is create $L=L_{1}\cdot (L_{2})^{*}$. Is this change result? – user4362081 Dec 7 '17 at 18:33
• In that case your approach is correct except for the fact that you forget the empty word in the Kleene iteration. And the comment concerning $L_2$ on the original question is true, too. I had not checked that part. – Peter Leupold Dec 7 '17 at 18:47