context-free-grammar - 识别语言否定的下推自动机

Question

举个例子：

假设我想设计一个 PDA 来识别字母表 {1,0} 上所有非回文字符串的语言。如果我设计一个 PDA 可以识别 {1,0} 上所有回文字符串的语言，然后将所有接受状态交换为失败状态，反之亦然，我会得到所需的 PDA 吗？

编辑：无论哪种方式都有一个简单的正式证明吗？

Answer 1

上下文无关语言（或 PDA）的集合在互补下不是封闭的。（ What is the context free grammar for the tiny over 0,1 ?{ww|w∈{0,1}*}{ww|w∈{0,1}*}

反转状态机的所有状态对于有限状态自动机来说效果很好（并且常规语言在补码下是封闭的），但由于堆栈，它对于 PDA 不起作用。