Self-Modifying Finite Automata
An SMFA is similar to an ordinary finite automaton, except that,
Each transition not only changes the state and reads an input symbol, it also
modifies the set of transitions of the machine.
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
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.
and T. Okazaki,
"A note on self-modifying finite automata",
Information Processing Letters
72 nos. 1–2 (29 October 1999),
J. Shutt and
"Self-Modifying Finite Automata: An Introduction",
Information Processing Letters 56 no. 4 (24 November 1995),
J. Shutt and
"Self-Modifying Finite Automata",
In B. Pehrson and I. Simon, editors,
Technology and Foundations:
Information Processing '94 Vol. I:
Proc. 13th IFIP World Computer Congress,
Amsterdam: North-Holland, 1994,
my other Academic Work.