The language which is generated by the grammar S → aSa|bSb|a|b over the…
2020
The language which is generated by the grammar S → aSa|bSb|a|b over the alphabet {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
Attempted by 70 students.
Show answer & explanation
Correct answer: C
The grammar S → aSa|bSb|a|b generates palindromes. The base cases 'a' and 'b' are odd-length (1). Each recursive step adds 2 characters, preserving odd length. Thus, the language is the set of all palindromes of odd length.