Автомат с нажатием кнопки, который распознает отрицание языка

Question

В качестве примера:

Скажем, я хочу создать КПК, который распознает язык всех строк в алфавите {1,0}, которые НЕ являются палиндромами. Если я спроектирую карманный компьютер, который распознает язык всех строк по {1,0}, которые являются палиндромами, а затем поменять местами все принимаемые состояния для состояний сбоя, и наоборот, получу ли я нужный КПК?

РЕДАКТИРОВАТЬ: Есть ли простое формальное доказательство в любом случае?

Answer 1

Набор контекстно-свободных языков (или КПК) не закрыт при дополнении. (В ответе на вопрос " Что такое контекстно-свободная грамматика для дополнения к двойному слову над 0,1?" Есть простая демонстрация, которая создает CFG для дополнения {ww|w∈{0,1}*}, Дело в том, что {ww|w∈{0,1}*} это не КЛЛ, как известно.)

Инвертирование всех состояний конечного автомата прекрасно работает для конечного автомата (а обычные языки закрыты при дополнении), но не будет работать для КПК именно из-за стека.