Question

$S\to aSa|bSb|a|b$
The language generated by the above grammar over the alphabet {a,b} is the set of

• A. all Palindromes
• B. all even length palindromes
• C. strings that begin and end with the same symbol
• D. all odd length palindromes

Answer 1

The correct option is D all odd length palindromes

$S\to aSa|bSb|a|b$
is the grammar corresponding to all odd length palindromes.
Notice that choice (c) is not correct since "abaa" is a string that begins and ends with the same symbol but cannot be generated by above grammar.
Since all strings generates by this grammar have odd length, choices (a) and (d) are also incorrect.