Work the following problems; we will review on Wed

1.     Give the type of the following functions/expressions:
   
   
   fun fribble g x y = g(x,y);
   
   
   fun frubble a b = (a+b,a-b);
   
   
   fun zappit f [] = [] |
       zappit f (a::b) = (f a)::(zappit f b);
   

2.     Write an ML implementation of the following ML signature:
   
   signature ZOSE = sig
      type 'a zat
      val zem:  'a zat
      fun zip: 'a -> 'a zat -> 'a zat
      fun zop: 'a zat -> 'a
      fun zest: 'a zat -> 'a zat
   end
   
   
   it should be the case that:
   zop(zem) = ERROR
   zop(zip a x) = a
   zest(zem) = zem
   zest(zip a x) = x
     

3.     For the grammar:
   
   S -> Saab |  aaSb  |   aabS  | baa
   
   which of the following are valid sentences:
   
   a) aabbaa
   b) baabaa
   c) aaaaaabbb
   d) aaabbb
     

4.     Demonstrate the following grammar is ambiguous:
   
       E ->  E + E |  E * E | E -E | x | y | z
     

5. Implement the function sorted: (('a,'a) -> bool) -> 'a list -> bool which applies it's first argument (the function) to each pair pf consecutive items in the list; and returns true if the function returns true for each consecutive pair.

6. Assume we have a database of prolog statements of the following format:  (actor, movie, year); here are a few samples:
   (kevin bacon, animal house, 1978)
   (kevin bacon, diner, 1982)
   (kevin bacon, footloose, 1984)
   
   
   Write the prolog statement to determine "three degrees of Kevin Bacon";
   that is to check whether, for a given actor, there is a pair of other
   (distinct) actors who co-starred in some movie, such that one of those
   actors co-starred with Kevin Bacon, and the other co-starred with the
   "given" actor (in a third distinct movie).
         

7. 	Write the prolog function which will delete the first instance of an element from a list.
   
   	delete1st(7,[1,7,3,7],[1,3,7)  would yield true
   	delete1st(5,[2,3,5,5], Y) would yield Y|[2,3,5]
         

8.  Convert EBNF -> BNF
   
   	Blist -> { var (^ | \/ | => \) } var
   

9. 	  Write the regular expressions:
   
   For 8 digit (year,month,day) dates:
   20250304 is valid
   20251313 is not valid
   19880734 is not valid
   20250219 is valid
   19991231 is valid

10. 	  Write the grammar such that, every string contains only a and/or b:
    
    And, no "b" occurs before any "a"