How can I write my context-free grammar?

Question

I'm trying to write a CFG over the alphabet Σ = {a,b} for all words starting and ending with the same number of a's, with at least one b in the middle.

Now I understand the basic concept of CFG, variables, production rules, etc. Unfortunately I've run out of ideas for writing the aforementioned CFG. All I've got so far is

S → aYXYa
X → XbX | b | λ
Y → ???

I think that the production rules S and X will give me a string with two as on both sides with as many bs in the middle as I'd like. However, I'm not sure how I can also put as many as on both sides of the bs while making sure there are exactly the same number of as on each side.

Any suggestions, solutions would be much appreciated. Thanks.

Answer 1

As an ex-professor who's taught this class before, I'm not going to give you the answer. I will, however, give you a hint:

You have the right idea to break it into two parts, the a's and the rest. However, you're not doing either one of them right.

First try writing: aⁿbaⁿ then branch off from there.

Hope that helps.

Answer 2

S → aSa | B
B → b | bB

This should be the CFG you're looking for. Whenever you've dealing with the same thing on the beginning and end, remember that you can't guarantee that the same var will be filled the same way. As such, you have to make those explicit.

Answer 3

It's been a while since my CS undergrad days but this looks reasonable:

S -> aSa | bX

X -> bX | E

Basically, you start with S and add as many pairs of a's as you want and then switch to X and add as many b's as you want.