不收缩文法

在形式语言理论中，文法是不收缩的（或单调的）

形式定义在形式语言理论中，文法是不收缩的（或单调的），如果所有它的产生规则都有如下形式

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

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

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

S → ε

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

例子S → abc

S → aSBc

cB → Bc

bB → bb

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

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

等价的文法类型和表达能力有容易的过程把任何不收缩文法转换成Kuroda范式。

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

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

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

形式语言在数学、逻辑和计算机科学中，形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。

如语言学中语言一样，形式语言一般有两个方面:语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。

本词条内容贡献者为:

黎明 - 副教授 - 西南大学