I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.

This is really confusing me, I'm having trouble with making sure that b is always in the middle. Any help?

  • 1
    $\begingroup$ Hint: This problem is really, really easy. $\endgroup$
    – gnasher729
    Commented Jun 4, 2020 at 6:06
  • $\begingroup$ Stronger hint: You put equal numbers of characters to each side, and you make sure there’s a b in the middle by putting a b in the middle. $\endgroup$
    – gnasher729
    Commented Jun 4, 2020 at 6:08

1 Answer 1



Here is a guideline to solve this problem:

Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, by counting once again"


$S\rightarrow b\space | \space xSy$ for every $x,y\in \{a,b\}$

Yea, thats everything in the CFG!

  • $\begingroup$ How are you supposed to do all that in a CFG? $\endgroup$
    – C.Cam
    Commented Jun 4, 2020 at 4:10
  • $\begingroup$ Counting is simple. Use the stack. Guessing is literally usimg the non-determinism and each letter we read we both guess that its the middle and its not the middle, and the rest is just comparing the rest to the stack $\endgroup$
    – nir shahar
    Commented Jun 4, 2020 at 4:15
  • $\begingroup$ Makes no sense to me at all. $\endgroup$
    – gnasher729
    Commented Jun 4, 2020 at 6:06
  • $\begingroup$ oh sorry, i mistook it for a PDA. $\endgroup$
    – nir shahar
    Commented Jun 4, 2020 at 9:19
  • $\begingroup$ Just fixed it, hope it helps now! $\endgroup$
    – nir shahar
    Commented Jun 4, 2020 at 9:23

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.