Time varying finite automata
Kamala Krithivasan, Anindya Das · International Journal of Computer Mathematics · 1986
In this paper, we consider two machine models equivalent in power to Turing machines. Time varying finite automata are defined and it is shown that time varying nondeterministic finite automata are equivalent to time varying deterministic finite automata. But, we find that, when ε-moves are introduced, the power is increased to that of Turing machines. Equivalence between time varying regular grammars [6] and time varying nondeterministic finite automata with ε-moves is shown. We also consider time varying generalized finite automata and show their equivalence to terminal weighted regular grammars [5], thus proving that time varying generalized finite automata have the same power as Turing machines.