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....
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 ...