GATE 2009

Question 12

S→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 odd length palindromes.
C	strings that begin and end with the same symbol.
D	all even length palindromes.

Question 12 Explanation:

From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}

Correct Answer: B

Question 12 Explanation:

From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}