A clue for problem 1. Let L be the language of all strings over the alphabet {a,b} which have equal numbers of a's and b's. Thus, for example, the empty string is in L, as are ab and ba, as are aabb, abab, abba, baab, baba, bbaa, aaabbb, and so forth. The following grammar generates L. S --> aSb S --> bSa S --> SS S --> epsilon We will explain in class why this grammar generates L, and also why it is ambiguous. Can you find an unambiguous grammar that generates L? That's much harder. The language in problem 3 is generated by the following context-free grammar: S --> S+S S --> S-S S --> S*S S --> (S) S --> a S --> b