Consider the following grammar followed by four statements about the language L generated by this grammar:
<s> ::= a <s> b | b <s> a | <s> <s> | ε

(i) All of the strings in L have even length, that is, they contain an even number of terminals.
(ii) The string abababbab belongs to L.
(iii) L contains all of the possible strings made up of an arbitrary number (including 0) of as and bs in any order.
(iv) Each and every string in L contains exactly the same number of as and bs.

Which of these statements are true?

(i) and (iv) only
  1. (i) only
  2. (ii) only
  3. (iii) only
  4. (iv) only
  5. (i) and (iv) only
  6. (ii) and (iii) only
  7. none of the four statements 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.