一個下推自動識別語言

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。