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 {a^mbⁿ | m < > n}.

5. Show a grammar that generates the set of strings {a^mbⁿh^pg^q | 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 {aⁿbcⁿdⁱe^x | 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
   AddOp -> + | -
   Term -> Term MultOp Factor | Factor
   MultOp -> * | /
   Factor -> ( Exp ) | num

9. Exercise 3.20 on page 141 of the text.