Institutt for Informatikk
Universitetet i Bergen
I 125 - Innføring i Programoversettelse
Voluntary Exercise Set 3 (Gruppeøvelser. 3)
-
Exercise 2.22 on page 93 of the text.
(Solution)
-
Exercise 2.24 on page 93 of the text.
(Solution)
-
Exercise 3.3 on page 138 of the text.
-
Exercise 3.6 on page 139 of the text.
-
Show a grammar that generates the set of strings
{ambn | m ¬= n}.
-
Show a grammar that generates the set of strings
{ambnhpgq |
n = q or m <= p or m+n = p+q}.
-
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.
-
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.
-
S -> aSc | bA
A -> dAe | dA | d
-
S -> AB
A -> aAc | b
B -> dBe | dB | d
-
S -> AB | EMPTY
A -> aAc | b
B -> dBe | EMPTY
-
S -> ABC
A -> aAc | abc
B -> dBe | dB | d
C -> Ce | EMPTY