S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the…
2016
S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the alphabet is the set of , ISRO 2016
- 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 56 students.
Show answer & explanation
Correct answer: B
The grammar S → aSa ∣ bSb ∣ a ∣ b generates palindromes. The base cases 'a' and 'b' are palindromes of length 1 (odd). The recursive rules S → aSa and S → bSb wrap existing palindromes with matching characters, preserving the palindrome property while increasing length by 2. Since we start with odd length (1) and add even numbers (2), all generated strings have odd lengths. Thus, the language is the set of all odd-length palindromes.