ISRO CSE 2020 | Question: 39

Question

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

• A. Strings that begin and end with the same symbol
• B. All odd and even length palindromes
• C. All odd length palindromes
• D. All even length palindromes

Answer 1

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 

Comments

thanks

Answer 2

Answer: c) All odd length palindromes.

Answer 3

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

so the option C is correct.

Answer 4

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.

(: