computer-science - 语言 A = {0^n 1^n 0^n} 上下文无关吗？

Question

我只是对不同的语言进行了一些思考（因为我正在为即将到来的期末考试复习），我想不出一个有效的下推自动机来处理语言 A = {0^n 1^n 0^n | n >= 0}。这不是上下文无关的语言，对吗？

Answer 1

我相信你是。它看起来非常类似于语言L = { a^ib^ic^i | i > 0 }的 Wikipedia article on the pumping lemma将其用作如何证明语言不是上下文无关的示例。

Answer 2

想一想 {0^n 1^n} 部分。替换0为(和1，)你就得到了简单嵌套括号的语言，这是一种语言不规则的死胡同。

添加最后的 0^n 使其与上下文相关（即不是上下文无关的）。请记住，CFG 可以由具有单个堆栈作为其唯一数据结构的有限状态计算机决定。看到 0 将导致字符被压入堆栈，看到 1 将从堆栈中弹出。这保证了 0 和 1 一样多，但是没有办法匹配更多的 0。