\documentclass{article}
\usepackage{fullpage}

\input{macros}

\setlength{\parskip}{.4cm}
\setlength{\baselineskip}{15pt}
\setlength{\parindent}{0cm}

\author{}
\date{}

\begin{document}

\hrule
\begin{center}
{\LARGE \sc $\underline{\mbox{Problem Set 7}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: March 7, 2013 & Due on: March 14, 2013
\end{tabular}
\end{center}
\hrule

{\bf Instructions:} This homework has 3 problems that can be solved in
groups of size at most 3. Please follow the homework guidelines given
on the class website; submitions not following these guidelines will
not be graded. 

{\bf Recommended Reading:} Lecture 13, 14, and 15.

\begin{problem}{Design}
Design a PDA to recognize the language
\[
C = \{x\# y\: |\: x,y \in \{0,1\}^*,\ x \neq y\}
\]
You need not prove the correctness of your construction but you should
provide the intuition behind the states and stack symbols used, that
makes your construction clear and understandable.\points{10}
\end{problem}

\begin{problem}{Comprehension+Design+Proof}
A CFG $G$ will be said to \emph{right-linear} if every rule in $G$ is
either of the form $A \rightarrow \emptystr$ or $A \rightarrow aB$,
where $a$ is a terminal symbol, and $B$ is a variable. Prove that if
$G$ is right-linear then $\lang{G}$ is regular. {\em Hint:} Construct
an NFA that accepts a string iff it is generated by $G$.\points{10}
\end{problem}

\begin{problem}{Proof}
Let $G$ be a CFG in Chomsky normal form that contains $b$
variables. Show that if $G$ generates some string with a derivation
having at least $2^b$ steps, $\lang{B}$ is infinite.\points{10}
\end{problem}

\end{document}
