跳转到内容

不收缩文法

维基百科,自由的百科全书
(重定向自单调文法

形式定义

[编辑]

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

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

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

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

S → ε

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

例子

[编辑]
S → abc
S → aSBc
cB → Bc
bB → bb

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

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

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

[编辑]

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

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

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

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

参见

[编辑]