3.5k views

$$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:

1. all palindromes
2. all odd length palindromes
3. strings that begin and end with the same symbol
4. all even length palindromes
edited | 3.5k views
0
y not b & c both or we have to choose very specific????????
0
There are counter examples for c.So c is not correct.
0
not able to generate bbab and many other strings. well still this question creates confusion because option c should have been c) all strings that begin and end with the same symbol
0
aa is not genrated . In option c
0

In option C, there is not talking about all .

All the odd length palindrome have same being and end character.

So, i confused.

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

All this strings are odd length palindromes.

edited
+1
Even c is correct too?
+20

C is not correct because it does not generate set of all strings that begin and end with the same symbol.

aaaaba is not generated by given grammar.

+1
@sachin_mittal_1  SIR , Questions says that Language generated by above grammar is the set of ____ ( strings that begin and end with the same symbol )
If palindrome means string will begin and end with same symbol . so C is also correct , right ? They didn't asks it in reverse order ie. strings that begin and end with the same symbol is accepted by the grammar .
I marked option B because it gives more clarity . I dont feel option C is wrong
+2

Your statement is Wrong bcoz you just consider Palindrome not Odd length Palindromes ,which is given in Option B.

We have counter ex for option C,ex- aa, bb .

Hence option (B) is the ONLY correct option.

0
@gatematesingh even Epsilon is not generated by this grammar so C is wrong
0
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?
0

the language u given covers  BOTH B and C.
0
aa is starting and ending with same symbal but not cover by above grammar.so option C) is wrong.only option B) is correct
(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.
(B) all odd length palindromes
+1 vote

option b

0
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.
0
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.
0
Yes it genrate all string . Not subset of string
0
Thanks Bro!!

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

0
How option C is covered in option B?

1
2