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
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
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.
(:
64.3k questions
77.9k answers
244k comments
80.0k users