Это дополнительный вопрос этого .
В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что набор языков, принимаемых такими машинами ( ), не является ни подмножеством, ни надмножеством набора языков без контекста. Учитывая успешное разрешение и очевидный интерес к этому вопросу, я перехожу к нескольким последующим вопросам.
Известно, что обычные языки закрыты под различными операциями (мы можем ограничиться базовыми операциями, такими как объединение, пересечение, дополнение, различие, конкатенация, звезда Клини и обращение), тогда как языки без контекста имеют другое закрытие свойства (они закрыты под объединением, конкатенацией, звездой Клини и обращением).
HAL закрыт при обращении?
источник
Ответы:
Рассмотрим язык (где # 0 ( x ) обозначает количество нулей в x ).
Легко определить с помощью машины HAL - обратите внимание, что машине необходимо отслеживать два свойства: количество нулей в x против y и длину x , y (против z ). Он может помещать a в кучу для каждого нуля, который он видит в x (и затем позже высовывать любой ноль, видимый в y ); кроме того, он выдвигает любой бит в x , y (и позже появляется для любого бита z ). Так как все s выталкиваются в кучу, они не мешают подсчету. ⊥L×2 x y x,y z x y x,y z ⊥ служит разделителем и может быть практически проигнорирован.
0
0
1
1
1
0
Теперь пусть , обратный язык. То есть L = { z ⊥ y ⊥ x ∣ x , y , z ∈ { 0 , 1 } , # 0 ( x ) = # 0 ( y ) и | х | + | у | = Г } Покажем , что ни HAL машина не может решить , L .L=LR×2
Интуиция заключается в следующем. Как и выше, машина должна отслеживать как длину и количество нулей в x , y . Однако в этом случае необходимо отслеживать их одновременно . Это не может быть сделано через кучу. Более подробно, после прочтения z , куча содержит информацию о длине | х | + | у | , при чтении y машина также должна держать в куче количество нулей в y . Однако эта информация не может влиять на информацию, которую куча уже имеет на ожидаемой нами длине xz x,y z |x|+|y| y y x быть. Очень интуитивно, либо информация о количестве нулей будет «ниже» информации о длине , и тогда мы не сможем получить к ней доступ при чтении х , либо она «выше» этой информации, делая последнюю недоступной, или две информации будут «смешаны» и станут бессмысленными.x x
Более формально, мы собираемся использовать какой-то «насосный» аргумент. То есть мы возьмем очень длинный ввод и покажем, что «состояние» машины должно повторяться во время обработки этого ввода, что позволит нам «заменить» ввод, когда машина повторяет свое «состояние».
Для формального доказательства нам нужно упростить структуру машины HAL, а именно, что она не содержит «петли» переходов 1 . Исходя из этого предположения, мы видим, что для каждого входного символа, который обрабатывает машина, содержимое кучи может увеличиваться / уменьшаться не более чем сε 1 c (для некоторой достаточно большой константы ).c
Доказательство.H L 4n |x|=|y|=n |z|=2n ⊥ z,y #0(y)=n/2 различнаяй«ы такиечтог⊥у⊥х∈L.(nn/2) x z⊥y⊥x∈L
Предположим , решает , L , и рассмотрим достаточно долго вход (скажем, длиной 4 л , при этом | х | = | у | = п , | г | = 2 п , не обращая внимания на ⊥ сек и далее). Чтобы быть конкретным, зафиксируем z , y и предположим, что # 0 ( y ) = n / 2 . Обратите внимание, что есть ( п
Рассмотрим содержимое кучи сразу после обработки . Он содержит не более 3 n c символов (где каждый символ из фиксированного алфавита Γ ), по нашему предположению. Тем не менее, есть ( пz⊥y 3nc Γ (nn/2) x′s x1,x2
It is clear that the machine must accept the wordz⊥y⊥xp1xs2 , where xp1 is a prefix of x of length n/2 and xs2 is a suffix of x2 of the same length. Note that the number of zeros in xp1xs2 differs from the number of zeros in x1 and x2 (that is, from #0(y) ), due to the way we chose x1 and x2 , thus we reached a contradiction.
источник