1. Consider the following context-free grammar with non-terminal S and terminals {a, b}. epsilon denotes the empty string. The grammar has three productions:

S ::= a S b S | b S a S | epsilon

a) Show that there are two different ways of deriving the sentence abab.

b) Try to describe in words the language generated by this grammar.

2. Try to design a grammar for the following languages, over the alphabet {0, 1}. If the language is regular, describe it by means of a regular expression, otherwise by use a context-free grammar.

a) The set of all strings of 0's and 1's such that every 0 is immediately followed by at least one 1.

b) Strings of 0's and 1's in which 011 does not appear as a substring.

c) Strings with an equal number of 0's and 1's.

3. The grammar of C++ includes (among many others!) the following productions:

multiplicative-expression ::= cast-expression

cast-expression ::= unary-expression | (type-id) cast expression

unary-expression ::= unary-operator cast-expression | postfix-expression

unary-operator ::= + | - | &

postfix-expression ::= primary-expression

primary-expression ::= identifier | ( expression )

type-id ::= identifier

Consider the code fragment: (X)+Y.

Show that there are two ways of interpreting this fragment according to the grammar given above. Explain in words what the two interpretations are. How many ways are there of interpreting (X)+(Y)+Z ?