我很难阐明 Chomsky 类型 2（上下文无关语言）和 Chomsky 类型 3（常规语言）之间的区别。

有人可以用简单的英语给我答案吗？我无法理解整个层次结构。

我在维基百科上找到了这个解决方案。不应该说：j>n≥0 因为交集是两种语言中共有的元素。

考虑由 L1={a^(n)b^(n)c^(j)| 定义的语言 L1 和 L2 n,j ≥ 0} 和 L2 = {a^(j)b^(n)c^(n): n,j ≥ 0}。它们都是上下文无关的。但是，它们的交集是语言 L = {a^(n)b^(n)c^(n)| n≥0}。

给定 L1 和 L2（不规则）上下文无关语言 - L1 U L2 是否可能是规则的？

我知道这是可能的，但我找不到一个例子来说明这一点。很想得到一些帮助。

我不需要证明，因为这是一个客观的考试问题，只允许 2 分钟。选项是regular或cfl或csl。我不明白如何解决这个问题。

如果我们把它写成

现在调用第一部分 L1 和第二部分 L2，然后尝试使用，

De-morgons 定律 L'= L1' INTERSECTION L2'

考虑到我们只需要花 2-3 分钟的时间，我认为这不是正确的方法或快速的方法。有更好的方法吗？

给定 L1 上下文无关的非正则语言。给定 L2 常规语言。

L1 U L2 =常规语言有可能吗？另外，L1*L2 = 常规语言有可能吗？

我认为第二个是不可能的。但我不确定。

如果上述陈述之一（或两者）为真，希望看到一个例子。

我正在阅读上下文无关语法，我遇到了模棱两可的语法。如果 CFG 生成的语言具有多于 1 个解析树，则 CFG 是一种二义性语法。有什么方法可以找出或证明语法是明确的。一般来说，我可以测试一些由 CFG 生成的语言，并检查是否从该语言生成了超过 1 个解析树，以表明语法是模棱两可的。但是我如何检查或证明给 CFG 是明确的？

假设我们有以下 PDA：M=<Q, {0,1},{X,$},transition,q0, $, F>

我的解决方案是L(P)={w ϵ (0,1)* / 1^n 0 1^n 0 }......但还有另一个是1^n 0 1^n

哪个是最佳的？...考虑到两者之间的唯一区别是清除 PDA 的第一个输入，即 $

谢谢

假设： L={a ⁿ b ^m c ^o | n < m < o, n natural}
使用抽水引理我选择了： z = uvwxy = a ⁿ b ⁿ⁺¹ c ⁿ⁺²
|uv|<=n 和 |v|>0
=> uv ² wx ² y
If vwx 属于 a 和/或 b 没关系，我们将拥有比 c 更多的 a 和/或 b - 但如果 vwx 仅包含 c，它将是 L 的元素。
据我所知，所有新词都必须不是元素L 以表明它不是 CFL。我该怎么做？

你们能否列出您所知道的可判定为无上下文语言和确定性无上下文语言的问题。我确实在 Stack Overflow 和 Wiki 上获得了一些关于不可判定问题列表的信息，但与 CFG 或 DCFG 等细节无关。这个问题列表（带有证明/链接）可能对寻找此类问题的人非常有帮助。

我在理解如何获得两种无上下文语言的交集时遇到了一些麻烦（L = L1 ∩ L2）。我见过一个非常常见的例子：

但是像这样的例子呢：

我知道我需要为两者提出上下文无关的语法，我有：

但是此时，我不知道如何将两者相交并提出一种语言。我想知道是否有人可以告诉我如何。先感谢您。