标签: context-free-grammar

C 语言中有哪些非上下文无关语言的例子？C语言中如何存在以下非CFL？

a) L1 = {wcw|w 是 {a,b}*}

b) L2 = {a^nb^mc^nd^m| n,m >=1}

我试图通过 Pumping Lemma 证明以下语言不是正则的。但我不确定我是否做得正确。

{L = a ^{2 n} | n>= 0 }

到目前为止，我所做的如下：

s = a ^{2 p}

x = a ^{2 i}

y = a ^{2 j}

z = a ^{2 p-ij}

因此 xy ² z = a ^{2 p+j}

这意味着 a ^{2 p+j} > a ^{2 p} ，使语言不规则

我做得对吗？还是我有什么问题？

我刚接受了期中考试,但无法回答这个问题.

有人可以给出一些语言的例子,并为语言构建一个语法,或者 至少告诉我如何去做它？

另外如何编写语法L:

L = {a ⁿ b ^m | n,m = 0,1,2,...,n <= 2m}？

提前致谢.

我正在尝试在字母表上写一个CFG ? = {a,b},所有单词的开头和结尾都是相同的数字,中间a至少有一个b.

现在我理解了CFG的基本概念,变量,生产规则等.不幸的是,我已经没有用于编写上述CFG的想法了.我到目前为止所有的一切都是

S ? aYXYa
X ? XbX | b | ?
Y ? ???

我想的是,生产规程S和X会给我一个字符串以两个**a**S于两侧尽可能多的**b**S IN的中间,我想.但是,我不确定如何在**a**的两侧放置尽可能多的****,b同时确保a每侧****的数量完全相同.

任何建议,解决方案将不胜感激.谢谢.

我正在尝试编写一个lambda演算解析器,我定义的语法似乎不在LLR中:

E ::= x | \x.E | EE | (E)

我减少左递归:

E ::= xE' | \x.EE' | (E)E'
E'::= EE' | <empty>

似乎不对,有人可以帮忙吗？

什么时候说一种语言是上下文无关的？

另外，上下文无关语言和上下文无关语法有什么区别？

我阅读了多个答案，指出如果一种语言不是上下文无关的，那么它的补充就是上下文无关的（如果我错了，请纠正我）。相反的情况是这样吗？上下文无关语言的补充是上下文无关的吗？

我试图证明 L= {a^ib^ic^i : i >= 1} 的补集是上下文无关的。L 补码是：{w 是 {a,b,c}* 上的一个词*：w 不在 L 中}。

众所周知，上下文无关语言在联合下是封闭的。因此，我试图将我的语言（{a^ib^ic^i} 的补集）划分为上下文无关的子集，其中它们的联合必须是上下文无关的。谁能帮我找到子集？每次我尝试这样做，最终都会得到 L*！

谢谢。

我对语法相当陌生，想知道是否有人可以帮助我使用解析树确定下面的语法是如何不明确的？我知道它需要有两个可以创建的不同字符串。

S -> (S)|SS|()

我可以将其转换为乔姆斯基范式和格雷巴赫，但这些的歧义让我感到困惑。