问题标签 [context-free-language]

那里有很多信息，但这些信息都不能真正帮助像我这样的菜鸟。我阅读了很多关于上下文无关语言和下推自动化的文章。现在我试图了解某些事物在代码中的外观。

假设我们定义了一种语言，例如：

给我们以下生产规则：

这在伪代码中到底是什么样子的？我假设所有生产规则都是定义为 S1 的 1 个状态，或者它们都是单独的状态？无论哪种方式我都不知道，如果有人可以帮助我了解这是如何工作的，那就太好了。

我知道我们分析输入的字符，并根据我们得到的输入，应用其中一条规则将符号推入我们的 PDA 堆栈。

我在大学讲座中看到这个作为一个可选的挑战问题，但不知道如何解决它。

设 L 为语言。这种语言是上下文无关的吗？要么给它一个上下文无关的语法，要么证明它不是上下文无关的。L = {apbqapbq : p,q >= 0}

我知道这是一种上下文无关的语言，但问题中的语言使用 2 个变量并且也可能等于 0，这让我认为它不是上下文无关的。L = {apbp:p >= 1}

我应该使用抽引引理吗？任何帮助和解释将不胜感激

我想知道编程语言开发人员如何验证并证明他们的语法是正确的。假设我为一种新语言创建了一个新语法。我可以通过提供不同类型的测试程序，使用单元测试工具测试我的语法。但是，我永远不会 100% 确保我的语法是正确的。语言开发人员如何确保他们的语法在现实世界中是正确的？

假设我用铅笔和纸为一种新语言创建了一个语法。但是，我犯了一个错误，我的语法接受以 + 结尾的表达式，如 2+2+。如果我没有发现错误，我将使用这个不正确的语法来实现我的语言。经过实施和单元测试，我可以找到错误。在开始任何实施之前是否可以找到它？

当然，我可以使用铅笔和纸（推导等）输入一些示例输入来尝试我的语法，但我可能会错过一些极端情况。有没有更好的方法或者在真正的语言开发人员中如何测试他们的语法？

有人可以回答这些问题并为我简化，我没有完全掌握这些想法。我对诸如“终端到底是什么？”“w 代表什么？”之类的东西总体上感到困惑。

但至于真正的问题，请归类为常规、无上下文或其他。

a) {a^nb^na^n} ∩ # 个 a 是偶数。
b)(a^nb^n) ∪ 回文
c)a^n+mb^ma^2n

请分类说明。

标题解释了它。我无法将“方程”的左侧与右侧同步，因为每当我在左侧生成 2 时，必须出现右侧的 2。难道这种语言不是上下文无关的吗？提前致谢！

L = {2^x ∗ 2^y ∗ 2^z = 2^(x+y+z) | x, y, z > 0}

编辑：这与数学方程无关。" *" 和 " =" 只是语言字母表的符号， 2 的 " x" 次方意味着 2 被重复 x 次。

我发现在为该语言构建语法时遇到困难，尤其是对于线性语法。

谁能给我一些基本的技巧/方法，我可以为任何语言构建语法？提前致谢

我怀疑这个问题的答案“为语言构建线性语法：是否正确

L ={a^nbc^n | n 属于自然数}

解决方案：

右线性语法：

S--> 作为 | bA

A--> cA | ^

左线性语法：

S--> Sc | 抗体

A--> Aa | ^

我有一个关于这个问题的问题：

L= 空，其中字母为 {a,b}

如何为此创建语法？怎么会有生产规则？提前致谢

我在计算机科学理论的研究中遇到了一些问题......

谁能解释一下我们如何将上下文无关语法（cfg）转换为相应的下推自动机（pda）的算法，只有 2 个状态？

谁能告诉我如何证明这个语法是不明确的？提前致谢。

我找不到显示语法不明确的字符串:(

G2 = { {S}, {a,b}, {S->ab|ba|SS}, S }

我在互联网上搜索过，大多数人说只是说上下文无关语言对于联合、连接、反转和 Kleene Star 是关闭的。它们是否也因设置差异而关闭？