基于量子逻辑的几类有穷自动机之间的关系

The Relationships Among Several Types of Finite Automata Based on Quantum Logic

根据初始状态和终止状态是否为分明的,非确定型量子有穷自动机可分为四类,确定型量子有穷自动机可分为三类.本文详细讨论了四类非确定型量子有穷自动机之间的关系以及三类确定型量子有穷自动机之间的关系,并且利用新的构造方法,证明了初态为分明的确定型量子有穷自动机与终态为分明的确定型量子有穷自动机是等价的.这些结论为实际应用中计算模型的合理选取提供了理论依据.

With respect to the initial state and the final state being crisp or not,we classify the nondeterministic quantum finite automaton into four forms and the deterministic quantum finite automaton into three forms,and discuss the relationships among them.By employing a new construction method,we obtain that a deterministic quantum finite automaton with crisp initial state is equivalent to a deterministic quantum finite automaton with crisp final state.The results provide the theoretical foundations for the appropriate choice of computing models in practice.