G7400 F'12
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9
Set 10

Problem Set 1: Basic Programming

Due date: 9/14 @ at the beginning of class

Purpose: The goal of this problem set is to demonstrate basic competence in the prerequisites of this course and the PhD program in general (solid programming skills in a programming language, a basic understanding of regular expressions or (equivalently) finite state machines.)

Task Design a program that discovers whether a user presses a sequence of alphanumeric keys according to some regular expression or finite state machine. Running the program on the specification of a regular expression should open a 100 x 100 window and accept key events. The window should be white for the initial state, yellow for intermediate states (not initial, not final), green when the sequence is an acceptable string (final state), and red when a mismatch has been discovered. As soon as the sequence of key events satisfies the given regular expression, the program should shut down with a positive acknowledgment. Conversely, the program should stop with a negative acknowledgment when a key event violates the given specification.

Example Assume that the specified regular expression is equivalent to

Then (1) key sequences such as "abbbcd" and "ad" are accepted, (2) key sequences such as "b" and "d" are unacceptable, and (3) key sequences such as "abc" and "abbb" are strict prefixes.

Configuration The program is configured with a "program" in a domain-specific programming language (DSL) for the specification of finite state machines (FSM). Your program should read the specification from a file whose path is given the command line.

To keep the specification programming-language neutral, the DSL is a dialect of XML (eXtensible Markup Language). Here is the formal grammar:

    FSM = <fsm initial=State>
	     <final label=State></final> ...1
	     <transition current=State next=State>
		<action key=AlphaNumeric></action> ...1
	     </transition> ...1

    State = String 
    AlphaNumeric = the one-char strings 'a' thru 'z', 'A' thru 'Z', and '0' thru '9'
The notation ...1 means "a sequence of at least one of the preceding XML elements".

Informally, a FSM specification consists of a single XML element that specifies the initial state via an "initial" attribute; the final states and transition between states are listed as the content of the elements, i.e., as sequences of elements. The "final" XML element just names the "accepting" states of the FSM. Each transition element specifies the origin and destination states via attributes and the alphanumeric keys that enable the transition as a sequence of content elements.

Here are two sample specifications for a(b|c)*d:
    <fsm initial="a">
       <final label="d"></final>
       <transition current="a" next="bc">
          <action key="a"></action>
       <transition current="bc" next="bc">
          <action key="b"></action>
          <action key="c"></action>
       <transition current="bc" next="d">
         <action key="d"></action>
    <fsm initial="a">
       <final label="d" />
       <transition current="a" next="bc">
          <action key="a" />
       <transition current="bc" next="bc">
          <action key="b" />
          <action key="c" />
       <transition current="bc" next="d">
         <action key="d" />
Your program should print a reasonably informative, one-line error message if anything goes wrong with the configuration step.

Deliverable Send in a tar.gz bundle via email that contains a single directory. When I unpack the bundle on the standard departmental LINUX boxes (login-linux is a good example), I expect to be able to cd into this directory and run your solution as
  $ ./1.xyz 1.xml
where 1.xml is a file I will supply.

last updated on Wed Nov 7 10:09:15 EST 2012generated with Racket