查看“︁不收缩文法”︁的源代码

== 形式定义 ==
在[[形式语言]]理论中，[[形式文法|文法]]是'''不收缩'''的（或'''单调'''的），如果所有它的产生规则都有如下形式 
:α&nbsp;->&nbsp;β 这里的 |α|&nbsp;≤&nbsp;|β|，|α| 指示 α 的长度。 
就是说，没有规则会减少被重写的字符串的大小。

它是'''本质不收缩'''的，如果可有一个例外，也就是，规则

:S → ε

这里的 S 是开始符号而 ε 是空串。

== 例子 ==
:S → abc
:S → aSBc
:cB → Bc
:bB → bb

这个文法生成语言 <math> \{ a^n b^n c^n : n \ge 1 \} </math>，它不是[[上下文无关语言|上下文无关]]的。

还有给语言 <math> \{ a^n b^n c^n d^n : n \ge 1 \} </math> 的（更加复杂）的不收缩文法。

== 等价的文法类型和表达能力 ==

有容易的过程把任何不收缩文法转换成 [[Kuroda范式]]。

已知把任何不收缩文法变换成[[上下文有关文法]]或反之的过程。

所以，不收缩文法，Kuroda 范式的文法，和上下文有关文法有同样的表达能力。

更精确地说，不收缩文法精确的描述不包含空串的[[上下文有关语言]]，而本质不收缩文法精确的描述[[上下文有关语言]]的集合。

== 参见 ==
* [[上下文有关文法]]
* [[Kuroda范式]]
* [[形式文法]]
* [[分析表达式文法]]
* [[随机上下文无关文法]]

[[Category:形式语言|B]]