Engr 692: Special Topics in Engineering Science
(Ruby and Software Development)
Fall 2006

Assignment #3
Due 5:00 p.m., Friday, 10 November 2006

Consider a domain-specific language (DSL) for defining deterministic finite state automata (i.e., machines). The language consists of the following kinds of statements:

• state :s1, :s2, ... defines one or more states of the finite state machine. Each argument (e.g., :s1) declares the name of a state. A machine description file may contain one or more state statements. The set of states for the machine consists of the union of the sets defined by all the state statements. The arguments of the state statement follow the Ruby syntax for symbols.

• initial :si declares its argument as the initial state for the finite state machine. Only one of these statements may occur in a machine description file.

• final :f1, :f2, ... declares that its arguments are included in the final, accepting states of the machine. There may be more than one of these in a machine description file. The set of final states is the union of the sets defined by all the final statements.

• alphabet str1, str2, str3... declares the input alphabet for the machine to contain the given strings. (The strings are quoted string literals as in Ruby and do not contain embedded white space characters.) Note that the input symbols of the machine's alphabet may be whole words, not just single character symbols. There may be more than one of these statements in a machine description file. The alphabet is the union of all the sets defined by all the alphabet statements.

• transition :s1, str, :s2 defines a mapping from state :s1 with input symbol str to the next state :s2 of the machine. There may be many transition statements in a machine description file. Collectively, these statements define the transition function for the machine. This mapping must uniquely map a specific state- symbol pair to a next state. That is, it must be deterministic.

• Comments on lines begin with # and continue to the end of the line. They do not change the definition of the machine in any way.

• Blank lines in the description file are ignored.

In general, a state name must be declared in a state statement before it is used in any of the other statements. Otherwise, the statements can occur in any order in the machine description file.

For example, consider the following machine description file for a simple finite state machine to accept an even number of occurrences of the string "one". It has two states, one of which is both the initial and the final state. It also has an input alphabet consisting of a single symbol, the string "one". The DSL file for the machine description is as follows:

state :even, :odd
initial :even
final :even
alphabet ["one"]
transition :even, "one", :odd
transition :odd, "one", :even

The above machine would accept the input sequences "", "one one", "one one one one", and so forth. It would reject the input sequences "one", "one one one", and so forth. An input sequence such as "one three" would be an error situation because the symbol "three" is not in the input alphabet for the machine.

Write a Ruby program that takes a machine description written in the above DSL and builds a deterministic finite state acceptor for the regular language so described. As we have seen in example programs in class, the program may either implement an internal DSL using Ruby or an external DSL using simple language processing techniques.

The program should write appropriate error messages in cases such as when a nondeterministic machine is defined or more than one initial state is given.

After construction of the acceptor, the program should take a DSL file (i.e., a text file with a machine description written in the DSL) and determine whether an input file (i.e., just another text file) satisfies the language description. The program should ignore white space (blanks, tabs, newlines) between symbols in the input file.

It should be possible to run the program in irb by calling it follows with two filenames as follows:

FSM.accept machine_description_filename input_file_name

Design appropriate tests for your program and execute them.

Document your Ruby code appropriately.

Turn in a printout of the Ruby program code, your test input files, and the output from your test runs. Also turn in an electronic copy of your program with the Ruby code in a file named FSMacceptor.rb.

Challenges:

After doing the basic program above, extend it in the following ways:

• Transform it into a framework library. In particular, we want to use this library to control workflow between different loosely coupled components of a larger program. For example, consider the workflow involved with processing of an application for the graduate program -- application, initial processing steps by Graduate School (when transcripts and test scores arrive independently), processing by International Programs if needed, processing by Graduate Coordinator and admissions committe in Department, final processing by Graduate School, etc. Each of these processing steps might be considered as states of a finite state machine.

• Make the input alphabet consist of events (or messages) that may carry data along with the event names.

• Attach actions to states and to transitions. For example, you may want an action that is called when a transition occurs from one state to another and/or an action that is called when the machine first arrives in a state.

UP to Engr 692 Assignments page?