问题标签 [context-free-language]

我真的找不到这个问题的答案：

L = {大众 | {a,b) 的 v 元素，{b,c} 的 w 元素，a的数量 <= c 的数量}

V --> aV | BV | e

W --> bW | CW | e

但是我想不出如何将单词 v 和 w 一个接一个地组合起来，并牢记上述限制。谁能帮我一把？

我有以下 CFG 规则：

• S -> BSA | ε
• A -> abC | 一个 | C
• B -> baC | 乙 | ε
• C -> 抄送 | AB | ε

我处于算法的 epsilon 消除阶段，我已经消除了以下 epsilon C -> epsiolon，B -> epsilon，这是我到目前为止得到的：

• S_0 -> S
• S -> BSA | 南非 | ε
• A -> abC | 一个 | c| 抗体
• B -> baC | 乙 | 巴
• C -> 抄送 | AB | 交流| A 由于 S 是原始起始变量，我是否还应该消除 S-> epsilon（以粗体显示）？

我还应该在算法的单元规则阶段将 epsilon 复制到 S_0 吗？

我有一种语言，其中语言中的每个字符串都有偶数的 0 和 1（例如，0101、1010、1100、0011、10 都在语言中）。我希望定义一个描述这种语言的上下文无关语法。在定义了上下文无关文法之后，我想正式证明这个上下文无关文法描述了这种语言。

我想出了上下文无关的语法产生规则：

这是定义这种语言的正确上下文无关语法吗？

我有点难过证明部分。我猜我需要某种感应？

我正在阅读我的比较语言课的笔记，我有点困惑......

上下文无关语法和确定性上下文无关语法有什么区别？我正在专门阅读有关 CFG 的解析器是 O(n^3) 和 DCFG 的编译器是 O(n) 的具体情况，并且并不真正理解时间复杂度的差异如何如此之大（更不用说我仍然对使 CFG 成为 DCFG 的特征感到困惑）。

非常感谢您！

我需要找到以下语言的上下文无关语法：

L= { w 从 { a,b,c,d }* : #a+2#b=2#c+#d }

这是我的尝试，但我怀疑它是否正确：

我有点被自动机和语法问题困住了。我搜索了很多，但没有任何成功。

甚至有可能构造一个生成这种语言 L 的语法吗？

谁能为我提供简单的解决方案？

语言：{a^mb^n : m ≤ 2n}

如果有人可以就如何解决这个问题来构建语法以及一个非常感谢的解决方案提供建议！

我知道什么是常规语言和上下文无关语言，以及常规语言如何需要有限的内存以及其他相关内容。我担心的是，我认为如果 a ⁿ b ^m 这样n并且m它们之间有某种关系，那么它们就不可能是规则的，但是我在任何地方都找不到这样的东西。我这样说对吗？

如果我们用 operator *、|concatenation .（为了清楚起见，我们简单地省略了）、括号(和)来自一些字母的一些字母Sigma来描述正则表达式，那么描述正则表达式的语言本身就是正则表达式吗？在我看来不，因为我们有括号这一事实意味着没有有限状态机可以识别输入，所以它必须是一种上下文无关的语言。

注意题外话

我坚持我的立场，即这个问题与编程有关，因为我是在考虑编写正则表达式识别器时提出这个问题的。如果有人想要实现这样的事情，那么很快就会意识到您实际上需要一个上下文无关的解析器来解析正则表达式，这个问题将回答这个问题。此外，答案和问题并不是“非常理论化”，因为有限自动机的主题被认为是 1 年级和 2 年级本科生材料，因此将其放在理论计算机科学 Stackexchange 中将是一种矫枉过正。

JSpeech 语法格式允许用户在大括号中为单独的字符串指定标签，如下所示：

或者

参考规范的第 4.6.1 节更全面地描述了使用标签。

在Sphinx4 中，您可以使用RuleParsegetTags()中的方法捕获这些标签。因此，如果用户说“向左跳转”，则将返回以下标签“原始 jump_left ”

现在，我想做完全相反的事情——给定标签，我想将它与字符串匹配。所以对于“ NOTHING_HAPPENS ”，我想得到“什么都没有发生”或对于“ OBJECT_DESTRUCTION ”，一个包含所有可能选项的数组：“将死，死，死”。

有没有这样的方法可以以这种方式解析语法文件，还是我必须对其进行硬编码？