The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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
asked in Theory of Computation by Veteran (59.7k points)
edited by | 3.2k views
y not b & c both or we have to choose very specific????????
There are counter examples for c.So c is not correct.

4 Answers

+23 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
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.
+11 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 (43.2k points)
+7 votes
(B) all odd length palindromes
answered by Veteran (369k points)
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 (213 points)
How option C is covered in option B?

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

44,297 questions
49,787 answers
65,857 users