不收缩文法
形式定义
在形式语言理论中，文法是不收缩的（或单调的），如果所有它的产生规则都有如下形式
- α -> β 这里的 |α| ≤ |β|，|α| 指示 α 的长度。
就是说，没有规则会减少被重写的字符串的大小。
它是本质不收缩的，如果可有一个例外，也就是，规则
- S → ε
这里的 S 是开始符号而 ε 是空串。
例子
- S → abc
- S → aSBc
- cB → Bc
- bB → bb
这个文法生成语言 ，它不是上下文无关的。
还有给语言 的（更加复杂）的不收缩文法。
等价的文法类型和表达能力
有容易的过程把任何不收缩文法转换成 Kuroda范式。
已知把任何不收缩文法变换成上下文有关文法或反之的过程。
所以，不收缩文法，Kuroda 范式的文法，和上下文有关文法有同样的表达能力。