论文标题
Greibach的$ω$ - 代数系统和加权简单$ω$ -PUSHDOWN AUTOMAMATA的普通形式
Greibach Normal Form for $ω$-Algebraic Systems and Weighted Simple $ω$-Pushdown Automata
论文作者
论文摘要
在加权自动机理论中，许多关于形式语言的经典结果已扩展到定量环境中。在这里，我们调查了无限单词的无上下文语言，$ω$ - 不含语言的概括（Cohen，Gold 1977）以及有限单词的加权无上下文语言的扩展（Chomsky，Schützenberger，1963年）。与正式语法理论一样，这些不加权的无上下文语言或$ω$ - 代数系列可以表示为混合$ω$ - $ - 代码方程式的解决方案，并且通过加权$ω$ -PUSHDOWN AUTAMAMATA。 在我们的第一个主要结果中，我们表明（混合）$ω$ - 代数系统可以转换为Greibach正常形式。我们在第二个主要结果中使用Greibach普通形式，以证明简单的$ω$ -RESET下降自动机识别所有$ω$ -Algebraic系列。简单的$ω$ -RESET自动机不要使用$ε$ - $ - 最多只能通过一个符号更改堆栈。这些结果将无上下文语言的基本属性推广到无上下文的语言。
In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of $ω$-context-free languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Schützenberger 1963). As in the theory of formal grammars, these weighted context-free languages, or $ω$-algebraic series, can be represented as solutions of mixed $ω$-algebraic systems of equations and by weighted $ω$-pushdown automata. In our first main result, we show that (mixed) $ω$-algebraic systems can be transformed into Greibach normal form. We use the Greibach normal form in our second main result to prove that simple $ω$-reset pushdown automata recognize all $ω$-algebraic series. Simple $ω$-reset automata do not use $ε$-transitions and can change the stack only by at most one symbol. These results generalize fundamental properties of context-free languages to weighted context-free languages.
