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

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