不收缩文法

形式定义

形式语言理论中,文法不收缩的(或单调的),如果所有它的产生规则都有如下形式

α -> β 这里的 |α| ≤ |β|,|α| 指示 α 的长度。

就是说,没有规则会减少被重写的字符串的大小。

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

S → ε

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

例子

S → abc
S → aSBc
cB → Bc
bB → bb

这个文法生成语言  ,它不是上下文无关的。

还有给语言   的(更加复杂)的不收缩文法。

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

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

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

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

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

参见