问题标签 [context-free-language]

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

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

谢谢你。

我的教授希望我们能够快速判断给定语言是否是常规的、上下文无关的但不是常规的，或者不是上下文无关的（换句话说，无需绘制 PDA，编写上下文无关语法，并使用抽水引理作为上下文- 自由语言）。

我知道一些技巧可以帮助我们快速分辨出常规语言是什么，而不是语言是否是上下文无关的。

谢谢你。

我正在为我的理论课做硬件作业，遇到了一个我什至不知道从哪里开始的问题。我们正在介绍下推自动机部分。

“让 L1 是一种上下文无关语言，而 L2 是规则的。证明存在一种算法来确定 L1 和 L2 是否有无限数量的共同元素。”

我不知道如何解决这个问题。我无法让我的头脑理解这个想法。我确实知道常规语言不允许模棱两可，我想知道这是否是这个问题需要考虑的事情。此外，由于它位于“下推式自动机”部分，我假设它可能需要创建 npda 或 pda。谁能至少引导我朝着正确的方向前进。不是要求硬件解决，而是寻求硬件帮助！

提供一个上下文无关的语法，生成以下语言

Σ = {0,1}: {w = 0*1* : |w| 很奇怪}

我的解决方案：

S->AB|0|1

A->0A|^

B->1B|^

但是使用这种语法，我们可以创建偶数个字符串。

我想要产生 L = {0,1,000,111,001,011,00000,11111,00001,00011....}

嗨，我有以下 CFG

我设法删除了 epsilon，结果是：

我正在删除单元规则，这导致所有非终结符都具有相同的结果，例如：

我的问题是，我对 epsilon 的消除是否正确？有没有这样做？

我一直在尝试找到这种上下文无关语法的“第一组”。我想出了2个答案，但我不确定它们是否正确。如果有人能解释如何生成该语法的第一组，我将不胜感激。

两个答案都以不同的方式编写，因为我读过的资料用不同的语法解释了它。

有问题的语法：

我的第一个答案：

我的第二个回答：

我正在学习形式语言和自动机理论，我有一个关于书中没有回答的问题的问题。问题是：

这种语言是上下文无关的、常规的还是上下文相关的？

L={a^ib^jc^k|i<=j 或 j<=i , j=k}

如果我有一种由以下上下文无关文法定义的语言 {0,1} 和起始变量 S，它是一种常规语言吗？S→TS, S→1T, S→1S T→TT, T→0T1, T→1T0 T→ε</p>

这种语言是正规的吗？

在我看来，这种语言不可能是规则的，因为它基本上是终端和变量的任意组合。而常规语言需要是右或左线性的。我是对的，还是我的想法不正确？是否有任何人推荐确定上下文无关语法是否正常的特定过程？

W 属于 {a,b}* 的 WW 是上下文无关语言吗？如果是，请提供 PDA。

在介绍计算理论书籍时，对于该语言 ，状态图如下：

我知道可能有其他图表，但我怀疑我找到的解决方案可能是错误的，这与原始图表略有不同：

对于我的解决方案，我将不胜感激任何计数器输入。