问题标签 [context-free-language]

我需要生成明确的语法来访问语言L= { a^i b^j c^k | i, j, k ≥ 0 , i = j or i = k }

我已经拥有的是：

但是这种语法是模棱两可的，它可以通过两种不同的方式识别 a,b,c 数量相等的字符串。有没有更好的建议让它明确？

我想使用扩展巴科斯-瑙尔形式 (EBNF) 上下文无关语法定义一组无序的值。在 EBNF 中定义值的无序列表很容易，例如：

但是，我怀疑它是否可以用于无序集。

以下是有效无序值集的示例：

虽然无效列表是：

或任意长度的列表。

我有一个关于为该语言设计下推自动机的问题：

换句话说，'s in 的数量是b'sw数量的2 倍和's 数量a的3 倍之间a。

我对这个问题感到困惑：我知道（希望如此！）当 's 的数量分别b等于 's 数量的两倍a或 's 数量的 3 倍时，如何设计 PDA 以接受该语言a。

这种语言似乎是它们的交集，但我认为没有一种简单的方法可以使用这些交集来创建 PDA。我们如何结合数字可以介于两个值之间的事实。

任何帮助深表感谢...

PS如果您还可以提供上下文无关的语法（以及解释），那也将非常有帮助。

PPS：另外，如果有人可以提供一个链接以某种方式展示如何逐步构建无上下文语法，我真的需要它。（我找到了正则表达式的正则文法的链接，但是对于上下文无关文法，当我尝试跟踪变量并看到一个变量转到自身，或者转到另一个变量时，该变量又返回到初始变量，我真的很困惑。）

所以，我有这种语言L={a^i b^2j+1 / i<>j}，我必须基于它生成一个上下文无关的语法，你能帮我说明一下这样做的步骤吗？

到目前为止，我有这个：

但我不确定它是否正确，请帮助我理解它。

当一种语言满足常规语言的泵引理时，并不总是意味着它是一种常规语言。那么它至少是一种上下文无关的语言吗？或者介于两者之间？

如何找到可被 5 整除且 MSB 为 1 的二进制数语法并找到 L 的反转

所以，我需要一个生成数字的语法，比如..

等等

我在字母表 {0,1} 上有语言 {4^(w⋅g)34^(g)|w,g∈NAT}。

我需要找出这种语言是可识别的、可判定的、上下文无关的、常规的还是这些都不是。

我将如何去做或知道？

谢谢

我看到一个关于自动机理论的注释：

考虑以下语言：

L={xy : x,y in {a,b}*}

并考虑以下约束：

1) x=y

2) x != y

3) x=(y) 反向

4) x 的数量不等于 y 的数量

我读了一种带有约束 2,3,4 的语言是上下文无关的。高度赞赏 1 到 3 的任何提示或教程。

我需要为由具有相同数量的 a 和 b 的偶数长度回文组成的语言构造一个 CFG，然后证明它生成了该语言。

这是我得到的CFG：

S→ 阿巴 | 巴布| abSba | 巴萨布 | ε

我不确定该怎么做才能证明它（我只是在逻辑上想出了这个）......如果有人能指出我正确的方向，我将不胜感激。谢谢！

我正在尝试制作一个与以下功能等效的 CFG。我知道 B 是循环计数器，因此它可能是推入堆栈的一系列元素，每次循环完成时，都会弹出 B 中的一个元素，并且如果 B = Epsilon 退出。如何处理 while 循环上半部分的加法？