常规语言的定义

Question

我已经尝试并烧毁了我的大脑,以理解离散数学中的常规语言及其应用(罗森)的定义,但没有达到理解为什么定义与本书中的定义相同的目标.在页面(789),我正在改写定义:

类型3语法定义为:

w1 --> w2

其中w1是非终端,w2的形式如下:

w2 = aB
w2 = a

其中B是非终端,a是终端.一个特例是当w1是起始符号而w2是lambda(空字符串)时:

w1 = S
S --> lambda

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

Answer 1

首先,为什么w2不能成为Ba的形式.

以W作为起始符号采用以下语法:

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

它生成{a ⁿ b ⁿ:n natural},这不是常规语言.因此,如果您只想生成常规语言,则此限制至关重要.或者,您可以允许w2 = Ba,但禁止使用类型规则w2 = aB - 这也提供常规语言.该语法将构建一个"向后"的单词.

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

第二,为什么lambda仅允许用于起始符号.

这不是必要的限制.

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

因此,在许多地方使用lambda的每个类型3语法都可以"标准化"为仅使用lambda作为起始符号的语法.