Due date Oct. 1, 2003
1. We have seen that a grammar where all productions are of the form:
A -> aB, A -> c (A, B non-terminals, a,c terminals)
defines a regular language, and that from the grammar we can build directly
an FSA that recognizes the corresponding language. Show that if all the
productions have the form:
A -> Ba, A -> c
such a grammar also represents a regular language.
2. Describe the language generated by the following grammars (upper-case
letters are non-terminals, lower case terminals):
a) S -> SaS | b
b) S -> aSb | bSa | epsilon
3. The following grammar is not regular but it generates a regular language.
Write the regular expression that describes it:
S -> SSS | a | ab
4. Show that the following grammar is ambiguous, by producing one string
in the language that has two different parse trees:
S -> aS | aSbS | epsilon
5. Show that the language generated by the grammar:
S -> aSbS | bSaS | epsilon
is the set of all strings with an equal number of a's and b's. You might
want to prove this by induction over the length of the string, or by
reasoning over the sentential forms that derive a string.