Self-Modifying Finite Automata - Basic Definitions and Results
Roy S. Rubinstein, John N. Shutt · 1995
We formally define the Self-Modifying Finite Automaton (SMFA), a model of computation introduced in [RS93, RS94, RS95], as a subclass of a new more general model, the Self-Modifying Automaton (SMA). SMAs are similar to standard finite automata, but changes to the transition set are allowed during a computation. An SMFA is constrained in that it can have only finitely many different modification instructions, and the effect of each instruction must be computable. 1 Introduction The Self-Modifying Finite Automaton (SMFA) is a model of computation introduced in [RS93, RS94, RS95]. SMFAs are similar to standard finite automata, but changes to the transition set are allowed during a computation. While retaining much of the simplicity of finite automata, SMFAs have greater power. A weak form of SMFAs has been shown to accept the class of metalinear languages, as well as some other classes of context-free and even non-context-free languages [RS94, RS95]. The treatment of SMFAs in previous pa...