我已经尝试过，烧脑去理解 Discrete Mathematics and its Applications(Rosen) 中正则语言的定义没有达到理解为什么定义是本书中那样的目标。在第 (789) 页上，我重新定义了定义:
类型 3 语法定义为:
w1 --> w2
其中 w1 是非终结符，w2 的形式为:
w2 = aB
w2 = a
其中 B 是非终结符，a 是终结符。一个特殊情况是当 w1 是起始符号而 w2 是 lambda(空字符串)时:
w1 = S
S --> lambda
两个问题我找不到答案。一、为什么不能 w2 形式为 巴 .二、为什么 lambda 仅允许用于起始符号 只有 .书中指出，常规语言相当于有限状态自动机，我们可以很容易地看到，我们可以为这两种情况构建 FSA。我查看了其他资源，这些资源中不存在这些限制。
最佳答案
First, Why can't w2 be of the form Ba.
取以下以 W 为起始符号的文法:
W -> lambda
W -> aX
X -> Wb
它生成 {an bn : n natural } 这不是常规语言。所以这个限制是必不可少的，如果你只想生成常规语言。或者，您可以允许 w2 = Ba，但禁止 w2 = aB 类型的规则 - 这也给出了常规语言。该语法将构建一个单词“向后”。
如果您允许这两种类型的规则，您将得到一个名为 linear languages 的类。 .
Second, Why lambda is only allowed for the starting symbol only.
这不是必要的限制。
您可以消除 lambda 对非终结符的所有使用:采用一些规则 W -> lambda，将其删除，并将所有规则 U -> aW 替换为 U -> aW 和 U -> a。显然，您不能消除对终结符使用 lambda(该语言不再产生空词)。
因此，每个在许多地方使用 lambda 的类型 3 语法都可以“规范化”为仅将 lambda 用于起始符号的语法。
关于regex - 正则语言的定义，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2885936/