量化上下文无关语言的代数性质

摘要

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同.%By introducing the concepts of quantitative pushdown automata and quantitative context-free grammars,this paper investigated the equivalent relation that a quantitative language can be accepted by quantitative pushdown automatain two different ways.It is showed the fact that quantitative pushdown automata can accept the same quantitative context-free languages which are generated by quantitative context-free grammars over commutative double unital valuation monoid in the meanwhile.