On the Structure of Finite Automata of Which M'Is an(Weak)Inverse with Delay τ

• 作 者: 陈世华
• 机 构: Institute of Software Academia Sinica,Beijing,
• 出 处: Journal of Computer Science and Technology
• 发表日期: 1986年02期
• 关键词: inverse automata label universal vertex verify nonempty infinite have proof

In this paper,we first give a method that for any inverse finite automaton M’ withdelay τ,all inver tible finite automata with delay τ,of which M’ is an inverse with delayτ,can be constructed;and a universal nondeterministic finite automaton,for all finiteautomata of which M’ is an inverse with delay τ,can also be constructed.We then give amethod that for any weak inverse finite automaton M’ with delay τ,all weaklyinvertible finite automata with delay τ of which M’ is a weak inverse with delay,can beconstructed;and a universal nondeterministic finite automaton,for all finiteautomata of which M’ is a weak inverse with delay τ,can also be constructed.

In this paper, we first give a method that for any inverse finite automaton M ’with delay τ, all in tttver finite automata with delay τ, of which M’ is an inverse with delayτ, can be constructed; and a universal nondeterministic finite automaton, for all finite automata of M ’is an inverse with delay τ, can also be constructed. Then then amethod that for any weak inverse finite automaton M’ with delay τ, all weakly invertible finite automata with delay τ of which M ’is a weak inverse with delay, can be constructed; and a universal nondeterministic finite automaton, for all finite automata of which M ’is weak inverse with delay τ, can also be constructed.