edited by
2,073 views
2 votes
2 votes

The language which is generated by the grammar $S \rightarrow aSa \mid bSb \mid a \mid b$ over the alphabet of $\{a,b\}$ is the set of

  1. Strings that begin and end with the same symbol
  2. All odd and even length palindromes
  3. All odd length palindromes
  4. All even length palindromes
edited by

4 Answers

1 votes
1 votes

Strings generated by grammar are $\{a, b, aba, aaa, bab, ababa, aaaaa,..\}$ all are odd length palindromes. Option b) & d) eliminated.

Option a) is not correct as $'aaba'$ is a string starts and ends with same symbol but not generated by given grammar.

Hence Option C) is correct 

0 votes
0 votes
the string generated by this grammar are {a,b,aaa,aba,bab,bbb,aaaaa,ababb..........}

so the option C is correct.
0 votes
0 votes

We can solve such kinds of question with the help of OPTION ELIMINATION METHOD.

 FOR OPTION A,B,D: It does not generate {aa}

Hence,OPTION C is correct.

(:

 

 

Answer:

Related questions

7 votes
7 votes
5 answers
1
Satbir asked Jan 13, 2020
7,017 views
Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is$3$$4$$5$$6$
1 votes
1 votes
2 answers
2
Satbir asked Jan 13, 2020
2,301 views
Which of the following classes of languages can validate an $\text{IPv4}$ address in dotted decimal format? It is to be ensured that the decimal values lie between $0$ an...
6 votes
6 votes
3 answers
3
Satbir asked Jan 13, 2020
3,850 views
The following circuit compares two $2$-bit binary numbers, $X$ and $Y$ represented by $X_1X_0$ and $Y_1Y_0$ respectively. ($X_0$ and $Y_0$ represent Least Significant Bit...