带空移动的加权有限自动机量化等价及其转换

摘要

In classical finite automaton theory,the finite automaton with ε-moves and normal finite automaton are equivalent.The weighted finite automaton valued in real numbers is an extension model of automaton,it assigns one weight valued in real numbers to every transition of classical automaton,these weights denote the cost of transitions execution.To study whether the finite automaton with ε-moves and the normal finite automaton are equivalent,we introduce the concept of quantitative equivalence,and give a method of how to transform a weighted finite automaton with ε-moves to a normal weighted finite automaton in quantitative equivalence with the former.Study result shows that these two are quantitatively equivalent.%在经典的有限自动机理论中，带空移动的有限自动机与不带空移动的有限自动机是等价的。取值于实数的加权有限自动机是自动机的一种推广模型，它给经典自动机的每个转换赋一个取值于实数的权值，这些权值表示执行转换的代价。为了研究带空移动的加权有限自动机与不带空移动的加权有限自动机是否具有等价性这一问题，提出量化等价的概念，并研究如何将一个带空移动的加权有限自动机转换为一个与之量化等价的不带空移动的加权有限自动机。研究结果表明：这两者是量化等价的。