Appendix A: Hints and Partial Solutions to Selected Exercises

Exercise 2.13. Hint: Use trace on recognize_next to spot when a state in the search space keeps repeating. Look to see which node in the network this state involves and reorder the arcs coming from this node so that another one is chosen first.

Exercise 2.15. A solution to this exercise is presented in lib bubrecog.

Exercise 2.16. Hint: Include in the representation of a state in the search space the list of nodes that have been visited previously. Thus redefine recognize_next to be of the form:

define recognize_next(node,tape,network,visited_previously);

 ...

When recognize_next is called recursively, the recursive call needs to be given a list the same as the original call, except that the current node is added to the front. When a final state is encountered, an appropriate list of nodes can be returned, instead of true. It does not matter if the list of nodes visited comes out in reverse order.

Exercise 2.25.

Hint: In order for your network to "remember" the first character to produce it at the end of the second tape, the nodes that a traversal passes through must be different for each possible value of the first character. Thus the network will consist of many pieces of network like the following:

From 1 to 212 by a_h

From 212 to 213 by ^_^

From 213 to 2 by h_a

Exercise 2.28. A solution to this exercise is presented in lib fstgen.

Exercise 2.29.

Here is a sketch of how one might argue. Imagine a FSTN that can recognize precisely the strings in the language a\un\db\un\d. Since this network can accept any number of initial as but the network itself only has a finite number of nodes, there must be at least one cycle in the network that accepts a sequence of m as, where m is greater than 0. Moreover, for any n sufficiently large, the recognition of a\un\db\un\d must involve the traversal of such a cycle. Let N be such a value and M be the length of one such cycle that is traversed. Then there is a traversal of the network that is just like the traversal for a\uN\db\uN\d, except that the cycle is traversed one more time. This traversal accepts the string a\uN+M\db\uN\d, which is not in the desired language. This contradicts the original assumption. Therefore such a FSTN cannot exist.

Exercise 3.4.

Hint: You need to argue that at each stage a selected state only leads to a finite number of next states and that it is not possible for a state to lead to a state that leads to a state ... and so on for ever. Therefore if a given state is not immediately selected, then it will nevertheless eventually be selected, even if we have to wait until all the other alternatives, and the states that follow from them, have been exhausted.

Exercise 3.12. A solution to this exercise is presented in lib pdtransd.

Exercise 3.13.

Hint: A string is of the form a\un\db\un\d if it is empty or if it consists of an a, followed by a string of this form, followed by a b.

Exercise 3.14.

If there is no VP network, then it is not possible for networks to talk about VPs as constituents. For instance, it is hard to express the fact that VPs can be conjoined ("took over the company and sacked the directors") and that certain verbs subcategorize for VPs ("threatened to take over the company").

Exercise 3.16.

Hint: In order to associate the right NP with the right "hole", it is necessary to have the hold register be a stack. The only element that can be used to fill a hole is then the last element that was "pushed" onto the register. This ensures that in the second example Hanni is seen to have erased the tape, rather than the man. Previous tests that the hold register be empty in various places now have to be appropriately modified.

Exercise 3.17. The extended ATN is presented in lib atnarcs2.

Exercise 4.2.

Hint: For a rule like "A -> B C D" you can introduce arcs like the following in a network named A:

Initial 1

Final 10

From 1 to 2 by B

From 2 to 3 by C

From 3 to 10 by D

Exercise 4.4.

Hint: Here is one possible approach. You will need to create a new category for each cycle in a network. The rules for this category consist of one rule which corresponds to going round the cycle and one rule which has an empty RHS. For each path through a network (from an initial node to a final node) which doesn't go round a cycle you can create a rule for the category named by the network, simply spelling out the sequence of arc labels encountered. Finally, wherever such a path goes through a node which is on a cycle you need to splice into the rule an occurrence of the category created to represent that cycle. This procedure, whilst correct, does not result in optimal rule sets.

Exercise 4.8.

Hint: Does the grammar allow a whole sentence to be topicalized, with the remaining S/S being simply the empty string?

Exercise 4.12.

Hint: Consider VPs like "I handed Dr Chan donations", "I bet Dr Chan thousands patients had recovered".

Exercise 4.13.

Hint: If a mother category has a non-0 slash, how many of the daughters will also have a non-0 slash?

Exercise 4.20.

Hint: You will need to introduce rules rather like the following:

NP -> Det N S

  <S slash> = NP.

Exercise 4.23. A solution to this exercise is presented in lib featexp.

Exercise 5.2.

Hint: This problem is described in Hopcroft and Ullman (1979), section 4.4. The basic idea is, firstly, to determine the set of categories which can be realised by the empty string (the "nullable" categories). Any category which has a rule with an empty RHS is obviously a nullable category. Similarly any category with a rule, all of whose RHS categories are nullable, is nullable. Secondly, we construct the new grammar out of all the rules with non-empty RHSs that can be derived by deleting zero or more nullable categories from the RHS of rules in the original grammar.

Exercise 5.5. A solution to this exercise is presented in lib buparse1.

Exercise 5.6. A solution to this exercise is presented in lib buparse2.

Exercise 5.7.

Hint: The basic idea is to replace a pair of rules like "A -> A B" and "A -> C" by the rules "A -> C Z", "Z -> " and "Z -> B Z". Variations on this theme can eliminate rules of the form "A -> A B ...", but will not handle indirect left recursion in cases like "A -> B C", "B -> A D". Aho and Ullman (1972, Vol 1, section 2.4.4) present a general algorithm.

Exercise 6.1. Here is probably the simplest way to change lib tdparse to use a WFST. Whenever the procedure find_trees produces a result, it also adds to the Pop11 database a fact of the form:

[found ^goal ^string ^list_of_results]

This database now serves as a primitive WFST, recording the successful results of previous parsing attempts (even though it uses a representation that does not facilitate rapid retrieval by indexing on the position in the input). The start of find_trees now needs to be altered to consult this table:

define find_trees(goal,string);

   vars cat rule rhs s trees remainder results;

   if present([found ^goal ^string ?results] then

      results

   elseif goal matches [?cat] then

   ...

Exercise 6.3.

If the grammar contains e-productions, then the WFST graph needs to include arcs which start and finish at the same point in the input, i.e. it needs to allow certain simple cycles.

Exercise 6.7.

Hint: If the grammar has the rule "A -> A", as well as other rules for A, then it assigns infinitely many different analyses to any phrase of type A. If a chart parser as described considers edges to be different if they include different parse trees, then it should get into an infinite loop with such a grammar. A similar problem will arise with "A -> B A" if B can be realised as the empty string. One could argue that natural language grammars are not (should not be?) of this form. Otherwise one solution might be to run a chart recognizer and then, somehow, reconstruct just as many different parse trees as one wanted.

Exercise 7.9. Hint: You will find that the program sometimes seems to get involved in a very long computation without returning an answer in reasonable time. Use trace to see what sorts of phrases it is trying to generate. Having found out when the problem arises, use the interactive version of oneof to help the program avoid these problems. On the basis of the sentences that you can then generate, comment on the deficiencies of the grammar.

Exercise 7.10. A solution to this exercise is presented in lib randftre.

Exercise 7.14.

See Shieber's (1985c) mentioned in the Further Reading section.

Exercise 7.18.

Hint: One way is to encode in sequence the restrictions that a verb makes on the phrases that follow it and then the restrictions it makes on its subject. Thus the following entry:

Lexeme persuade:

   <cat> = V

   <subcat first cat> = NP

   <subcat first case> = non_subject

   <subcat rest first cat> = VP

   <subcat rest rest first cat> = NP

   <subcat rest rest first case> = subject

   <subcat rest rest rest> = NIL.

Rule VP -> V:

   <VP subcat> = <V subcat>.



Rule VP1 -> VP2 X:

   <VP2 subcat first> = X

   <VP1 subcat> = <VP2 subcat rest>.

Exercises 7.21, 7.22. Solutions to these exercises are presented in lib lexicon.

Exercise 8.2. Here are some of the rules that you might employ:

Rule number -> less_than_1000.

Rule number -> less_than_1000 thousand less_than_1000.

Rule less_than_1000 -> digit hundred.



Word two: <cat> = digit.

Word thousand: <cat> = thousand.

define interpret_number(tree);

   if tree matches [number [less_than_1000 ==]] then

      interpret_less_than_1000(tree(2))

   elseif tree matches

    [number [less_than_1000 ==] [thousand ==] [less_than_1000 ==]] then

      1000*interpret_less_than_1000(tree(2))

      + interpret_less_than_1000(tree(4))

   ...

enddefine;

Exercise 8.3. Of course, the shape of your program will depend on the output language that you choose. If you choose English (using the grammar above), then part of the program might look like the following:

define generate_number(tree);

   ...

   if tree matches [= = =] then

      [number ^(generate_less_than_1000(tree))]

   elseif tree matches [??thousands ?h ?t ?u] and thousands /= [] then

      [number

       ^(generate_less_than_1000(thousands))

       [thousand thousand]

       ^(generate_less_than_1000([^h ^t ^u]))

      ]

   ...

Exercise 9.1. Hint: Here is the value of dag_patterns that you will need:

[

 [predicate arg0 arg1 arg2]

 [predicate arg0 arg1]

 [predicate arg0]

 [predicate]

 [connective prop1 prop2]

 [[cat IMP] *sem *pre]

 [[cat V] *subcat *p *arg1 *arg2 *sem *pre]

 [[cat PP] *p *arg0 *arg1 *p_pre *np_pre]

 [[cat NP] *pre *referent]

 [[cat N] *pre *referent]

 [[cat P] *p *pre *arg0 *arg1]

 [[cat DET]]

] -> dag_patterns;

Exercise 9.4.

A solution to this sort of problem is discussed in Kaplan (1983).

Exercise 9.9. Here are the inference rules for the grammar corresponding to Grammar1 of Chapter 4:

[

[[S _s1 _s3] [NP _s1 _s2] [VP _s2 _s3]]

[[VP _s1 _s3] [V _s1 _s2] [NP _s2 _s3]]

[[VP _s1 _s2] [V _s1 _s2]]

[[NP [Dr [Chan _s]] _s]]

[[NP [nurses _s] _s]]

[[NP [MediCenter _s] _s]]

[[NP [patients _s] _s]]

[[V [died _s] _s]]

[[V [employed _s] _s]]

] -> infrules;

With these rules, try doing the following:

for s in back_infer([S _s []]) do apply_subst(s,"_s") ==> endfor;

Exercise 9.10. Here is how the above inference rules could be modified to build parse trees:

[

[[S [S _nptree _vptree] _s1 _s3] [NP _nptree _s1 _s2] [VP _vptree _s2 _s3]]

[[VP [VP _vtree _nptree] _s1 _s3] [V _vtree _s1 _s2] [NP _nptree _s2 _s3]]

[[VP [VP _vtree] _s1 _s2] [V _vtree _s1 _s2]]

[[NP [NP Dr Chan] [Dr [Chan _s]] _s]]

[[NP [NP nurses] [nurses _s] _s]]

[[NP [NP MediCenter] [MediCenter _s] _s]]

[[NP [NP patients] [patients _s] _s]]

[[V [V died] [died _s] _s]]

[[V [V employed] [employed _s] _s]]

] -> infrules;

With these rules, try doing the following:

for s in back_infer([S _tree [Dr [Chan [employed [nurses []]]]] []]) do

   apply_subst(s,"_tree") ==>

endfor;

Exercise 10.13. For the first example, here are the inference rules and the desired call to plan:

[ [[channel sue alan]]

  [[at alan inside]]

  [[at sue inside]]

] -> infrules;



plan("sue",[[at alan outside]]) ==>

Here are the same for the new example:

[

 [[channel sue alan]]

 [[channel alan sue]]

 [[channel alan ann]]

 [[channel ann alan]]

 [[knows_ref ann combination]]

] -> infrules;



plan("sue",[[knows_ref sue combination]]) ==>

Send us a comment.