\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

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

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Artificial Intelligence -- 
6.034 Problem Set \psnum \\ Juliet Bourne -- Section R1 -- #1} \\ 
\vspace{-.1in}
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.034 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{10/12/90}

\prob{1}

\subprob{A} Here is the code for the transition tree grammar described
in Chapter 3B:

\begin{verbatim}
(define-tree interface
  (brnchs
   (count > objects if-end-rtn 
     (db-call `(db-count ,objects)))
   (how many > objects are there if-end-rtn 
     (db-call `(db-count ,objects)))
   (identify the > attributes of > objects if-end-rtn
     (db-call `(db-show (db-project ,objects over ,@attributes))))
   (identify > objects if-end-rtn (db-call `(db-show ,objects)))))

(define-tree attributes
  (brnchs (> attribute > attributes rtn (cons attribute
                                              attributes))
          (and > attribute          rtn (list attribute))
          (> attribute              rtn (list attribute))))

(define-tree attribute
  (brnchs (class        rtn 'class)
          (classes      rtn 'class)	;added.
          (color        rtn 'color)
          (colors       rtn 'color)	;added.
          (size         rtn 'size)
          (sizes        rtn 'size)	;added.
          (weight       rtn 'weight)
          (weights      rtn 'weight)))	;added.

(define-tree attribute-values
  (brnchs (> attribute-value > attribute-values
             rtn (append attribute-value attribute-values))
          (and > attribute-value rtn attribute-value)
          (> attribute-value rtn attribute-value)))

(define-tree attribute-value
  (brnchs (large        rtn '(size eql large))
          (medium       rtn '(size eql medium))
          (small        rtn '(size eql small))
          (long         rtn '(size eql long))
          (short        rtn '(size eql short))
          (black        rtn '(color eql black))
          (blue         rtn '(color eql blue))
          (red          rtn '(color eql red))
          (yellow       rtn '(color eql yellow))
\end{verbatim}

\mynewpage

\begin{verbatim}
          (gray         rtn '(color eql gray))
          (heavy        rtn '(weight eql heavy))
          (light        rtn '(weight eql light))))

(define-tree objects
  (brnchs (> determiner > objects rtn objects)
	  (> object rtn object)
          (> attribute-values > object 
	     rtn `(db-select ,object with ,@attribute-values))))

(define-tree determiner
  (brnchs (a) (the)))

(define-tree object
  (brnchs (tool         rtn 'tools)
	  (tools        rtn 'tools)
	  (saw          rtn '(db-select tools with class eql saw))
          (saws         rtn '(db-select tools with class eql saw))
          (hammer       rtn '(db-select tools with class eql hammer))
          (hammers      rtn '(db-select tools with class eql hammer))
          (wrench       rtn '(db-select tools with class eql wrench))
          (wrenches     rtn '(db-select tools with class eql wrench))
          (screwdriver  rtn '(db-select tools with class eql screwdriver))
          (screwdrivers rtn '(db-select tools with class eql screwdriver))))
\end{verbatim}

Here is the output on the example sentences:

\begin{verbatim}
SENTENCE>Count the red screwdrivers.
2
SENTENCE>Identify the size and weight of the red screwdrivers.
| SIZE  | WEIGHT |
| ----- | ------ |
| LONG  | HEAVY  |
| SHORT | LIGHT  |
SENTENCE>Identify the size of the heavy red screwdriver.
| SIZE |
| ---- |
| LONG |
\end{verbatim}

\subprob{B} The code for the modified grammar involves modification of
two transition trees, interface and objects. In interface, the branch
beginning {\bf (what $>$ attributes ... )} is added. In objects, two
branches are added. The order in which these branches are added is
important. If the more specific branches are not placed before similar but
less specific ones, the interface won't proceed past the general case
and it will fail on the general case since it hasn't reached the end
of the sentence.

\mynewpage

\begin{verbatim}
(define-tree interface
  (brnchs
   (count > objects if-end-rtn 
     (db-call `(db-count ,objects)))
   (how many > objects are there if-end-rtn 
     (db-call `(db-count ,objects)))
   (what > attributes are > objects if-end-rtn 
     (db-call `(db-show (db-project ,objects over ,@attributes))))
   (identify the > attributes of > objects if-end-rtn
     (db-call `(db-show (db-project ,objects over ,@attributes))))
   (identify > objects if-end-rtn (db-call `(db-show ,objects)))))

(define-tree objects
  (brnchs (> determiner > objects rtn objects)
	  (> object and > objects rtn `(db-union ,object ,objects))
	  (> object rtn object)
	  (> attribute-values > object and > objects
	     rtn `(db-union (db-select ,object with ,@attribute-values) 
		   ,objects))
          (> attribute-values > object 
	     rtn `(db-select ,object with ,@attribute-values))))
\end{verbatim}

The output is as follows:

\begin{verbatim}
SENTENCE>What sizes are the red screwdrivers.
| SIZE  |
| ----- |
| LONG  |
| SHORT |
SENTENCE>Identify the size and weight of the red screwdrivers and the
blue hammers.
| SIZE  | WEIGHT |
| ----- | ------ |
| LONG  | HEAVY  |
| SHORT | LIGHT  |
| LARGE | HEAVY  |
SENTENCE>Identify the color and weight of the hammers and the red screwdrivers.
| COLOR | WEIGHT |
| ----- | ------ |
| BLUE  | HEAVY  |
| RED   | HEAVY  |
| RED   | LIGHT  |
SENTENCE>Identify the screwdrivers and the saws.
| CLASS       | COLOR | SIZE   | WEIGHT |
| ----------- | ----- | ------ | ------ |
| SCREWDRIVER | BLUE  | LONG   | LIGHT  |
| SCREWDRIVER | BLACK | LONG   | LIGHT  |
\end{verbatim}

\mynewpage

\begin{verbatim}
| SCREWDRIVER | RED   | LONG   | HEAVY  |
| SCREWDRIVER | RED   | SHORT  | LIGHT  |
| SAW         | BLACK | MEDIUM | HEAVY  |
\end{verbatim}

\prob{2}

\subprob{A}

\vspace{4in}

\subprob{B}

\vspace{4in}

\end{document}
