

\documentclass[11pt]{article}
\setlength{\parskip}{0.5em}
\setlength{\parindent}{0em}


\marginparwidth 0pt
\oddsidemargin -0.4in
\marginparsep 0pt
\topmargin  -0.6in
\textwidth   7.2in
\textheight  9.1in

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[xdvi,dvips]{graphics}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{array}
\usepackage{float}
\usepackage{dsfont}
\usepackage{xspace}

\input{preamble}
%\input{special}

\newcounter{jump}

\newcounter{tbl}
\newcounter{fgr}[section]

\renewcommand{\thefgr}{\thesection.\arabic{fgr}}

\newcounter{mdl}
\newcounter{prp}
\newcounter{action}
\newcounter{priority}
\newcounter{benchmark}


\renewcommand{\theaction}{{\rm{\Alph{mdl}}\arabic{action}}}

\renewcommand{\Label}{\label}
\renewcommand{\Ref}{\ref}

\renewcommand{\today}{}




\begin{document}
\title{UNLV CS456 Spring 2008 Homework 8}
\author{}
\maketitle

%{\tt
%\vskip 0.2in
%\input{tempdt}
%}

\date{}


\begin{enumerate}
\item Give a context-free grammar for each of these languages.
	\begin{enumerate}
\item
The language of all strings of the form $a^ib^j$ such that $i\ge 2j$.
\item
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.
\item
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.
	\end{enumerate}
\item Give an unambiguous context-free grammar for each of these languages.
	\begin{enumerate}
\item
The language of all strings of the form $a^ib^j$ such that $j\ge 2i$.
\item
The language of all palindromes over $\braced{0,1}$.
\item
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.
	\end{enumerate}
\item
Write a polynomial time reduction of the knapsack problem to
the partition problem.
\end{enumerate}


\end{document}

