Exercise Chapter 8.1

1. 
   

    
    [the,clever,boy,buys,a,sweet]
   
    [the,clever,sweet,buys,a,clever,clever,boy]
   
   (etcetera)
   
   

   These are legitimate inputs produced by the query

    
   ?- s([the,clever,boy,buys,a,sweet],[]).
   
   ?- s([the,clever,sweet,buys,a,clever,clever,boy],[]).
   
   (etcetera)
   
   

   It is not so immediately apparent that this grammar can generate sentences as well. What is the order in which sentences are generated?

    
   [a,boy,buys,a,boy]
   
   [a,boy,buys,a,sweet]
   
   [a,boy,buys,the,boy]
   
   [a,boy,buys,the,sweet]
   
   [a,boy,buys,a,clever,boy]
   
   [a,boy,buys,a,clever,sweet]
   
   [a,boy,buys,a,clever,clever,boy]
   
   [a,boy,buys,a,clever,clever,sweet]
   
   [a,boy,buys,a,clever,clever,clever,boy]
   
   (and so on)
   
   

2. Here is just one example ---there are various ways of doing this.

    
   s(sentence(NP-VP))		  --> 		 np(NP),
   
   		  		 		 vp(VP).
   
   np(nounphrase(Det-N))		  --> 		 det(Det),
   
   						 noun(N).
   
   np(nounphrase(Det-Adjs-N))	  --> 	         det(Det),
   
   						 adjs(Adjs),
   
   						 noun(N).
   
   vp(verbphrase(V-NP))		  --> 		 verb(V),
   
   						 np(NP).
   
   det(determiner(a))		  --> 		 [a].
   
   det(determiner(the))		  --> 		 [the].
   
   adjs(adjectives(Adj))		  --> 	         adj(Adj).
   
   adjs(adjectives(Adj-Adjs))	  --> 	         adj(Adj),
   
   						 adjs(Adjs).
   
   adj(adjective(clever))		  --> 		 [clever].
   
   noun(noun(boy))		  	  --> 		 [boy].
   
   noun(noun(sweet))		  --> 		 [sweet].
   
   verb(verb(buys))		  --> 		 [buys].
   
   

   which produces (in a much less readable form than the following):

    
   X = sentence(
   
   		 nounphrase(
   
   			 	determiner(a)
   
   				-
   
   				adjectives(adjective(clever))
   
   				-
   
   				noun(boy))
   
   		 -
   
   		 verbphrase(
   
   				verb(buys)
   
   				-
   
   				nounphrase(
   
   						determiner(a)
   
   						-
   
   						adjectives(adjective(clever)-adjectives(adjective(clever)))
   
   						-
   
   						noun(boy))))
   
   

3. This is very hard to do in general. The issue here is one of `robust parsing' and it is a major research topic. Consequently, there is no complete answer but a first attempt might look like:

    
   s(sentence(NP-VP))  		            --> 		 np(NP),
   
   				                            	 vp(VP).
   
   np(nounphrase(Det-N)) 		          --> 		 	 det(Det),
   
   				                            	 noun(N).
   
   np(nounphrase(Det-Adjs-N))   		   --> 			 det(Det),
   
   				                                 adjs(Adjs),
   
   				                                 noun(N).
   
   vp(verbphrase(V-NP))       		     --> 		 verb(V),
   
   				                                 np(NP).
   
   det(determiner(a)) 		             --> 		 [a].
   
   det(determiner(the)) 		           --> 		 	 [the].
   
   det(unknown_det(X))  		           --> 		 	 [X],
   
   				                                 {\+(known(X))}.
   
   adjs(adjectives(Adj))   		        --> 		 adj(Adj).
   
   adjs(adjectives(A-Adjs)) 		       --> 		 adj(A),
   
   				                                 adjs(Adjs).
   
   adj(adjective(clever)) 		         --> 		 	 [clever].
   
   adj(unknown_adj(X))         		    --> 		 [X],
   
   		                                    		 {\+(known(X))}.
   
   noun(noun(boy))  		               --> 		 [boy].
   
   noun(noun(sweet)) 		               --> 		 [sweet].
   
   noun(unknown_noun(X))  		         --> 		 	 [X],
   
   				                                 {\+(known(X))}.
   
   verb(verb(buys))		                --> 		 [buys].
   
   verb(unknown_verb(X))  		         --> 		 	 [X],
   
   				                                 {\+(known(X))}.
   
   known(X):-noun(noun(X),_,_).
   
   known(X):-verb(verb(X),_,_).
   
   known(X):-det(determiner(X),_,_).
   
   known(X):-adj(adjective(X),_,_).
   
   

   Some points to note:
   1. It cannot cope with missing words so this goal fails badly. We could try to extend it to meet this problem. For example, we might like the following query to succeed:

       
      s(X,[the,clever,buys,a,sweet],[]).
      
      

   2. It does cope quite well with more than one misspelling provided the sentence structure is acceptable ---as in the query:

       
      s(X,[the,clever,silly,buoy,buys,a,sweet],[]).
      
      

   3. The known/1 predicate is not at all clever.