\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{1, part 1}

% DEFINE THE DUE DATE
\def\due{February 12, 1992}

% title command
\newcommand{\mytitle}{{\large\noindent 6.863J Natural Language
Processing \hfill{} Juliet Bourne \\ 
Lab \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.863J Natural Language
Processing \hfill{} Juliet Bourne \\
Lab \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace*{.15in}\noindent{\fbox{\large\bf #1}}}
% 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} The configuration is there to double the appropriate surface
consonant, as specified by the gemination rule. When a vowel is
encountered followed by an appropriate consonant $C$, a lexical `+' and
a surface $C$ are generated/recognized by this region in the state
table. If this pair $(+.C)$ is not encountered then either the
gemination rule doesn't apply or the automaton enters a failing state.

\prob{2} Most likely, the {\sc SUBSET} $S$ is expanded into its members
and $(s.s)$, $(x.x)$, and $(z.z)$ are considered feasible pairs
for the Epenthesis automaton. Since the pair $(s.s)$ already exists in
the automaton, only $(x.x)$ and $(z.z)$ are given the transition
vectors associated with the $(S.S)$ pair. Therefore, since the lexical
and surface characters are the same, this is reflected in the same way
for both the {\sc GMACHINE} and {\sc RMACHINE} representations of the
Epenthesis automaton, i.e. there are entries in both that look like:
\verb+( ... (x (x (3 3 3 3 0 1))) (z (z (3 3 3 3 0 1))) ... )+.

\prob{3} Looking up a pair in an {\sc RMACHINE} results in (C) a column
of an automaton if the {\sc RMACHINE} represents a single automaton. It
results in (E) a list of columns of automata if the {\sc RMACHINE}
represents several automata.

\prob{4} The only difference between {\sc GMACHINE} and {\sc RMACHINE}
representations is the fact that lexical characters are listes first in
{\sc GMACHINE} and the surface characters are listed first in {\sc
RMACHINE}. This is because the generation algorithm accesses the
automaton(a) by lexical characters whereas the recognition algorithm
uses the surface characters.

\prob{5} No. In the case of the generation algorithm, it is only
necessary to find the entry in {\sc GMACHINE} which corresponds to the
appropriate lexical character (taken from the input). For the
recognition algorithm, it is only necessary to: 1) find the {\sc
RMACHINE} entry for the surface character $0$, and 2) find the entry for
the surface character that next in the input. Thus, {\sc GMACHINE} and
{\sc RMACHINE} representations eliminate the need to search through all
feasible pairs.

\prob{6} Using the order of automata on pp 227-8, this would be the
result of looking up the feasible pair $(a.a)$ in the {\sc RMACHINE}
representation: 

\begin{verbatim}
;; transition vectors                   automaton
( (1)                                ;; surface characters
  (1 1 1 1 0 1)                      ;; epenthesis
  (4 1 0 16 16 16 16 ... 16)         ;; gemination (16 states)
  (1 1 0 0 1 1)                      ;; y-spelling
  (2 1 1 0 1 0 1 1 0 0 1 0 0 1 1)    ;; elision
  (1 0 0 0 1 1 1) )                  ;; i-spelling
\end{verbatim}

\mypage

\prob{7}

\subprob{a} \verb-``try+ed'' ==> ``tried''- (No problems arise in the
Y-spelling automaton.)

\subprob{b} \verb-``hoe+ed'' ==> *** NONE ***- (The elision automaton blocks.)

\subprob{c} The elision automaton blocks since $(e.e)$ matches $(V.V)$
before it matches $(e.e)$ in the columns of the automaton. The wrong
transition vector is associated with $(e.e)$ in the {\sc GMACHINE}.
When the first $(e.e)$ pair is encountered the automaton goes into the
wrong state and thus leads to a failing state. In order to fix this
problem, priority should be given to the more specific matching pairs
when choosing the transition vector for a pair.

\prob{8} If there are lexicons in the continuation class of an entry,
tasks will be constructed for them and $(LexCha.0)$ feasible pairs will
be checked, even if there is no more input.

\prob{9} Generating ``refer+ing'':

\begin{verbatim}
PC-KIMMO>g refer+ing
  refering
\end{verbatim}

\noindent The problem is that the feasible pair $(+.0)$ is tried before
the feasible pair $(+.r)$ which would give the correct gemination
behavior. $(+.0)$ will work because the surface characters automaton
happily gives back whatever alphabetic character is in the lexical form.
The gemination rule works other than this problem of a false working
pair, as evidenced by:

\begin{verbatim}
PC-KIMMO>r refering
  *** NONE ***
PC-KIMMO>r referring
  re`fer+ing     [ V(refer)+PROG ]
\end{verbatim}

\prob{10} The problem with the recognition of ``flier'' is that the noun
root lexicon (as opposed to the verb root lexicon) is searched first.
The recognizer first sees the ``fly'' part as a noun instead of a
verb, so it has to back up to the beginning of the input when it
discovers it cannot parse the ``fly'' in ``flier'' as a noun. This will
happen for all roots that can be nouns or verbs, such as ``fly''.

\end{document}

