4k 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 | 4k 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.

0
Because  aaba , bbbab, abbbabba these are the string which begin and end with the same symbol but our given grammar unable to generates  .....

Hence option C is wrong and

Option B is true because  of odd length palindrome generates given grammar.

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

All this strings are odd length palindromes.

by Active (4.1k points)
edited
0
Even c is correct too?
+23

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.

+2
@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.
by Boss (41.9k points)
(B) all odd length palindromes
by Veteran (431k points)

option b

by Boss (36.5k points)
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!!
+1 vote

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

by (457 points)
0
How option C is covered in option B?

Let's consider this one....

by (471 points)