Assignment II

Due date Feb. 19, 2004.

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:

additive-expression ::= multiplicative-expression | additive-expression + multiplicative-expression
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 ?