BNF grammar for a palindrome

4.8k views Asked by At

I need help with a non-extended BNF grammar:

  • Σ = {a,b}

  • L = {ω ɛ Σ^* | such that w is equal to the reverse of ω}

For example, the strings aba, bab, and ababa are in the language, but string ababab is not.

I am not sure if this is a solution but this is what I found online and I am wondering if I am heading in the right direction:

<palindrome> ::= a <palindrome> a | b <palindrome> b |
                 c <palindrome> c | d <palindrome> d | 
                 e <palindrome> e | ...
                                  | z <palindrome> z
<palindrome> ::= <letter>
<letter>     ::= a | b | c | ... | y | z
1

There are 1 answers

20
arkascha On BEST ANSWER

At least you have to include the words with an even number of characters, so:

<palindrome> ::= a | b | aa | bb | a<palindrome>a | b<palindrome>b