computer-science - 是语言 {0^n 1^n 0^k | k != n} 上下文无关？

Question

我相信这种语言不是上下文无关的，因为 PDA 不可能比较 2 个相同长度的 0 和 1 块并记住它的长度以备后用。

不幸的是，我不知道如何证明这一点。

我尝试使用泵引理无济于事......

我还试图通过矛盾假设语言是上下文无关的，并使用这样一个事实，即上下文无关语言与常规语言的交集也是上下文无关的(通过找到一些神秘的常规语言 L)，并且令人惊讶地(或不是) - 我所有的努力都白费了...

任何帮助，将不胜感激

Answer 1

是语言 { 0n1n0k | k != n} 上下文无关？

否 , 语言 L = { 0n1n0k | k!=n } 是 不是上下文无关的语言 .另外，Class of Regular Languages is subset of class Context free languages .

你的想法使用 PDA是表明语言不是上下文无关的正确且明显的方式。
我们不能画 PDA对于语言 0n1n0k 因为匹配前缀 0n 到 1n 堆栈后变空，那么我们没有存储信息来检查天气后缀 0K 是否等于 n或不。

提示:对于形式证明

第一

L = {0ⁿ1ⁿ0^k | k!=n } now complement of L is L^'.

L^' = {{0ⁿ1ⁿ0ⁿ} that is well known context sensitive language (can be proof).

和 上下文敏感语言的补充本身就是上下文敏感的。

第二

对于抽引引理:

L = {0ⁿ1ⁿ0^k | k!=n } is Union of L₁ and L₂, Where
L₁ = {0ⁿ1ⁿ0^k | k > n } and L₂ = {0ⁿ1ⁿ0^k | k < n },

L = L₁ U L₂

L1 和 L2 都是非上下文无关语言。和 两种非上下文无关语言的联合是非上下文无关的。 (可以很容易地通过语法证明)

另外， 两种上下文相关语言的并集连接是上下文相关的。