UNLV CS456 Spring 2008 Homework 8

1. Give a context-free grammar for each of these languages.

(a) The language of all strings of the form a^{i}b^{j} such that i ≥ 2j.

(b) Binary numerals for multiples of 3, where leading zeros are not allowed. I cannot figure out how to do this one with fewer than four variables.

(c) The language of all algebraic expressions over the variables x, y, z with the operators of addition +, subtraction -, multiplication ∗, exponentiation ∗, and negation -, and with parentheses. Your grammar must have only one variable, the start symbol.

2. Give an unambiguous context-free grammar for each of these languages.

(a) The language of all strings of the form a^{i}b^{j} such that j ≥ 2i.

(b) The language of all palindromes over {0, 1}.

(c) The language of all algebraic expressions over the variables x, y, z with the operators of addition ‘+’ subtraction ‘-’ multiplication ‘*’ exponentiation ‘ˆ’ and negation ‘-’, and with parentheses. Your grammar must respect the usual precedence of operators. You will need at least three variables.

3. Write a polynomial time reduction of the knapsack problem to the partition problem.