Time varying finite automata

Abstract

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.

Keywords:

• Terminal weighted grammars
• time varying grammars
• time varying finite automata
• time varying generalized finite automata

C.R. Categories:

• 5.23