Institutt for Informatikk
Universitetet i Bergen
INF 225 - Innføring i Programoversettelse - H07
Voluntary Exercise Set 3 (Group meeting 21.09.2009)
Exercise 3.3 on page 138 of the text.
Exercise 3.4 on pages 138 and 139 of the text.
Exercise 3.6 on page 139 of the text.
Show a grammar that generates the set of strings
{a^{m}b^{n} | m < > n}.
Show a grammar that generates the set of strings
{a^{m}b^{n}h^{p}g^{q} |
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
{a^{n}bc^{n}d^{i}e^{x} |
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
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