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?

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – user4362081 Dec 7 '17 at 18:33
  • $\begingroup$ 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. $\endgroup$ – Peter Leupold Dec 7 '17 at 18:47
  • $\begingroup$ OK, thank you and also @Henning Makholm $\endgroup$ – user4362081 Dec 7 '17 at 20:23

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.