状态转移函数对加权自动机计算能力的影响

The Influence of State-transition Function on the Computing Powers of Weighted Automata

在非确定型加权自动机(NS-WA)与确定型加权自动机(DS-WA)的基础上,引入了状态转移函数是分明的非确定型加权自动机(NS-WAc)与状态转移函数是分明的带空移动的非确定型加权自动机(NS-WAε-c)的概念。在已知NS-WA与DS-WA不等价的结论下,进一步探究了NS-WAc、NS-WAε-c与DS-WA之间的等价性,并给出了等价性证明以及相关的算法和例子。

Based on the concepts of nondeterministic weighted automata(NS-WA)and deterministic weighted automata(DS-WA),we give the concepts of nondeterministic weighted automata with crisp transition function(NS-WAc)and nondeterministic weighted automata withε-move and crisp transition function(NS-WAε-c).It is known that NS-WA is not equivalent to DS-WA.Furthermore,we study the equivalences among NS-WAc,NS-WAε-c and DS-WA,and we give the algorithms and examples.