6

我已经尝试并烧毁了我的大脑来理解离散数学及其应用(Rosen)中的正则语言的定义,但没有达到理解为什么定义在这本书中这样的目标。在第(789)页,我重新定义了定义:

类型 3 语法定义为:

w1 --> w2

其中 w1 是非终结符,而 w2 的形式为:

w2 = aB
w2 = a

其中 B 是非终结符,a 是终结符。一个特殊情况是 w1 是起始符号而 w2 是 lambda(空字符串):

w1 = S
S --> lambda

我找不到答案的两个问题。首先,为什么w2不能采用Ba的形式。其次,为什么lambda只允许用于起始符号。书中指出,常规语言相当于有限状态自动机,我们可以很容易地看到,我们可以为这两种情况构建 FSA。我查看了其他资源,这些资源中不存在这些限制。

4

1 回答 1

5

首先,为什么 w2 不能是 Ba 的形式。

取以下以 W 为起始符号的文法:

W -> lambda
W -> aX
X -> Wb

它生成不是常规语言的 {an b n : n natural } 因此,如果您只想生成常规语言,则此限制是必不可少的。或者,您可以允许 w2 = Ba,但禁止w2 = aB 类型的规则——这也给出了常规语言。该语法将构建一个单词“backwards”。

如果您允许这两种类型的规则,您将获得一个称为线性语言的类。

其次,为什么 lambda 只允许用于起始符号。

这不是必要的限制。

您可以消除 lambda 对非终结符号的所有使用:获取一些规则 W -> lambda,将其删除,然后将所有规则 U -> aW 替换为 U -> aW 和 U -> a。显然,您不能消除使用 lambda 作为终端符号(该语言将不再产生空字)。

因此,在许多地方使用 lambda 的每个类型 3 语法都可以“规范化”为仅将 lambda 用于起始符号的语法。

于 2010-05-21T22:42:22.017 回答