GATE CSE 2009 | Question: 12, ISRO2016-37

Question

$$S \to aSa \mid bSb\mid a\mid 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

Comments

@Pranavpurkar Agreed! Bad framing of options

---

Abhrajyoti00

it all depends on what the question setter wants from us.

---

@Pranavpurkar

no both b and c cant be true, because in option c we can have ‘abaa’ in which first and last symbol is same but it can’t be generated by above grammar

Answer 1

option A is wrong as the given grammar can not generate the string like aa, bb, aaaa  

option D is wrong because it also covered string like  aa, bb which can not be generated by the given grammar

option C and option B are correct but option C is already covered in option B so we can neglect option C 

option B is the correct answer as it can generate a,b , bab, aaa, ababa ... etc

Comments

How option C is covered in option B?

Answer 2

option B all odd length palindromes is the correct

and c is false as aaba can not be generated from it

Answer 3

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