\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 6}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: February 28, 2013 & Due on: March 7, 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 12, and 13.

\begin{problem}{Design+Proof}
Design a context-free grammar for the language $L = \{a^ib^j\: |\: 2i
\leq j \leq 3i,\ i,j \in {\mathbb N}\}$. Provide a formal proof that
your construction is correct. \emph{Hint:} Build a grammar for the
case when $j = 2i$ and $j = 3i$, and think of a way to fuse the two
together.\points{10}
\end{problem}

\begin{problem}{Comprehension+Design}
Let $G = (V,\Sigma,R,\tuple{\mbox{STMT}})$ be the following grammar
\[
\begin{array}{rcl}
\tuple{\mbox{STMT}} & \longrightarrow & \tuple{\mbox{ASSIGN}}\: |\: 
  \tuple{\mbox{IF-THEN}}\: |\: \tuple{\mbox{IF-THEN-ELSE}}\\
\tuple{\mbox{IF-THEN}} & \longrightarrow & {\tt if\ condition\ then\ } 
  \tuple{\mbox{STMT}}\\
\tuple{\mbox{IF-THEN-ELSE}} & \longrightarrow & {\tt\ if\ condition\ then\ } 
  \tuple{\mbox{STMT}}\ {\tt else\ } \tuple{\mbox{STMT}}\\
\tuple{\mbox{assign}} & \longrightarrow & {\tt a := 1}
\end{array}
\]
where $\Sigma = \{{\tt if}, {\tt then}, {\tt else}, {\tt condition},
{\tt a := 1}\}$ and $V =
\{\tuple{\mbox{STMT}},\tuple{\mbox{IF-THEN}},\tuple{\mbox{IF-THEN-ELSE}},
\tuple{\mbox{ASSIGN}}\}$. $G$ is a natural looking grammar for a
fragment of a programming language, but $G$ is ambiguous.
\begin{enumerate}
\item Show that $G$ is ambiguous.\points{5}
\item Give a new unambiguous grammar for the same language. You need
  not prove that your grammar is correct but explain your
  construction. You may want to look at examples in Lecture
  12.\points{5}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension}
Consider the PDA $P$ over the input alphabet $\setof{0,1,\#}$ shown in
the figure below; $a$, in the transitions below, is either $0$ or $1$.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}
\node[autst](A) at (0,0) {$A$};
\node[autst](B) at (3,0) {$B$};
\node[autst](C) at (6,0) {$C$};
\node[autst](D) at (9,0) {$D$};
\node[finalst](E) at (12,0) {$E$};
\initialst{A};
\draw (A) -- node[above]{$\emptystr,\emptystr \rightarrow \$$} (B);
\selfloopabove{B}{$a,\emptystr \rightarrow a$};
\draw (B) -- node[above]{$\#,\emptystr \rightarrow \emptystr$} (C);
\selfloopabove{C}{$a,\emptystr \rightarrow \emptystr$};
\draw (C) -- node[above]{$\emptystr,\emptystr \rightarrow \emptystr$} (D);
\selfloopabove{D}{$a,a \rightarrow \emptystr$};
\draw (D) -- node[above]{$\emptystr,\$ \rightarrow \emptystr$} (E);
\selfloopabove{E}{$a,\emptystr \rightarrow \emptystr$};
\end{tikzpicture}
\end{center}
\end{figure}
\begin{enumerate}
\item Write the formal description of the PDA $P$ listing the states,
  stack alphabet, transition function, initial state and final
  states.\points{5}
\item For each of the following strings either show that they are
  accepted by $P$ by describing an accepting computation, or show that
  they are not accepted by showing the \emph{entire} computation tree
  on the input: $01\#10$, $01\#01$, $01\#111000$.\points{3}
\item Describe the language recognized by the PDA $P$. Give an
  informal justification for your answer, by explaining how the PDA
  works.\points{2}
\end{enumerate}
\end{problem}

\end{document}
