Consider the following grammar for a
language
called L:
S
→ a S a | b S b | λ
For this problem, a 'palindrome' is defined as a
string made of an arbitrary number (including 0)
of as and bs that reads the same
backwards as it does forwards. Which one of the statements
below is true?
L contains only
palindromes, but some palindromes do not belong
to L.L contains all of the palindromes, as
well as some strings that are not palindromes.L is exactly the set of all
palindromes.L contains a finite number of
palindromes.You can think inductively to determine the truth value of some of these statements.
One way to get started is to derive a few of the
shortest strings in L and look for
patterns.
You can also consider each one of the strings of length
0, 1, 2, etc., to determine which ones are
not in L and why.