context-free-grammar

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