NAME

finite_automata

SYNOPSIS

finite_automata [--verbose ] [--diagram] input1.fa [ input2.fa ... ]

DESCRIPTION

A perl script that implements and displays DFAs and NFAs (deterministic and non-deterministic finite automata).

Options

--diagram: For each input file input.fa, create input.dot and input.png files with graphviz diagram specs and a PNG image of the finite state machine.
--verbose: Turn on lots of diagnostic output, including a trail of the states passed through during execution.

Input files are text files ending in a .fa (i.e. finite automata) extension in YAML format, which specify the states, transitions, and input strings for deterministic or non-deterministic finite automata. See the files in this directory for examples.

Setting the input to *.fa will cause the program to run all input files in the current directory

~ is used to represent the empty string, or for a transition without any input. Often this is represented by the small greek epsilon (ε); however, ~ is a more commonly available symbol which is consistent with YAML's conventions for the empty string.

The automa's alphabet is taken to be all symbols appearing in the transition table, and so doesn't need to be given explicitly. Likewise, the set of states is taken to any be any states named in the transition table.

Each input file may include test cases, strings that are marked ``yes'' or ``no'' depending on whether they are or aren't in the language defined by the automata.

Here's an example of a machine that recognizes strings of 0's and 1's with an even number of 1's or a total length which a multiple of 3.

   example.fa
   ------- cut here -----------------------
   # This line is a comment.
   start: s
   accept: [ q0, r0 ]
   transitions :  
     #   state x alpha -> state
     - [ s,      ~,       q0   ]
     - [ s,      ~,       r0   ]
     - [ q0,     1,       q1   ]
     - [ q1,     1,       q0   ]
     - [ r0,     [0,1],   r1   ]
     - [ r1,     [0,1],   r2   ]
     - [ r2,     [0,1],   r0   ]
   tests :
     - [ yes, ~      ]
     - [ no,  00000  ]
     - [ yes, 1111   ]
     - [ no,  1010   ]
     - [ yes, 111000 ]
   ------- cut here -----------------------

Sample Session

Running the program on this file from the command line gives the following terminal output.

   $ ./finite_automata --diagram example.fa
   Running finite_automata on example.fa .
   
   ===== example.fa =====
   states : [ q0, q1, r0, r1, r2, s ] 
   accept : [ q0, r0 ]
   alphabet : [ 0, 1 ] 
   start : s
   tests : 
     yes   [  ]
     no    [ 0, 0, 0, 0, 0 ]
     yes   [ 1, 1, 1, 1 ]
     no    [ 1, 0, 1, 0 ]
     yes   [ 1, 1, 1, 0, 0, 0 ]
   transitions :
     q0      x  1             =>  q1    
     q1      x  1             =>  q0    
     r0      x  [ 0, 1 ]      =>  r1    
     r1      x  [ 0, 1 ]      =>  r2    
     r2      x  [ 0, 1 ]      =>  r0    
     s       x  ~             =>  q0    
     s       x  ~             =>  r0    
   analysis :
     It's not a strict DFA.
     Running inputs and tests :
       '' => yes (ok)
       '00000' => no (ok)
       '1111' => yes (ok)
       '1010' => no (ok)
       '111000' => yes (ok)
     Passed all 5 tests.
     Diagram created in file 'example.png'

AUTHOR and LICENSE

Jim Mahoney, Marlboro College (mahoney@marlboro.edu)