Кажется, что для этой модели недетерминированные машины не эквивалентны детерминированным, в основном по той же причине, по которой детерминированные КПК не эквивалентны недетерминированным.
Рассмотрим язык
L =х $ у∣ | х | = | Y| ∧х≠у
(где
- специальный знак, не содержащийся в
x и
y ).
$ИксY
Я утверждаю , что недетерминированная машина - Н L может решить этот язык: Он выполняет такой же , как для КПК L . Стандартное решение PDA использует стек только для подсчета смещений: он недетерминированно угадывает смещение i , запоминает значение x i (добавляя символ в стек на каждом шаге), затем PDA игнорирует ввод, пока не найдет $ , и затем он выталкивает символы из стека, пока не станет пустым. На этом этапе мы находимся именно на y i, и он может проверить, если x i ≠ y iNЧАСA LLяИкся$YяИкся≠ уя, (если что-то пойдет не так в середине, КПК «умирает»). Поскольку алфавит стека одинарный, его можно смоделировать на машине с минимальной кучей. На самом деле: любой который принимается КПК с унарным алфавитом, может быть принят машиной с минимальной кучей. (Я игнорирую, может быть, еще один специальный знак, добавленный для идентификации пустого стека, но эквивалентный знак может быть добавлен в кучу)L
Что касается другого направления, у меня нет формального доказательства, но вот мои мысли:
Я утверждаю, что детерминированная машина - H A L не способна решить этот язык. Интуитивно понятно, что содержимое кучи не может быть соотнесено с x (в противном случае перестановка x . Содержимое кучи остается неизменной ..). Это говорит о том, что единственное, что имеет значение, это количество элементов в куче, но тогда, если D - H A L может решить L , то может быть и детерминистический - P D ADЧАСA LИксИксDЧАСA LLпD A .
Изменить: более подробную информацию о претензии "permute ". Предполагая гипотезу Рафаэля,
существуют x 1 и x 2, что после прочтения их содержимое кучи одинаково. Затем рассмотрим слова x 1 $ x 1 и x 2 $ x 1 . Содержимое кучи одинаково, когда HAL достигает знака доллара, поэтому он должен либо принять оба, либо отклонить оба. противоречие .ИксИкс1Икс2Икс1$ х1Икс2$ х1
Кто-нибудь видит непосредственное доказательство этой гипотезы?