p. 240
6.1(a): As the productions are applied substrings are formed: one in front of S and one behind S. Everytime a production is applied a or b is appended at the end of the front substring and the same symbol is prepended to the hind string. Thus the language generated by this grammar is {wwr | w
{a, b}* }.
6.1(f): By looking at the productions one can make the following observations:
1. Any number of consecutive b's can appear anywhere in a string.
2. Every string must end with a.
3. Any number of a's can appear anywhere in a string.
4. Every string can start with a or b.
Thus the language generated by this grammar is (a+b)*a.
p. 247
6.43: Since all the S's appearing in intermediate strings must turn into 0 to get to strings of the language, what we need to prove is that all the strings appearing in the process of generating a string from S have more 0's and S's than 1's. For example in S -> 1SS -> 1S0S -> 100S -> 1000, 1SS has two S's for one 1 1's, 1S0S has three 0's and S's combined for one 1 etc. Thus all strings appearing in this generation process have more 0's and S's than 1's. We are going to show that that is always the case.
If we prove that, then when a string w is generated from S, the last step is the application of S -> 0 because that is the only production that eliminates S. Hence w can be written as u0v for some strings u and v and the string just before turnig to w is uSv. Thus if uSv has more 0's ands S's than 1's, then u0v certainly has more 0's than 1's.
Basis Step: 0 obviously has more 0's than 1's.
Inductive Step: Assume that all the strings of length less than n appearing in the generation process have more 0's and S's than 1's. Let x be a string of length n appearing in the generation process. We are going to show that x has more 0's and S's than 1's. Note that the string one step before x can be expressed as ySz for some strings y and z of 0's, 1's and S's and x is obtained by applying one of the productions to the S. Hence yz has at least as many 0's and S's combined as 1's. Now there are six possibilities for x depending on what production is applied. They are y0z, yS0z, y0Sz, y1SSz, ySS1z and yS1sz. In all six cases, there are more 0's and S's than 1's in x.
End of Proof
p. 290
7.5(b):
