In the context-free grammar below, S is the start symbol, a and b are…
2006
In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar?
- A.
aaaa
- B.
baba
- C.
abba
- D.
babaaabab
Attempted by 13 students.
Show answer & explanation
Correct answer: B
The grammar generates palindromes using the rules S → aSa | bSb | a | b | ϵ. A palindrome reads the same forwards and backwards. Option B (baba) is not a palindrome, so it cannot be generated by this grammar. Options A (aaaa), C (abba), and D (babaaabab) are palindromes and can be derived using the given rules. Therefore, baba is NOT generated by the grammar.
A video solution is available for this question — log in and enroll to watch it.