论文标题
Parikh定理的另一个证明
Yet another proof of Parikh's Theorem
论文作者
论文摘要
帕里克（Parikh）的定理说，无上下文语言的帕里克（Parikh）形象是半领的。我们使用Verma，Seidl和Schwentick的表格就Presburger Arithmetic的表述提供了帕里克定理的简短证明。证明依赖于无上下文语言的衍生树的欧拉属性，并受到Hierholzer算法的启发。它不使用乔姆斯基正常形式。
Parikh's Theorem says that the Parikh image of a context-free language is semilinear. We give a short proof of Parikh's Theorem using the formulation of Verma, Seidl, and Schwentick in terms of Presburger arithmetic. The proof relies on an Eulerian property of derivation trees of context-free languages and was inspired by Hierholzer's algorithm; it does not use the Chomsky normal form.
