Homework 4

Due: Monday Oct 21 2002

Problem 1: Game Show [50 pts]

Congratulations. You have just reached the final round of the game show "The Winner Takes It All". All you have to do is to decide is if the order of a line up of items that is presented to you on a conveyer belt follows certain rules. The show master has already acquainted you with them ahead of time (they may vary from game to game) and you are very lucky today! There are only two rules he asked you to memorize.

Before the game starts for real, there are three practice rounds. Item by item is presented before you, and you have 30 seconds after you have seen all of them to decide if you can justify the order in which they occurred using these two rules.

Test Round 1:

The conveyer belt starts rolling and you see 
 V K V E T
Quickly you see, that sure, that's ok, because the first V and K satisfy two of the tree requirements of rule 1. Note that rule 1 is not fully applied yet, because there must be at least one entertainment item among the remaining articles. The next V is valid by rule 2, then comes E which justifies the application of rule 1. And the final item T justifies the second rule. If this were the real game and not just a practice round, you should have said YES!.

Test Round 2:

The conveyer belt starts rolling and you see 
 V V T
As you can quickly see, this order of articles cannot be justified by the two rules from above. You should say NO, and the car, the bike, and the trip to Cancun would have been yours.

Test Round 3:

The conveyer belt starts rolling and you see 

 V K V E K E
Also this is a valid order, because it is justified by rule 1 (two applications) .

Back to the homework! Please solve this problem for the general case by writing a Haskell program which decides for you if to say yes or no. 

      type Rule = [Char]
      play :: [Rule] -> String -> Bool
I am sure, that your solution will return an answer in less time than 30 seconds. You can assume that the rules are formalized as lists of characters [Char], and the items of the conveyer belt are presented to you as a String.

Hint: Try to adopt and modify the code for matching regular expressions in class. Do not write more than 40 lines of code! If you do, something is likely to be wrong, or you haven't found an elegant solution.

Problem 2: Adding Negation to Regular Expressions [extra credit 20 pts]

With this problem we return to the world of algorithms that match regular expressions. In class we have discussed the standard set of operators of regular expressions, and we have discussed an algorithm that decides if a string is matched by a regular expression our not. You are asked to extend the regular expression language by a new constructors that can express negation. 

  acc  "00" (Not (Star (Char "1"))) init
should succeed, because 00 is not an element of Star (Char "1").

To solve this problem we extend the data type Reg by the new constructor Not: 
  data Reg 
    = Zero
    | One
    | Char Char
    | Plus Reg Reg
    | Times Reg Reg
    | Star Reg
    | Not Reg
  deriving Show
Mathematically, the language generated by this language is defined as 
  L(Not R)  = {s | s is not an element of L(R)}
Please extend the acceptor for regular expressions accpresented in class to cover this new case.