CS 451 --- Fall 2002 --- Assignment Three


	==============================================
	There's nothing remarkable about it.  
	All one has to do is hit the right keys at the 
	right time and the instrument plays itself.
               -- J.S. Bach

	==============================================


		NATURAL LANGUAGE PARSER


			   Finger Exercises

Define flip_alternates/2, with signature flip_alternates(-,-), which
is satisfied by two lists each with an even number of elements where
the elements at positions 2i and 2i+1 are in positions 2i+1 and 2i in
the other.  Examples:
 flip_alternates([],[])
 flip_alternates([a,b,foo(c),d], [b,a,d,foo(c)])



Define colored/3 which is satisfied when given a correctly colored
graph (ie in which no adjacent vertices have the same color), as
 - a (simple undirected) graph represented as a list of vertices and
   an adjacency list (as shown)
 - a list of valid colors
 - a coloring, in the same order as the vertex list
For extra credit, make the signature (+,+,-).  Examples:

 colored( g( [a,b,c,d], [v(a,b), v(b,d), v(c,a), v(c,d)] ),
	  [red, green, blue],
	  [red, green, green, blue] )

 colored( g( [a,b,c,d], [v(a,b), v(b,d), v(c,a), v(c,d)] ),
	  [black, white],
	  [black, white, white, black] )

 colored( g( [a,b,c,d], [v(a,b), v(b,d), v(c,a), v(c,d)] ),
	  [black, white],
	  [white, black, black, white] )

 colored( g( [a,b,c,d,e,f], [v(a,b), v(b,d), v(c,a), v(c,d)] ),
	  [black, white],
	  [white, black, black, white, white, white] )

 colored( g( [a,b,c,d,e], [v(a,b), v(b,d), v(c,a), v(c,d)] ),
	  [black, white],
	  X )
  X=[white, black, black, white, white]
  X=[white, black, black, white, black]
  X=[black, white, white, black, white]
  X=[black, white, white, black, black]

			     Main Problem

Starting with the Recursive Descent Parser from Section 14.9.2 (pages
666-670) in the handout from Dr. George Luger's book "Artificial
Intelligence - Structures and Strategies for Complex Problem Solving,"
introduce predicates and Prolog Rules for including Adjectives,
Prepositions and Conjunction into the grammar.  Maintain context
sensitivity as much as possible.

----------------------------------------------------------------

Due noon, Wed Oct 16.

Please comment reasonably.  Points for readability and conciseness.

Hand your code in by running the script
 ~bap/bin/hw-handin your-cs451-hw.scm
on a CS machine.  It will generate a time stamp which you should save.