I have a hard time creating a context-free grammar for the language

$$L=\{(a^n)^*(b^m)^*y\mid y\in\{a,b\}^*,\ |y|=n+m \}\,.$$

Any help breaking down the problem is appreciated, since I'm getting nowhere with this one...

  • 1
    $\begingroup$ Your definition of the language was a little unclear to me. I've tried to write it in more easily parsed notation: could you check that I've put the brackets in the right place? $\endgroup$ Apr 2, 2017 at 14:39
  • 2
    $\begingroup$ For April fool's this language is a little late. Since any star contains $\varepsilon$ all I can make of this is $L = \{a,b\}^*$. $\endgroup$ Apr 2, 2017 at 16:40

1 Answer 1


I'm not sure to have fully understood your notation.

As production rules you could consider:

$S \rightarrow aSa \ |aSb \ | S_1 | \epsilon$

$S_1 \rightarrow bS_1a | \ bS_1b \ | \ \epsilon$

In $S$ for each $a$ you add an $a$ or a $b$ or you can go to $S_1$ and then never come back to $S$ again.

In $S_1$ for each $b$ you add an $a$ or a $b$.

  • $\begingroup$ Ok, so I've totally misunderstood the language that OP specified I guess. $\endgroup$
    – abc
    Apr 2, 2017 at 14:43
  • $\begingroup$ Well, it wasn't specified very clearly at all. Maybe I misunderstood it! Let's see if the asker clarifies. $\endgroup$ Apr 2, 2017 at 15:04
  • $\begingroup$ Most probably your answer is OK. The original formulation may have used * for concatenation. $\endgroup$ Apr 3, 2017 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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