S -> aSa|bSb|a|b; The language generated by the above grammar over the…
2009
S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of
- A.
All palindromes
- B.
All odd length palindromes.
- C.
Strings that begin and end with the same symbol
- D.
All even length palindromes
Attempted by 89 students.
Show answer & explanation
Correct answer: B
Answer: The language is the set of all odd-length palindromes over {a,b}.
Reasoning:
Base: The productions S -> a and S -> b produce the strings "a" and "b", which are palindromes of length 1.
Recursive step: The productions S -> aSa and S -> bSb add the same symbol at both ends of any string generated from S, so the palindrome property is preserved and the length increases by 2.
No empty-center case: There is no production for the empty string, so derivations cannot produce even-length palindromes (which would require an empty center).
Conclusion: Starting from length 1 and repeatedly adding two symbols preserves palindromicity and yields only odd lengths, so the language is exactly all palindromes of odd length over {a,b}.
Examples: "a", "b", "aba", "bab", "ababa", ...
A video solution is available for this question — log in and enroll to watch it.