问题标签 [context-free-language]

这是否意味着只有非确定性上下文无关语言才能在联合下关闭？那么为什么几乎所有的教科书和网站都提到 CFL 通常在 Union 下是关闭的？一个直观的解释就足够了。不需要详细的证明。

我一直找不到任何具有嵌套和不等式的上下文无关语法示例。

例如，我正在尝试为以下内容编写 CFG：

{aibjckdl : (i < l) ^ (j < k)}

因此，对于，CFG 将简单地为：{aidl : (i < l)}

S -> aSd | dS | d

b 和 c 的情况类似。但我不知道如何嵌套这两个语法。任何类似的示例或指针都会有所帮助。

我很困惑，它不应该是确定性的，因为 (a,zo/azo) 将进入 q1 和 (a,z0/eplison) 进入最终状态。这是真的还是假的

刚刚开始在 Sipser 的书中关于 CFL 的章节，并且已经无法理解基础知识。

假设这是某种语言的语法：

我真的对这个 A0A 部分感到困惑。这是否意味着从 0 开始的左侧应该始终与右侧相同。这是否意味着 00011 或 000 不是这种语言？

我有这个形式主义列表，我需要根据它们的表达能力对它们进行排序，其中一个也不真正属于。

我按以下方式订购了它们：

4中的那些是最强大的。我删除了 LR 语法，因为它们只是编写 CFG 的一种方式，以便它们可以被 LR 解析器解析。

但是我不确定这是否正确。

当我们要将语法转换为乔姆斯基范式时，为什么要添加新的起始状态 S0 -> S？如果我们不这样做，会出现什么问题？

起初我认为这是因为 epsilon 规则。但是我们不会从 start 变量中删除 epsilon 规则。那么，添加 S0 -> S 有什么好处呢？

谢谢

大家晚上好！作为 Perl 中正则表达式的粉丝，我想出了一个问题，我无法通过谷歌搜索和搜索自己来回答。

所以让我给你一个关于我的问题的最小例子：

我有两个文本文件：

文件A.txt：

文件B.txt：

我想检查每个文件内容是否是由特定上下文无关语言生成的单词。例如在这种情况下： L={a^nb^n | n > 0}。

现在我遇到了问题，Perl 的正则表达式不起作用，因为它不是常规语言。当然，我可以编写一个小 PDA 并检查它是否终止。

但是 Perl 中是否有另一种方法可以解决这个问题？也许是一种传递上下文无关语法或某事的方法？

L = {a^nbc^n| i 大于 1 且小于 100 ，n 大于 1}

我想我误解了cfl 的抽引引理。为什么我不能选择一个单词 z = a^ncb^n 然后将其拆分为 u= a^sv = a^ns w=epsilon x=b ,y= b^n 然后用 i=0 泵送它然后得到一个矛盾因为 0 b 不满足语言？我可能在这里遗漏了一些东西。

我想匹配包含“k”个0后跟“k+4”个1的字符串，其中k大于或等于0

我尝试了以下语法是否正确？

我正在阅读有关常规语言的信息。我不明白一件事。

为什么

变量 -> 变量是不允许的？

其背后的原因是什么？

如果有这样的规则会发生什么？它变成什么样的语法？