nlp-english-exercises.tex

\setlength{\medskipamount}{1.6\medskipamount}%%%%% Mona's suggestion

\begin{exercise}[washing-clothes-exercise]%
Read the following text once for understanding, and remember as much of
it as you can. There will be a test later.
\begin{squote}
The procedure is actually quite simple.  First you arrange things into
different groups.  Of course, one pile may be sufficient depending on how much
there is to do.  If you have to go somewhere else due to lack of facilities
that is the next step, otherwise you are pretty well set.  It is important not
to overdo things.  That is, it is better to do too few things at once than too
many.  In the short run this may not seem important but complications can
easily arise.  A mistake is expensive as well.  At first the whole procedure
will seem complicated.  Soon, however, it will become just another facet of
life.  It is difficult to foresee any end to the necessity for this task in
the immediate future, but then one can never tell.  After the procedure is
completed one arranges the material into different groups again.  Then they can
be put into their appropriate places.  Eventually they will be used once more
and the whole cycle will have to be repeated.  However, this is part of life.
\end{squote}

\end{exercise} 
% id=23.0 section=23.1

%%%% 23.1: Phrase Structure Grammars (9 exercises, 2 labelled)
%%%% =========================================================

\begin{exercise} %fe-f05
%\begin{enumerate}
An {\em HMM grammar} is essentially a standard HMM whose state variable
is $N$ (nonterminal, with values such as $Det$, $Adjective$, $Noun$ and so on) and whose
evidence variable is $W$ (word, with values such as $is$, $duck$, and so on). 
The HMM model includes a prior $\pv(N_0)$, a transition model $\pv(N_{t+1}|N_t)$,
and a sensor model $\pv(W_t|N_t)$.
Show that every HMM grammar can be written as a PCFG. [Hint: start by thinking about how the
HMM prior can be represented by PCFG rules for the sentence symbol. You may find it helpful
to illustrate for the particular HMM with values $A$, $B$ for $N$ and values $x$, $y$ for $W$.]
%\end{enumerate}
\end{exercise} 
% id=extras-28-oct.6 section=23.1

\begin{uexercise} %fe-f05
Consider the following PCFG for simple verb phrases:
\begin{formula}
0.1: VP \rightarrow Verb\\
0.2: VP \rightarrow Copula\ Adjective\\
0.5: VP \rightarrow Verb\ the\ Noun\\
0.2: VP \rightarrow VP\ Adverb\\
0.5: Verb \rightarrow is\\
0.5: Verb \rightarrow shoots\\
0.8: Copula \rightarrow is\\
0.2: Copula \rightarrow seems\\
0.5: Adjective \rightarrow \mbf{unwell}\\
0.5: Adjective \rightarrow \mbf{well}\\
0.5: Adverb \rightarrow \mbf{well}\\
0.5: Adverb \rightarrow \mbf{badly}\\
0.6: Noun \rightarrow \mbf{duck}\\
0.4: Noun \rightarrow \mbf{well}
\end{formula}

\begin{enumerate}
\item Which of the following have a nonzero probability as a VP?
(i) shoots the duck well well well\quad (ii) seems the well well\quad (iii) shoots the unwell well badly

\item What is the probability of generating ``is well well''?

\item What types of ambiguity are exhibited by the phrase in (b)?
%(i) lexical\quad (ii) syntactic\quad (iii) referential\quad (iv) none

\item Given any PCFG, is it possible 
to calculate the probability that the PCFG generates a string of exactly 10 words?

%\item A PCFG learning algorithm takes as input a set of strings $D$ and outputs
%the PCFG $h$ that maximizes $\log P(D|h) - C(h)$, where $C$ is a measure of the
%complexity of $h$. For a suitably defined $C$, this could be an example of
%(i) Bayesian learning\quad (ii) MAP learning\quad (iii) maximum likelihood learning.
\end{enumerate}
\end{uexercise} 
% id=extras-28-oct.5 section=23.1


\begin{iexercise} % fe-s04
Consider the following simple PCFG for noun phrases:
\begin{formula}
0.6: NP \rightarrow Det\ AdjString\ Noun\\
0.4: NP \rightarrow Det\ NounNounCompound\\
0.5: AdjString \rightarrow Adj\ AdjString\\
0.5: AdjString \rightarrow \Lambda\\
1.0: NounNounCompound \rightarrow Noun\ Noun\\
0.8: Det \rightarrow \mbf{the}\\
0.2: Det \rightarrow \mbf{a}\\
0.5: Adj \rightarrow \mbf{small}\\
0.5: Adj \rightarrow \mbf{green}\\
0.6: Noun \rightarrow \mbf{village}\\
0.4: Noun \rightarrow \mbf{green}
\end{formula}
where $\Lambda$ denotes the empty string.

\begin{enumerate}
\item What is the longest NP that can be generated by this grammar?
(i) three words\quad (ii) four words\quad (iii) infinitely many words
\item Which of the following have a nonzero probability of being generated as complete NPs?
(i) a small green village\quad (ii) a green green green\quad (iii) a small village green
\item What is the probability of generating ``the green green''?
\item What types of ambiguity are exhibited by the phrase in (c)?
\item Given any PCFG and any finite word sequence, is it possible 
to calculate the probability that the  sequence was generated by the PCFG?
%\item Suppose that, out of 1000 observed noun phrases, 700 begin with 
%``$\mbf{the}$'' and 300 begin with ``$\mbf{a}$'', and that as a result we reset
%the probabilities for the two $Det$ rules to 0.7 and 0.3. This is best 
%viewed as an example of\\
%(i) Bayesian learning\quad (ii) MAP learning\quad (iii) maximum likelihood learning.\\\\
\end{enumerate}
\end{iexercise} 
% id=extras-28-oct.9 section=23.1


\begin{exercise}
Outline the major differences between Java (or any other computer
language with which you are familiar) and English, commenting on the
``understanding'' problem in each case.  Think about such things as
grammar, syntax, semantics, pragmatics, compositionality,
context-dependence, lexical ambiguity, syntactic ambiguity,
reference finding (including pronouns), background knowledge, and what
it means to ``understand'' in the first place.
\end{exercise} 
% id=23.5 section=23.1

\begin{exercise}
This exercise concerns grammars for very simple languages.
\begin{enumerate}
\item Write a context-free grammar for the language \(a^n b^n\).
\item Write a context-free grammar for the palindrome language: the set of all
strings whose second half is the reverse of the first half.
\item Write a context-sensitive grammar for the duplicate language: the set of
all strings whose second half is the same as the first half.
\end{enumerate}
\end{exercise} 
% id=23.10 section=23.1

\begin{exercise}
Consider the sentence ``Someone walked slowly to the supermarket''
and a lexicon consisting of the following words:
\def\ra{\(\bnfeq\)}

\begin{tabular}{@{\quad}l@{\quad}l}
\tabtop \bnf{Pronoun} \bnfeq \bnft{someone} & \bnf{Verb} \bnfeq \bnft{walked} \\
\bnf{Adv} \bnfeq \bnft{slowly} & \bnf{Prep} \bnfeq \bnft{to}\\
\tabbot \bnf{Article} \bnfeq \bnft{the} & \bnf{Noun} \bnfeq \bnft{supermarket}
\end{tabular}

\noindent Which of the following three grammars, combined with the lexicon,
generates the given sentence? Show the corresponding parse tree(s).

\begin{tabular}{l@{\qquad}l@{\qquad}l}

\tabtop (A):			& (B):			& (C):			\\*
\bnf{S} \bnfeq  \bnf{NP} \bl \bnf{VP}		& \bnf{S} \bnfeq  \bnf{NP} \bl \bnf{VP}		& \bnf{S} \bnfeq  \bnf{NP} \bl \bnf{VP}		\\*
\bnf{NP} \bnfeq  \bnf{Pronoun}	& \bnf{NP} \bnfeq  \bnf{Pronoun}		& \bnf{NP} \bnfeq  \bnf{Pronoun}	\\*
\bnf{NP} \bnfeq  \bnf{Article} \bl \bnf{Noun}	& \bnf{NP} \bnfeq  \bnf{Noun}		& \bnf{NP} \bnfeq  \bnf{Article} \bl \bnf{NP}		\\*
\bnf{VP} \bnfeq  \bnf{VP} \bl \bnf{PP}	& \bnf{NP} \bnfeq  \bnf{Article} \bl \bnf{NP}		& \bnf{VP} \bnfeq  \bnf{Verb} \bl \bnf{Adv}		\\*
\bnf{VP} \bnfeq  \bnf{VP} \bl \bnf{Adv} \bl \bnf{Adv}	& \bnf{VP} \bnfeq  \bnf{Verb} \bl \bnf{Vmod}		& \bnf{Adv} \bnfeq  \bnf{Adv} \bl \bnf{Adv}	\\*
\bnf{VP} \bnfeq  \bnf{Verb}		& \bnf{Vmod} \bnfeq  \bnf{Adv} \bl \bnf{Vmod}		& \bnf{Adv} \bnfeq  \bnf{PP}		\\*
\bnf{PP} \bnfeq  \bnf{Prep} \bl \bnf{NP}	& \bnf{Vmod} \bnfeq  \bnf{Adv}		& \bnf{PP} \bnfeq  \bnf{Prep} \bl \bnf{NP}	\\*
\bnf{NP} \bnfeq  \bnf{Noun}		& \bnf{Adv} \bnfeq  \bnf{PP}		& \bnf{NP} \bnfeq  \bnf{Noun}		\\*
\tabbot \mbox{~}	& \bnf{PP} \bnfeq  \bnf{Prep} \bl \bnf{NP}		& \mbox{~} 
\end{tabular}

\medskip\noindent For each of the preceding three grammars, write down three sentences of English and three sentences of non-English generated by the grammar.
Each sentence should be significantly different, should be at least
six words long, and should include some new lexical
entries (which you should define).  Suggest ways to improve each
grammar to avoid generating the non-English sentences.
\end{exercise} 
% id=23.11 section=23.1

%% \begin{iexercise}[buffalo-exercise]%
%% (Derived from Barton {\em et al.} \citeyear{Barton+al:1987}.) This
%% exercise concerns a language we call \(\mbox{\it Buffalo}^n\), which is
%% a subset of English (and a subset of \Eng{0}) with only one word in the
%% lexicon: {\em buffalo\index{buffalo}}.  Here are two sentences
%% from the language:

%% Buffalo buffalo buffalo Buffalo buffalo.

%% Buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.

%% \noindent 
%% In case you don't believe these are sentences, here are two English
%% sentences with corresponding syntactic structure:

%% Dallas cattle bewilder Denver cattle.

%% Chefs London critics admire cook French food.

%% \noindent
%% Write a grammar for \(\mbox{\it Buffalo}^n\).  The lexical categories
%% are city, plural noun, and (transitive) verb, and there should be one
%% grammar rule for sentence, one for verb phrase, and three for
%% noun phrase: plural noun, noun phrase preceded by a city as a
%% modifier, and noun phrase followed by a reduced relative clause. A
%% reduced relative clause is a clause that is missing the relative
%% pronoun. It consists of a subject noun phrase
%% followed by a verb without an object.  An example reduced relative
%% clause is ``London critics admire'' in the example above. Tabulate the
%% number of possible parses for \(\mbox{\it Buffalo}^n\) for \(n\) up to~10.
%% Extra credit: Carl de Marcken\nindex{de~Marcken, C.} calculated that there
%% are 121,030,872,213,055,159,681,184,485 \(\mbox{\it Buffalo}^n\)
%% sentences of length 200 (for the grammar he used).  How did he do that?
%% \end{iexercise} 
%% % id=23.12 section=23.1

\begin{uexercise}
Collect some examples of time\index{time expressions} expressions,
such as ``two o'clock,'' ``midnight,'' and ``12:46.''  Also think up
some examples that are ungrammatical, such as ``thirteen o'clock'' or
``half past two fifteen.''  Write a grammar for the time language.
\end{uexercise} 
% id=23.18 section=23.1


%%%% 23.2: Syntactic Analysis (Parsing) (4 exercises, 1 labelled)
%%%% ============================================================

\begin{iexercise} % fe-s04
Some linguists have argued as follows:
\begin{quote} Children learning
a language hear only {\em positive examples} of the language and no
{\em negative examples}. Therefore, the hypothesis that ``every
possible sentence is in the language'' is consistent with all the
observed examples.  Moreover, this is the simplest consistent
hypothesis. Furthermore, all grammars for languages that are supersets
of the true language are also consistent with the observed data. Yet
children do induce (more or less) the right grammar. It follows that
they begin with very strong innate grammatical constraints that rule out 
all of these more general hypotheses {\em a priori}.
\end{quote}
Comment on the weak point(s) in this argument from a statistical learning viewpoint.
\end{iexercise} 
% id=extras-28-oct.10 section=23.2

\begin{exercise}[chomsky-form-exercise]
In this exercise you will transform \Eng{0} into Chomsky Normal Form (CNF). There are five steps:
(a) Add a new start symbol, (b) Eliminate \(\epsilon\) rules, 
(c) Eliminate multiple words on right-hand sides,
(d) Eliminate rules of the form (\bnf{X} \bnfeq \bnf{Y}),
(e) Convert long right-hand sides into binary rules.  
\begin{enumerate}
\item The start symbol, \(S\), can  occur only on the left-hand side in CNF. 
Replace \bnf{S} everywhere by a new symbol \bnf{S'} and add a rule of the form \bnf{S} \bnfeq \bnf{S'}.
\item The empty string, \(\epsilon\) cannot appear on the right-hand side in CNF. \Eng{0} does not have any rules with \(\epsilon\), 
so this is not an issue.
\item A word can appear on the right-hand side in a rule only of the form (\bnf{X} \bnfeq {\em word}). 
Replace each rule of
the form (\bnf{X} \bnfeq \ldots {\em word} \ldots) with (\bnf{X} \bnfeq \ldots \bnf{W'} \ldots) and (\bnf{W'} \bnfeq {\em word}),
using a new symbol \bnf{W'}.
\item A rule (\bnf{X} \bnfeq \bnf{Y}) is not allowed in CNF; it must be (\bnf{X} \bnfeq \bnf{Y} \bnf{Z}) or (\bnf{X} \bnfeq {\em word}).
Replace each rule of the form (\bnf{X} \bnfeq \bnf{Y}) with a set of rules of the form (\bnf{X} \bnfeq \ldots),
one for each rule  (\bnf{Y} \bnfeq \ldots), where (\ldots) indicates one or more symbols.
\item Replace each rule of the form (\bnf{X} \bnfeq \bnf{Y} \bnf{Z} \ldots) with two rules, (\bnf{X} \bnfeq \bnf{Y} \bnf{Z'})
and (\bnf{Z'} \bnfeq \bnf{Z} \ldots), where \bnf{Z'} is a new symbol.
\end{enumerate}
Show each step of the process and the final set of rules.
\end{exercise} 
% id=23.1 section=23.2

\begin{iexercise}
Consider the following toy grammar:
\begin{squote}
\bnf{S} \bnfeq \bnf{NP} \bnf{VP} \\
\bnf{NP} \bnfeq \bnf{Noun} \\
\bnf{NP} \bnfeq \bnf{NP} \bnft{and} \bnf{NP} \\
\bnf{NP} \bnfeq \bnf{NP} \bnf{PP} \\
\bnf{VP} \bnfeq \bnf{Verb} \\
\bnf{VP} \bnfeq \bnf{VP} \bnft{and} \bnf{VP} \\
\bnf{VP} \bnfeq \bnf{VP} \bnf{PP} \\
\bnf{PP} \bnfeq \bnf{Prep} \bnf{NP} \\
\\
\bnf{Noun} \bnfeq \bnft{Sally} \bnfor \bnft{pools} \bnfor \bnft{streams} \bnfor \bnft{swims} \\
\bnf{Prep} \bnfeq \bnft{in} \\
\bnf{Verb} \bnfeq \bnft{pools} \bnfor \bnft{streams} \bnfor \bnft{swims}
\end{squote}
\begin{enumerate}
\item Show all the parse trees in this grammar for the sentence ``Sally swims in 
streams and pools.''
\item Show all the table entries  that would be made by a (non-probabalistic) CYK parser
on this sentence.
\end{enumerate}

\end{iexercise} 
% id=23.7 section=23.2

\begin{exercise}[exercise-subj-verb-agree]
Using DCG notation, write a grammar for a language that is just like
\Eng{1}, except that it enforces agreement between the subject and verb of a
sentence and thus does not generate ungrammatical sentences such as ``I smells the wumpus.''
\end{exercise} 
% id=23.3 section=23.3

%%%%%%%%%%%%%% \pagebreak %%%%%%% used pagebreak for US edition
\begin{uexercise}
Consider the following PCFG:
\begin{squote}
\bnf{S} \bnfeq \bnf{NP} \bnf{VP} [1.0] \\
\bnf{NP} \bnfeq \bnf{Noun} [0.6] \bnfor \bnf{Pronoun} [0.4] \\
\bnf{VP} \bnfeq \bnf{Verb} \bnf{NP} [0.8] \bnfor \bnf{Modal} \bnf{Verb} [0.2] \\
\\
\bnf{Noun} \bnfeq \bnft{can} [0.1] \bnfor \bnft{fish} [0.3] \bnfor \ldots \\
\bnf{Pronoun} \bnfeq \bnft{I} [0.4] \bnfor \ldots \\
\bnf{Verb} \bnfeq \bnft{can} [0.01] \bnfor \bnft{fish} [0.1] \bnfor \ldots\\
\bnf{Modal} \bnfeq \bnft{can} [0.3] \bnfor \ldots
\end{squote}
The sentence ``I can fish'' has two parse trees with this grammar. Show the two trees,
their prior probabilities, and their conditional probabilities, given the sentence.
\end{uexercise} 
% id=23.8 section=23.2


%%%% 23.3: Augmented Grammars and Semantic Interpretation (5 exercises, 1 labelled)
%%%% ==============================================================================

\begin{exercise}
An augmented context-free grammar can represent languages that a
regular context-free grammar cannot. Show an augmented context-free
grammar for the language \(a^nb^nc^n\).  The allowable values for
augmentation variables are 1 and \noprog{Successor}\((n)\), where \(n\) is
a value.  The rule for a sentence in this language is
\[
S(n) \bnfeq A(n) \bl B(n) \bl C(n) \ .
\]
Show the rule(s) for each of \bnf{A}, \bnf{B}, and \bnf{C}.
\end{exercise} 
% id=23.2 section=23.3


\begin{uexercise}
Augment the \Eng{1} grammar so that it handles article--noun
agreement. That is, make sure that ``agents'' and ``an agent'' are \bnf{NP}s, but
``agent'' and ``an agents'' are not.
\end{uexercise} 
% id=23.4 section=23.3


\begin{exercise}
Consider the following sentence (from {\em The New York Times,} July 28, 2008):
\begin{quote}
Banks struggling to recover from multibillion-dollar loans on real estate are
curtailing loans to American businesses, depriving even healthy companies
of money for expansion and hiring.
\end{quote}
\begin{enumerate}
\item Which of the words in this sentence are lexically ambiguous?
\item Find two cases of syntactic ambiguity in this sentence (there
are more than two.)
\item Give an instance of metaphor in this sentence.
\item Can you find semantic ambiguity?
\end{enumerate}
\end{exercise} 
% id=23.6 section=23.3

\begin{exercise}[washing-clothes2-exercise]
Without looking back at \exref{washing-clothes-exercise}, answer the following
questions:
\begin{enumerate}
\item What are the four steps that are mentioned?
\item What step is left out?
\item What is ``the material'' that is mentioned in the text?
\item What kind of mistake would be expensive?
\item Is it better to do too few things or too many? Why?
\end{enumerate}
\end{exercise} 
% id=23.9 section=23.3


%%%% 23.4: Machine Translation (5 exercises, 0 labelled)
%%%% ===================================================


\begin{exercise}
Select five sentences and submit them to an online translation service.
Translate them from English to another
language and back to English. Rate the resulting sentences for
grammaticality and preservation of meaning.  Repeat the process; does
the second round of iteration give worse results or the same results?
Does the choice of intermediate language make a difference to the
quality of the results?
If you know a foreign language, look at the translation of one paragraph into that language.
Count and describe the errors made,
and conjecture why these errors were made.
\end{exercise} 
% id=23.14 section=23.4

\begin{exercise}
The \(D_i\) values for the sentence in \figref{mt-alignment-figure} sum to 0.  Will that be true
of every translation pair?  Prove it or give a counterexample.
\end{exercise} 
% id=23.15 section=23.4

\begin{exercise}
(Adapted from \citeA{Knight:1999}.) Our translation model assumes
that, after the phrase translation model selects phrases and the
distortion model permutes them, the language model can unscramble the
permutation. This exercise investigates how sensible that assumption
is. Try to unscramble these proposed lists of phrases into the correct order:
\begin{enumerate}
\item have, programming, a, seen, never, I, language, better
\item loves, john, mary
\item is the, communication, exchange of, intentional, information brought, 
by, about, the production, perception of, and
signs, from, drawn, a, of, system, signs, conventional, shared
\item created, that, we hold these, to be, all men, truths, are, equal, self-evident
\end{enumerate}
Which ones could you do? What type of knowledge did you draw upon?
Train a bigram model from a training corpus, and use it to find the
highest-probability permutation of some sentences from a test
corpus.  Report on the accuracy of this model.
\end{exercise} 
% id=23.16 section=23.4

%% \begin{iexercise}
%% In an English--French dictionary, the translation for
%% ``hear'' is the verb ``entendre.''  But when the first statistical machine  translation systems
%% were trained 
%% on the Canadian Hansard, the most probable French translation for ``hear'' was
%% ``Bravo.'' Explain why that is.  ({\em Hint}: you might want to look at
%% some Hansard text. Try a Web search for [Canada Hansard] and then search for [hear].
%% \end{iexercise} 
%% % id=23.17 section=23.4


%%%% 23.5: Speech Recognition (1 exercises, 0 labelled)
%%%% ==================================================

\begin{exercise}
Calculate the most probable path through the HMM in \figref{sr-hmm-figure} for
the output sequence \([C_1,C_2,C_3,C_4,C_4,C_6,C_7]\).  Also give its probability.
\end{exercise} 
% id=23.19 section=23.5





% \begin{exercise}
% Describe how a simple pseudonatural-language (template-based)
% explanation\index{explanation!natural language} facility can be built
% for a vanilla, backward-chaining, logical reasoning system. The
% explanation facility should be written as a program \prog{Why} that
% generates an explanation after \prog{Ask} has answered a question from
% the user.  The explanation should consist of a description of the
% premises and inference method used to reach the conclusion; the user
% should be able to further query the premises to see how they were derived.
% \end{exercise}

%% \begin{exercise}
%% Which of the following are reasons for introducing a quasi-logical form?
%% \begin{enumerate}
%% \item To make it easier to write simple compositional grammar rules.
%% \item To extend the expressiveness of the semantic representation language.
%% \item To be able to represent quantifier scoping ambiguities (among others)
%% in a succinct form.
%% \item To make it easier to do semantic disambiguation.
%% \end{enumerate}
%% \end{exercise}


%% \begin{exercise}
%% Determine what semantic\index{semantic interpretation} interpretation would be given to the following
%% sentences by the grammar in this chapter:
%% \begin{enumerate}
%% \item It is a wumpus.
%% \item The wumpus is dead.
%% \item The wumpus is in 2,2.
%% \end{enumerate}
%% Would it be a good idea to have the semantic interpretation for ``It
%% is a wumpus'' be simply \(\Exi{x} x \elt \J{Wumpuses}\)?  Consider
%% alternative sentences such as ``It was a wumpus.''
%% \end{exercise}

%\begin{exercise}
%Here is a regular\index{regular expression} expression for numbers in certain programming languages:
%\[ [+|-] \J{Digit}^* [ . \J{Digit}^* ] [\bnft{E} [+ | -] \J{Digit}^* ] \]
%\begin{enumerate}
%\item Write a context-free grammar for {\mathdelim}\bnf{Number}{\mathdelim}.
%\item Write a regular grammar for {\mathdelim}\bnf{Number}{\mathdelim}.
%\item Draw a finite-state machine diagram for {\mathdelim}\bnf{Number}{\mathdelim}.  This consists
%of states, with arcs between states labeled by terminal symbols.  One state
%is designated the start state, and any number of states can be accept states.
%(An example is shown in \figref{a+b+-figure}.)
%\end{enumerate}
%\end{exercise}
%
%\begin{figure}[ht]
%\epsfxsize=3in
%\figboxnew{figures/a+b+.eps}
%\caption{A finite-state machine for the language {\mathdelim}a^+b^+{\mathdelim}, with the accept
%state denoted by a double circle.}
%\label{a+b+-figure}
%\end{figure}

% \begin{exercise}\prgex
% This exercise continues the example of
% \secref{communicating-agent-section} by making the slave more
% intelligent.  On each turn, the slave describes its percepts as
% before, but it also says where it is (e.g., ``I am in 1,1'') and
% reports any relevant facts it has deduced about the neighboring
% squares (e.g., ``There is a pit in 1,2'' or ``2,1 is safe'').  You
% need not do any fancy language generation, but you do have to
% address the intention problem: deciding which facts are worth
% mentioning.  In addition, you should give your slave a sense of
% self-preservation.  If it is commanded to enter a deadly square, it
% should politely refuse.  If commanded to enter an unsafe square, it
% can ask for confirmation, but if commanded again, it should obey.  Run
% this slave in the wumpus environment a few times and comment on how useful it is.
% \end{exercise}


%% \begin{exercise}
%% Implement a version of the chart-parsing algorithm that returns a packed tree of all
%% edges that span the entire input.
%% \end{exercise}

%% \begin{exercise}
%% Implement a version of the chart-parsing algorithm that returns a packed\index{packed tree} tree for the
%% longest leftmost edge, and then if that edge does not span the whole input,
%% continues the parse from the end of that edge.  Show why you will need to call
%% \prog{Predict} before continuing.  The final result is a list of packed trees
%% such that the list as a whole spans the input.
%% \end{exercise}


%% \begin{exercise}
%% \label{coherence-parse-exercise}
%% Draw a discourse parse tree for the 
%% story on \pgref{fancy-restaurant-page} about John going to a fancy restaurant.
%% Use to the two grammar rules
%% for \bnf{Segment}, giving the proper \(\J{CoherenceRelation}\) for each node.
%% (You needn't show the parse for individual sentences.)
%% Now do the same for a 5 to 10--sentence discourse of your choosing.
%% \end{exercise}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%% \begin{exercise}\label{tomato-triphone-exercise}
%% The model of ``tomato'' in \figref{sr-tomato-figure} allows for a
%% coarticulation on the first vowel by giving two possible phones.  An
%% alternative approach is to use a triphone model in which the [ow(t,m)]
%% phone automatically includes the change in vowel sound. Draw a
%% complete triphone model for ``tomato,'' including the dialect
%% variation.
%% \end{exercise}

\begin{exercise}
We forgot to mention that the text in
\exref{washing-clothes-exercise} is entitled ``Washing\index{washing clothes} Clothes.''  Reread
the text and answer the questions in \exref{washing-clothes2-exercise}.  Did
you do better this time?  Bransford and
Johnson~\citeyear{Bransford+Johnson:1973} used this text in a 
controlled experiment and found that the title helped significantly.
What does this tell you about how language and memory works?
\end{exercise} 
% id=23.13 section=23.4


\resetmedskipamount