Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

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?

• Hint: This problem is really, really easy. Commented Jun 4, 2020 at 6:06
• 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. Commented Jun 4, 2020 at 6:08

PDA:

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"

CFG:

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

Yea, thats everything in the CFG!

• How are you supposed to do all that in a CFG? Commented Jun 4, 2020 at 4:10
• 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 Commented Jun 4, 2020 at 4:15
• Makes no sense to me at all. Commented Jun 4, 2020 at 6:06
• oh sorry, i mistook it for a PDA. Commented Jun 4, 2020 at 9:19
• Just fixed it, hope it helps now! Commented Jun 4, 2020 at 9:23