Rob*_*777 5 computer-science context-free-grammar pushdown-automaton regular-language
我相信这种语言不是上下文,因为PDA不可能比较2个0和1的相同长度的块,并且还记住它的长度以供以后使用.
不幸的是,我不知道如何证明它.
我尝试使用泵浦引理无济于事......
我还试图通过矛盾来假设语言是无上下文的,并且使用这样一个事实,即上下文无关语言与常规语言的交集也是无上下文的(通过找到一些神秘的常规语言L),并且令人惊讶(或者不是) ) - 我所有的努力都是徒劳的......
任何帮助,将不胜感激
不，语言 L = { 0 n 1 n 0 k | k!=n } 不是上下文无关语言。此外，常规语言类是上下文无关语言类的子集。
你的想法使用的PDA是正确且明显的方式来表明语言不是上下文无关的。我们无法绘制PDA语言 0 n 1 n 0 k，因为在匹配前缀 0 n到 1 n后堆栈变空，然后我们没有存储的信息来检查天气后缀 0 Kn是否等于 。
提示：用于形式证明
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 都是非上下文无关语言。两种非上下文无关语言的并集是非上下文无关的。（可以很容易地通过语法证明）
此外，两种上下文相关语言的并集、串联也是上下文相关的。