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

Answer is B. String generated by this language is $a,b,aba,bab,aabaa,\ldots$

All this strings are odd length palindromes.

Comments

but it is not written that grammar should generate all strings that begin and end with same symbol

option C should be " all strings that begin and end with same symbol"

then it is correct to remove option c

is it not?

---

even ur answer contains flaw

the language u given covers  BOTH B and C.

---

aa is starting and ending with same symbal but not cover by above grammar.so option C) is wrong.only option B) is correct

Answer 2

(A) Counter Example :- aa or bb not generated by above Grammar.

(C) Counter example :- aa not genetrated by above Grammer.

(D) Counter Example :- aa not generated, but a generated.

(B) Correct. Odd length palindromes are generated by this grammar.

Answer 3

option b

Comments

I agree with you but I am asking about if all do not mention we assume that it talking about all. As in option C.

---

In option c it is saying it genrate starting and ending with same symble. But it can't genrate all string like string aa.  So it is wrong.

---

Yes it genrate all string . Not subset of string

---

Thanks Bro!!

Answer 4

(B) all odd length palindromes