Consider the following grammar for a language called L:
<s> ::= a <s> a | b <s> b | ε

Given that, 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.
  1. L contains all of the palindromes, as well as some strings that are not palindromes.
  2. L contains only palindromes, but some palindromes do not belong to L.
  3. L is exactly the set of all palindromes.
  4. L contains a finite number of palindromes.
  5. None of the other options is true.

You can use structural induction (informally) 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.