我相信这种语言不是上下文无关的，因为 PDA 不可能比较 2 个相同长度的 0 和 1 块并记住它的长度以供以后使用。
不幸的是，我不知道如何证明这一点。
我尝试使用抽水引理无济于事......
我还试图通过矛盾假设该语言是上下文无关的，并使用上下文无关语言与常规语言的交集也是上下文无关的事实（通过找到一些神秘的常规语言 L），并且令人惊讶地（或不是） - 我所有的努力都是徒劳的......
任何帮助，将不胜感激
问问题
1402 次
1 回答
4
是语言 { 0 n 1 n 0 k | k != n} 上下文无关？
不，语言 L = { 0 n 1 n 0 k | k!=n }不是上下文无关语言。此外，常规语言类是上下文无关语言类的子集。
You Idea 使用PDA正确且明显的方式来表明语言不是上下文无关的。而且我们不能PDA为语言 0 n 1 n 0 k绘图，因为在匹配前缀 0 n到 1 n堆栈后变为空，然后我们没有存储信息来检查天气后缀 0 K是否等于n。
提示：对于正式证明
- 第一的
L = {0 n 1 n 0 k | k!=n } 现在 L 的补码是 L '。
L ' = {{0 n 1 n 0 n } 是众所周知的上下文相关语言（可以证明）。
上下文相关语言的补语本身也是上下文相关的。
- 第二
对于抽引引理：
L = {0 n 1 n 0 k | k!=n } 是 L 1和 L 2的并集，其中
L 1 = {0 n 1 n 0 k | k > n } 和 L 2 = {0 n 1 n 0 k | k < n },L = L 1 UL 2
L 1和 L 2 都是非上下文无关语言。和两种非上下文无关语言的联合是非上下文无关的。（可以很容易地通过语法证明）
此外，两种上下文相关语言的并集连接是上下文相关的。
于 2012-12-23T14:29:29.727 回答