generates the language
This claim is not so obvious, and we need to provide convincing arguments.
First, it is clear that every sentential form of G has an equal number of a’s
and b’s, since the only productions that generate an a, namely S → aSb and S →
bSa, simultaneously generate a b. Therefore, every element of L ( G) is in L. It is
a little harder to see that every string in L can be derived with G.
Let us begin by looking at the problem in outline, considering the various
forms w ∈ L can have. Suppose w starts with a and ends with b. Then it has the
form
where w 1 is also in L. We can think of this case as being derived starting with
if S does indeed derive any string in L. A similar argument can be made if w
starts with b and ends with a. But this does not take care of all cases, since a
string in L can begin and end with the same symbol. If we write down a string of
this type, say aabbba, we see that it can be considered as the concatenation of
two shorter strings aabb and ba, both of which are in L. Is this true in general?
To show that this is indeed so, we can use the following argument: Suppose that,
starting at the left end of the string, we count +1 for an a and −1 for a b. If a
string w starts and ends with a, then the count will be +1 after the leftmost
symbol and −1 immediately before the rightmost one. Therefore, the count has to
go through zero somewhere in the middle of the string, indicating that such a
string must have the form
where both w 1 and w 2 are in L. This case can be taken care of by the
production S → SS.