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 '17 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 '17 at 16:40

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 '17 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 '17 at 15:04
  • $\begingroup$ Most probably your answer is OK. The original formulation may have used * for concatenation. $\endgroup$ Apr 3 '17 at 16:32

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.