Formal
Languages
and the
Theory of
Computation

Fall 2019
course
site

finite automata - Jim's notes

simple automata in python

Check out even_1_automata.py ...

*.fa online simulator

I've installed on cs a *.fa simulator that implements a yaml finite automata spec. There's a link to it over on the left, in the "student" block.

Here's an example of a machine

# This is a *.fa (i.e. finite automata) definition file
# which follows the yaml.org data format.
# The ~ character is used to refer to the empty string.
# The automata below is non-deterministic, since both
# ~ and lists of symbols are used in the transition table.
#
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 ]
https://cs.marlboro.college /cours /fall2019 /formal_languages /notes /dfa
last modified Mon September 26 2022 2:08 am