Register

ISRO2020-39

• edited by
2,134 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
User Avatar

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 

User Avatar
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.
User Avatar
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.

(:

 

 

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

7 votes
7 votes
5 answers
1
Satbir asked Jan 13, 2020
7,127 views
ISRO2020-41
Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is $3$ $4$ $5$ $6$
Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is$3$$4$$5$$6$
User Avatar
1 votes
1 votes
2 answers
2
Satbir asked Jan 13, 2020
2,388 views
ISRO2020-40
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$ and $255$. RE and higher CFG and higher CSG and higher Recursively enumerable language
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...
User Avatar
6 votes
6 votes
3 answers
3
Satbir asked Jan 13, 2020
3,953 views
ISRO2020-66
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 Bits) Under what conditions $Z$ will be $1$? $X>Y$ $X<Y$ $X=Y$ $X!=Y$
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...
User Avatar
Link Copied!