retagged by
20,200 views
34 votes
34 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
retagged by

7 Answers

Best answer
38 votes
38 votes

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

All this strings are odd length palindromes.

edited by
17 votes
17 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.
14 votes
14 votes

option b

Answer:

Related questions

20 votes
20 votes
5 answers
2
Kathleen asked Sep 22, 2014
8,362 views
In which one of the following page replacement policies, Belady's anomaly may occur?FIFOOptimalLRUMRU
33 votes
33 votes
5 answers
4