问题标签 [context-free-language]

我在处理以下问题时遇到问题。

给出以下语言的上下文无关文法：

解决这个问题的最佳方法是什么？目前我只是用直觉来解决这些问题，但有没有有用的技术？即你能想到这种语言的 PDA 会是什么样子，然后从中推导出语法吗？有没有使用语法 A 和 B 找到语法 G = A 和 B 的方法？

我正在努力寻找如何解决这个问题，所以任何帮助都将不胜感激。

谢谢。

我遇到了两个完全不同的答案。

一个人说：

是的，确实存在 的上下文无关文法，以下文法确保存在的 1 可以有一半或更少的 0：{0i1j | 1≤i≤j≤2i}

另一个：不，反证法：

情况1：

假设您将 i 0 压入堆栈。

弹出 j 1s。

您无法确定 j<=2i。

案例二：

假设您将 2i 0 压入堆栈。

弹出 j 1s。

您无法确定 j>=i。

压入堆栈的任何其他不等于 i 或 2i 的值都是相对于这两个值中的任何一个的值，因此适用相同的推理。

是否正确？非常感谢！

为了表达常规语言，我们使用正则表达式，对于上下文无关语言，我们可以使用类似堆栈的内存，我知道上下文无关语言有一些规范，例如中心嵌入，但我仍然不确定我们什么时候可以确信给定语言是上下文自由语言？例如为什么自然语言不是常规语言。除了中心嵌入还有什么原因吗？

我有以下问题。这个语法是模棱两可的：

stmt -> 如果 expr 则 stmt stmt' | 一个

stmt'-> 否则 stmt | 爱普生

表达式 -> b

我试图修改它，我的结果是：

stmt -> 如果 expr 则 stmt'' | 一个

stmt'' -> stmt | stmt'</p>

stmt' -> B 否则 stmt

表达式 -> b

但这不会生成相同的语言。

有人可以帮我修改模棱两可的语法，使其明确并接受相同的语言吗？

下面给出的语言是 CFL 吗？如果不能通过 Pumping Lemma 证明。L = {www| w 属于 {0,1}*} 我知道这不是 cfl！但我面临着通过抽引理来解决它的困难。请帮助我

G 是给定的 CFG，L(G) 是规则的吗？这是一个无法确定的问题。

但我的论点是，语言是给定的，如果我可以做以下任何事情，那么它将是常规的，否则将是非常规的：

• 创建 DFA/NFA
• 编写左线性或右线性语法
• 编写正则表达式

请告诉我为什么它无法确定？

如果我有{a^n b^n c^n | n > 0} \sum = {a,b,c}，我如何证明它是否是上下文无关语言？

我看这里：确定一种语言是否是上下文无关的，但对我来说没有多大意义。

我相信如果我这样做

但我不确定。任何帮助，将不胜感激！

我如何解释这个语法？我不明白为什么有些词是粗体的。

如果我为此编写解析树/表，我会包含粗体字吗？我想弄清楚图片中的语法是否为 LL(1)，但不明白如何阅读。任何帮助，将不胜感激！

我正在学习构建解析器，并认为也许我应该从一个简单的解析器开始，比如 JSON。我正在查看此RFC 文档中发布的 JSON 语法。

此处显示的 JSON 语法如下所示。这是什么样的符号，我如何为此生成/编写解析器？

什么是非上下文无关的递归可枚举语言的简单示例？我的教科书在明确提供这样一个例子方面很糟糕。

需要明确的是，这不是一个 hmk 问题。