# Building a context-free grammar for this language

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...

• 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? – David Richerby Apr 2 '17 at 14:39
• 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\}^*$. – Hendrik Jan Apr 2 '17 at 16:40

## 1 Answer

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$.

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