一个下推自动识别语言

Question

作为例子的否定：

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

编辑：有没有简单的形式证明任何一种方式？

Answer 1

上下文无关语言（或PDA）的集合在补充下未关闭。 （有没有在回答What is the context free grammar for the complement of the double word over 0,1?，它构造一个CFG为{ww|w∈{0,1}*}补一个简单的演示。事实上，{ww|w∈{0,1}*}不是CFL是众所周知的。）

反转状态机的所有状态正常工作了有限状态自动机（和正规语言在补充下关闭），但由于堆栈原因，它不适用于PDA。