Assignment III

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.