CS 3800 Software

The following files comprise a DFA simulator with two examples:

• dfa.sps is the DFA simulator itself, as an R6 Scheme top-level program preceded by two local libraries.
• test1.dfa is an example of how a DFA is described to the simulator.
• test1.txt is an example of an input accepted by test1.dfa.
• test2.dfa is another example of a DFA.

The simulator can be run in Larceny or Petit Larceny as follows:

larceny --r6rs --program dfa.sps -- <machine> <input>

where <machine> is the name of a file containing a description of a DFA as specified by the grammar below, and <input> is the name of a file containing an input for the DFA. The <input> may be omitted, in which case the input is taken from standard input.

Example:

larceny --r6rs --program dfa.sps -- test1.dfa test1.txt

Although the simulator has been tested only in Larceny, it should be possible to run the simulator in any other implementation of R6 Scheme, including Chez Scheme, Ikarus, IronScheme, Mosh, PLT, and Ypsilon, but most or all of these systems will require you to store the libraries in separate files that are named according to some implementation-dependent convention. Some systems may also require those libraries to be installed using some implementation-dependent process.

Here is the grammar that generates the language used to describe a DFA:

<DFA>  -->  <DESC>  |  <DESC> <DFA>
<DESC>  -->  state <NAME> <TRANSITIONS>
          |  accept <NAME> <TRANSITIONS>
<NAME>  -->  <symbol>
<TRANSITIONS>  -->
                 |  <symbol> => <NAME> <TRANSITIONS>
                 |  <number> => <NAME> <TRANSITIONS>

For assignment 4 you are given:

• turing.sch -- an interpreter for Turing machines
• turing0.sch -- a simple example of a Turing machine
• turing1.sch -- a more complicated Turing machine

Last updated 9 March 2010.