The Gateway to Computer Science Excellence
+20 votes

$$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
in Theory of Computation by Veteran (52.2k points)
edited by | 4k views
y not b & c both or we have to choose very specific????????
There are counter examples for c.So c is not correct.
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
aa is not genrated . In option c

In option C, there is not talking about all . 

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

So, i confused.

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.

6 Answers

+28 votes
Best answer

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 by
Even c is correct too?


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.

@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

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.

@gatematesingh even Epsilon is not generated by this grammar so C is wrong
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 option C) is wrong.only option B) is correct
+13 votes
(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)
+7 votes
(B) all odd length palindromes
by Veteran (431k points)
+7 votes

option b

by Boss (36.5k points)
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!!
+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)
How option C is covered in option B?
0 votes

Let's consider this one....

by (471 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,910 users