计算机科学

首页 > 计算机科学

不收缩文法

2018-08-30 10:01:47     所属分类:形式语言

目录

  • 1 形式定义
  • 2 例子
  • 3 等价的文法类型和表达能力
  • 4 参见

形式定义

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

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

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

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

S → ε

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

例子

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

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

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

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

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

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

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

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

参见

  • 上下文有关文法
  • Kuroda范式

上一篇:L系统
相关推荐