正规语言的定义

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

以W为起始符号的语法如下:

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

它产生{a ⁿ 乙 ⁿ :n自然不是常规语言。因此,如果您只想生成常规语言,那么这个限制是必要的。或者,您可以允许w2=ba,但是 禁止 w2=ab类规则-这也提供常规语言。这种语法将建立一个“向后”的词。

如果您允许这两种类型的规则,您将得到一个名为 linear languages .

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

这不是必要的限制。

您可以消除对非终端符号使用lambda的所有情况:采用一些规则w->lambda,将其删除,并将所有规则u->a w替换为u->a w和u->a。显然,您不能消除对终端符号使用lambda的情况(该语言不再生成空词)。

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