赋权型自动机的不同模型研究

Investigations on Variants of Weighted Automata

自动机理论是理论计算机科学的基础理论之一,在很多领域自动机有着广泛的应用,有穷状态自动机是正则语言的识别机器,通常分为确定型与非确定型两种模型,其识别语言的能力是等价的。赋权自动机是另一类重要的自动机模型,自动机的每条转移规则和状态可以赋以某一代数结构上的某一数值,从而可以计算输入字符串的权值。任何有穷状态自动机都可以视为一特殊赋权自动机,因此赋权自动机功能更强大,应用更为广泛。

Automata theory is one of the foundations of theoretical computer science.Automata techniques have extensive use in many fields.Finlte state automata are the recognizers of regular languages.Finite state automata have deterministic and nondeterministic models,which are equivalent with respect to the language recognizing abillty.Weighted automata are finite automata with each transition associated with an input symbol and an dement from an algebraic structure as well. The weight of any input string can be computed.Any finite automaton is a special weighted automaton,So weighted automata are more powerful and have more applications.