context-free-grammar - 是什么让这个示例成为上下文无关语言而不是常规语言？

我很难看到是什么使“任意数量的 a 后跟相同数量的 b 和 c”成为上下文无关语言，而“任意数量的 a 后跟任意数量的 b 后跟任意数量的 c”是常规语言，正如我所看到的，没有教师解释。（注意在后一个例子中，b 和 c 的数量可能是唯一的，而在前一个例子中，b 和 c 的数量是相等的）。

任何见解都值得赞赏；为一个可能粗鲁的问题（格式）道歉。

标签： context-free-grammarregular-languagecontext-free-language

如果“a”的数量必须等于“b”和“c”的数量之和，则不能随意将“b”或“c”添加到字符串中。您可以做的是保留一个堆栈，在其中推送每个“a”，每次看到“b”或“c”时从堆栈中弹出一个。如果句子的结尾与空堆栈重合，则该句子是可以接受的。像这样具有单个堆栈的解析器对应于上下文无关语法。

堆栈是解析器状态的一部分，没有什么限制堆栈的大小。所以你需要潜在的无限状态。常规语言可以由具有有限状态的解析器解析（通常表示为状态机中的单个状态或从有限的可能性集合中进行的某种其他选举）。这足以识别a*b*c*，因为已经看到了多少个“a”或还有多少个“c”都无关紧要。

您可能知道，如果“a”的数量、“b”的数量和“c”的数量必须相等，那么单个堆栈已不足以进行识别，而语言不再是上下文无关的。该语言是上下文相关的。