# Context-free grammar how to have same number of variables within a language

I am trying to get a CFG for the language:

The set $$A$$ of odd-length strings in $$\{a,b\}^*$$ whose first, middle and last symbols are all the same.

(some example of correct answers would be: a, aaa, ababa, aababba, some incorrect answers include: ɛ, aaaa, abbaa)

This is what I've done so far:

S = a|b|aTaTa|bTbTb
T = aT|bT|ɛ


However the problem is, I need T to be a string of any combination of 'a's and 'b's but of the same length, but I'm not sure how to express this. As you can see above, I can get strings made up of any combination, but they won't be the same length when passed to S. Any help is appreciated!

## 1 Answer

Your approach won't work. Whenever you try to match the length of two non-terminals, that should be a big red flag your approach won't work.

Here's a hint: expand from the middle out, after starting with $$S = a \mid b \mid aAa \mid bBb$$. Can you take it from here?

• Thanks a lot! I think I have realized the correct way to do it now :) Will post my solution in a sec, once I fine-tune the logic. – DoubleRainbowZ Oct 12 '19 at 14:12
• S = a | b | aAa | bBb, A = aAa | aAb | bAa | bAb | a, B = aBa | aBb | bBa | bBb | b – DoubleRainbowZ Oct 12 '19 at 14:15
• @DoubleRainbowZ Correct. – orlp Oct 12 '19 at 15:24