The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
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
asked in Theory of Computation by Veteran (52.1k points)
edited by | 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.

5 Answers

+24 votes
Best answer

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

All this strings are odd length palindromes.

answered by Active (4.1k points)
edited by
+1
Even c is correct too?
+20

@gatematesingh

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
even ur answer contains flaw

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
+12 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.
answered by Boss (41k points)
+7 votes
(B) all odd length palindromes
answered by Veteran (414k points)
+1 vote

option b

answered by Boss (34.2k 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!!
0 votes

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

answered by (307 points)
0
How option C is covered in option B?
Answer:

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
49,811 questions
54,540 answers
188,429 comments
75,606 users