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