This problem set concerns the following grammar $($ S is the start symbol$)$:

NOTE: when a phrasal category $($XP or XB$)$ has more than one rule for re$-$writing it$,$ consider the rules in the order that they are listed.

$-$ For VB$,$ first try VB $\backslash (\backslash$rightarrow $\backslash$mathrm$\{$V$\}$ D P $\backslash ),$ then $\backslash (\backslash$mathrm$\{$VB$\}\backslash$rightarrow $\backslash$mathrm$\{$VCP$\}\backslash ).$

$-$ For NP$,$ first try NP $\backslash (\backslash$rightarrow $\backslash$mathrm$\{$N$\}\backslash ),$ then NP $\backslash (\backslash$rightarrow $\backslash$mathrm$\{$N$\}$ P $\backslash$mathrm$\{$P$\}\backslash ).$

Be sure to indicate at the end whether parsing succeeded or failed!

If you reach a successful parse, you do not need to keep looking for other possible parses.

Problem $1(17$ points$)$

Apply the top down parsing algorithm to the sentence "the hunter saw a rabbit fool a duck in the woods". Show the step$-$by$-$step operation using the table format shown in the lectures and handout.

Problem $2(3$ points$)$

Show the parse tree $($or partial tree$)$ corresponding to the state of parsing when the algorithm has finished. If parsing succeeded, this will be the grammatical tree for the successful parse. If parsing failed, it will be the partial $($non$-$grammatical$)$ tree representing what the algorithm had built $($what it was working on$)$ at the last time it tried to backtrack. Please generate a tree diagram $($using jsSyntaxTree or some similar tool$)$ and include the image in your work.