CFG for A = { w | w has odd length where first, middle and last symbols are equal }, w from {0,1}* (epsilon is in the language)

A = { w | w has odd length where first, middle and last symbols are equal }, w from {0,1}* (epsilon is in the language)

ε, 011101010, 10101, 1 are in the language.

Let 'e' is an epsilon.

S -> 0X0X0 | 1X1X1 | e

Bad, I don't know length of both X's. Because of that my middle symbol would not be in the middle anymore....

S -> X0X | X1X | e

X -> 10X | 01X | 1 | 0

Bad, w can starts with 0 and ends with 1 and length can be even

I don't have an idea....

Solution

Straight forward would be the following grammar

S -> 0X0 | 1Y1 | 0 | 1 | e
X -> 0X0 | 0X1 | 1X0 | 1X1 | 0
Y -> 0Y0 | 0Y1 | 1Y0 | 1Y1 | 1

Ie the first character of the word determines whether you go into X or Y. An X always has an odd number of arbitrary characters, with the middle character being a 0. An Y is more or less the same, just that the middle character is 1.

I don't say it's the minimal grammar, but it should do the trick ...