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

(c) Binary numerals for positive multiples of 3, where leading zeros are not allowed. Can you do this with only three variables?

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