\documentstyle[11pt,simplemargins]{article}
\setallmargins{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{2}

% DEFINE THE DUE DATE
\def\due{September 30, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\ 
Homework \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\
Homework \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.035 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\begin{document}

\mytitle

\prob{1}

\subprob{a} LL(1) is defined as containing exactly those grammars that
have disjoint predict sets for productions that share a common left-hand
side. G is not LL(1) because it non-disjoint predict sets. Namely:

Predict(A $\rightarrow$ B) = First(B) = \{\verb+id+\}

Predict(A $\rightarrow$ B\verb+-+A) = First(B) = \{\verb+id+\}

\noindent and:

Predict(B $\rightarrow$ \verb+id+) = \{\verb+id+\}

Predict(B $\rightarrow$ \verb+id(+A\verb+)+) = \{\verb+id+\}

\noindent (i.e. \verb+id+ predicts two different productions for both A
and B as left-hand sides.)

\subprob{b} Constructing G$'$ such that G$'$ is LL(1) and $L(G') = L(G)$:

Let $S = \{A\rightarrow B, A\rightarrow B-A\}$. 

Create new non-terminal H such that $S = \{A\rightarrow BH, H\rightarrow
-A, H\rightarrow \lambda\}$.

Let $R = \{B\rightarrow id, B\rightarrow id(A)\}$. 

Create new non-terminal F such that $R = \{B\rightarrow id F, F\rightarrow (A), F\rightarrow \lambda\}$.

Therefore, G$'$ is:

A $\rightarrow$ -A $\mid$ (A) $\mid$ BH

B $\rightarrow$ \verb+id+ F

H $\rightarrow$ -A $\mid \lambda$

F $\rightarrow$ (A) $\mid \lambda$

\subprob{c} Determining the function $T: V_n \times V_t \rightarrow P
\cup \{Error\}$:

\vspace*{-.05in}
\begin{tabbing}
xxxxxxxx\= xxxxxxxxxxxxxxxxxxxx\= \kill
T(A,-) \> = A$\rightarrow$-A 	\>since - $\in$ Predict(A$\rightarrow$-A) \\
T(A,() \> = A$\rightarrow$(A)	\>since ( $\in$ Predict(A$\rightarrow$(A)) \\
T(A,)) \> = error 		\>since - $\not\in$ Predict(A$\rightarrow$-A $\mid$ (A) $\mid$ BH) \\ 
T(A,\verb+id+) \> = A$\rightarrow$BH \>since \verb+id+ $\in$ Predict(A$\rightarrow$BH) \\
T(A,\$) \> = error			\>since $\lambda \not\in$ Predict(A$\rightarrow$-A $\mid$ (A) $\mid$ BH) \\ 
T(B,-) \> = error			\>since - $\not\in$ Predict(B$\rightarrow$\verb+id+F) \\
T(B,() \> = error			\>since ( $\not\in$ Predict(B$\rightarrow$\verb+id+F) \\
T(B,)) \> = error			\>since ) $\not\in$ Predict(B$\rightarrow$\verb+id+F) \\
T(B,\verb+id+) \> = B$\rightarrow$\verb+id+F \>since \verb+id+ $\in$ Predict(B$\rightarrow$\verb+id+F) \\
T(B,\$) \> = error			\>since $\lambda \not\in$ Predict(B$\rightarrow$\verb+id+F) \\
T(H,-) \> = H$\rightarrow$-A	\>since - $\in$ Predict(H$\rightarrow$-A) \\ 
T(H,() \> = error			\>since ( $\not\in$
Predict(H$\rightarrow$-A $\mid \lambda$) \\
T(H,)) \> = error			\>since ) $\not\in$
Predict(H$\rightarrow$-A $\mid \lambda$) \\
T(H,\verb+id+) \> = error		\>since \verb+id+ $\not\in$
Predict(H$\rightarrow$-A $\mid \lambda$) \\
T(H,\$) \> = H$\rightarrow \lambda$ \>since $\lambda \in$
Predict(H$\rightarrow \lambda$) \\
T(F,-) \> = error			\>since - $\not\in$
Predict(F$\rightarrow$(A) $\mid \lambda$) \\
T(F,() \> = F$\rightarrow$(A)	\>since ( $\in$ Predict(F$\rightarrow$(A)) \\ 
T(F,)) \> = error			\>since ) $\not\in$
Predict(F$\rightarrow$(A) $\mid \lambda$) \\
T(F,\verb+id+) \> = error		\>since \verb+id+ $\not\in$
Predict(F$\rightarrow$(A) $\mid \lambda$) \\
T(F,\$) \> = F$\rightarrow \lambda$ \>since $\lambda \in$
Predict(F$\rightarrow \lambda$) \\
\end{tabbing}

\mypage

Thus, the table:

\vspace*{.1in}
\begin{tabular}{|c|c|c|c|c|c|}\hline
\mbox{} & - & ( & ) & \verb+id+ & \$ \\ \hline
A & A$\rightarrow$-A & A$\rightarrow$(A) & error & A$\rightarrow$BH &
error \\ \hline
B & error & error & error & B$\rightarrow$\verb+id+F & error \\ \hline 
T & T$\rightarrow$-A & error & error & error & T$\rightarrow \lambda$ \\ \hline
F & error & F$\rightarrow$(A) & error & error & F$\rightarrow \lambda$ \\ \hline
\end{tabular}

\mypage

\prob{2}

\subprob{a} In the context of \verb+b+A\verb+ba+, a look-ahead of \verb+b+
can predict either A$\rightarrow \lambda$ or A$\rightarrow$\verb+b+. A
look-ahead of \verb+ba+ predicts only the production A$\rightarrow
\lambda$ and a look-ahead of \verb+bb+ predicts only
A$\rightarrow$\verb+b+. Therefore, $k=2$ is the smallest value for
which G can be recognized by an LL($k$) parser.

\subprob{b} A PDA is the simplest machine that can recognize G. A DFA is
the only machine simpler than a PDA, but it can't recognize  G because
DFA's only have a look-ahead of 1, i.e. the next symbol in the input. A
PDA, however, has a look-ahead of 2 because it can look at the top of
its stack as well as the next symbol in the input. Thus, a PDA can
recognize G.


\end{document}

