## Institutt for Informatikk Universitetet i Bergen INF 225 - Innføring i Programoversettelse - H05

### Voluntary Exercise Set 3 (Group meeting 19.09.2005)

1. Exercise 3.3 on page 138 of the text.

2. Exercise 3.4 on pages 138 and 139 of the text.

3. Exercise 3.6 on page 139 of the text.

4. Show a grammar that generates the set of strings {ambn | m < > n}.

5. Show a grammar that generates the set of strings {ambnhpgq | n = q or m <= p or m+n = p+q}.

6. Show a grammar that generates the set of all palindromes over the alphabet {a, b, c, d }. A palindrome is a string that reads exactly the same backwards as it does forwards. For example, the words mom and kyayk are palindromes in the English language.

7. Assume EMPTY corresponds to the empty string. For each grammar below, either indicate that the grammar generates exactly the language {anbcndiex | n >= 0 and i >= x}, or show why it does not generate the language.

1. S -> aSc | bA
A -> dAe | dA | d

2. S -> AB
A -> aAc | b
B -> dBe | dB | d

3. S -> AB | EMPTY
A -> aAc | b
B -> dBe | EMPTY

4. S -> ABC
A -> aAc | abc
B -> dBe | dB | d
C -> Ce | EMPTY

8. Extend the following expression grammar to include the exponentiation operator **. Your grammar should give ** higher precedence then either * or /, and ** should be right associative.

Exp -> Exp AddOp Term | Term