Consider the following grammar for a
language called L:
S →
a S b | b S a | S S |
λ
Now, here are four statements:
(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 the following is correct?
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.