Self-Modifying Finite Automata

This page is Copyright John N. Shutt 1996–1999,2002–2011,2015–2017. Here's what you're allowed to do with it.
Last modified: 01-Jan-17.


An SMFA is similar to an ordinary finite automaton, except that,

  1. Each transition not only changes the state and reads an input symbol, it also modifies the set of transitions of the machine.
  2. Each SMFA has a fixed finite set of registers, whose values are created states (as opposed to predefined states, which are part of the initial configuration of the machine).  When creating a new transition, its source and destination states must be specified; the only way to specify a created state is by retrieving it from a register; and the value of a register can only be changed to a state that doesn't already exist.  Thus, once a created state is no longer stored in the register that created it, there is no way to create more transitions to/from that state.

Journal papers:

Tech reports:
See also: my other Academic Work.