Institutt for Informatikk
Universitetet i Bergen
I 125 - Innf°ring i Programoversettelse


Voluntary Exercise Set 3 (Gruppe°velser. 3)

  1. Exercise 2.22 on page 93 of the text. (Solution)

  2. Exercise 2.24 on page 93 of the text. (Solution)

  3. Exercise 3.3 on page 138 of the text.

  4. Exercise 3.6 on page 139 of the text.

  5. Show a grammar that generates the set of strings {ambn | m ¬= n}.

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

  7. 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.

  8. 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