不收缩文法, 目录, 形式定义, 例子, 等价的文法类型和表达能力, 参见形式定义, 编辑在形式语言理论中, 文法是不收缩的, 或单调的, 如果所有它的产生规则都有如下形式, 这里的, 指示, 的长度, 就是说, 没有规则会减少被重写的字符串的大小, 它是本质不收缩的, 如果可有一个例外, 也就是, 规则, ε这里的, 是开始符号而, 是空串, 例子, 编辑s, asbc, bb这个文法生成语言, displaystyle, nbsp, 它不是上下文无关的, 还有给语言, displaystyle, nbsp, 更. 目录 1 形式定义 2 例子 3 等价的文法类型和表达能力 4 参见形式定义 编辑在形式语言理论中 文法是不收缩的 或单调的 如果所有它的产生规则都有如下形式 a gt b 这里的 a b a 指示 a 的长度 就是说 没有规则会减少被重写的字符串的大小 它是本质不收缩的 如果可有一个例外 也就是 规则 S e这里的 S 是开始符号而 e 是空串 例子 编辑S abc S aSBc cB Bc bB bb这个文法生成语言 a n b n c n n 1 displaystyle a n b n c n n geq 1 nbsp 它不是上下文无关的 还有给语言 a n b n c n d n n 1 displaystyle a n b n c n d n n geq 1 nbsp 的 更加复杂 的不收缩文法 等价的文法类型和表达能力 编辑有容易的过程把任何不收缩文法转换成 Kuroda范式 已知把任何不收缩文法变换成上下文有关文法或反之的过程 所以 不收缩文法 Kuroda 范式的文法 和上下文有关文法有同样的表达能力 更精确地说 不收缩文法精确的描述不包含空串的上下文有关语言 而本质不收缩文法精确的描述上下文有关语言的集合 参见 编辑上下文有关文法 Kuroda范式 形式文法 分析表达式文法 随机上下文无关文法 取自 https zh wikipedia org w index php title 不收缩文法 amp oldid 55531382, 维基百科，wiki，书籍，书籍，图书馆，
