我已经尝试并烧毁了我的大脑来理解离散数学及其应用(Rosen)中的正则语言的定义,但没有达到理解为什么定义在这本书中这样的目标。在第(789)页,我重新定义了定义:
类型 3 语法定义为:
w1 --> w2
其中 w1 是非终结符,而 w2 的形式为:
w2 = aB
w2 = a
其中 B 是非终结符,a 是终结符。一个特殊情况是 w1 是起始符号而 w2 是 lambda(空字符串):
w1 = S
S --> lambda
我找不到答案的两个问题。首先,为什么w2不能采用Ba的形式。其次,为什么lambda只允许用于起始符号。书中指出,常规语言相当于有限状态自动机,我们可以很容易地看到,我们可以为这两种情况构建 FSA。我查看了其他资源,这些资源中不存在这些限制。