1
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – DoubleRainbowZ Oct 12 at 14:12
  • $\begingroup$ S = a | b | aAa | bBb, A = aAa | aAb | bAa | bAb | a, B = aBa | aBb | bBa | bBb | b $\endgroup$ – DoubleRainbowZ Oct 12 at 14:15
  • $\begingroup$ @DoubleRainbowZ Correct. $\endgroup$ – orlp Oct 12 at 15:24

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.