S → aSa |bSb| a | b; The language generated by the

Home » Theory of Computation » Theory of computation miscellaneous » Question

S → aSa |bSb| a | 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 with the same symbol
4. all even length palindromes

Correct Option: B

Given grammar S → aSabSbab. The strings generated through this grammar is definitely palindromes,but not all it can only generate palindromes of odd length only so (A) & (D) are false, (B) is correct. Also it can generate palindromes which start and end with same symbol, but not all strings eg. aabababba .