Self-Modifying Finite Automata.
Roy S. Rubinstein, John N. Shutt · 1993
We present here a new model of computation: the Self-Modifying Finite Automaton #SMFA#. This is similar to a standard #nite automaton, but changes to the machine are allowed during a computation. It is shown here that a weak form of this model has the power to recognize an important class of context-free languages, the metalinear languages, as well as some signi#cant non-context-free languages. Less restricted forms of SMFA's may accept even more. 1 Introduction Many abstract models of computation have been devised over the years, including #nite automata, pushdown automata, linear-bounded automata, and Turing Machines. This technical report presents a new model: the Self-Modifying Finite Automaton #SMFA#. SMFA's are similar to standard #nite automata, but changes to a machine are allowed during a computation. While retaining much of the simplicity of #nite automata, SMFA's have greater power and can recognize many non-regular and even non-context-free languages. This paper show...