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

Question

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

Answer 1

我相信你是。它看起来非常类似于语言 L = { a^i b^i c^i | i > 0 } 维基百科文章 the pumping lemma用作如何证明语言不是上下文无关的示例。