Доказательство замыкания при обращении языков, принятых автоматами min-heap

16

Это дополнительный вопрос этого .

В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что набор языков, принимаемых такими машинами ( HAL ), не является ни подмножеством, ни надмножеством набора языков без контекста. Учитывая успешное разрешение и очевидный интерес к этому вопросу, я перехожу к нескольким последующим вопросам.

Известно, что обычные языки закрыты под различными операциями (мы можем ограничиться базовыми операциями, такими как объединение, пересечение, дополнение, различие, конкатенация, звезда Клини и обращение), тогда как языки без контекста имеют другое закрытие свойства (они закрыты под объединением, конкатенацией, звездой Клини и обращением).

HAL закрыт при обращении?

Patrick87
источник
Каковы виды использования таких машин? Или это академическое упражнение?
Дэйв Кларк,
@DaveClark Ну, в основном это академическое упражнение (насколько я знаю, я просто придумал их в связанном вопросе). Однако они могут выполнять вычисления так же, как и другие машины (DFA, TM и т. Д.), Поэтому, возможно, их можно было бы использовать.
Patrick87
Этот вопрос показывает, почему вы хотите, чтобы ваши автоматы сопровождались грамматикой. Арр, мой мозг!
Рафаэль
4
Я пытался доказать это, используя язык формата , но это заняло слишком много времени, и я сдался. Может быть, эта идея поможет кому-нибудь. {xyy is a lexicographically sorted copy of x}
Ран Г.
@RanG .: Я думаю, что это должно работать. Я рад присуждать награду за ответ, который доказывает, что язык написан на языке и дает убедительные аргументы в пользу того, что это не так. HAL
Рафаэль

Ответы:

4

Рассмотрим язык (где # 0 ( x ) обозначает количество нулей в x ).

L×2={xyzx,y,z{0,1},#0(x)=#0(y) and |x|+|y|=z}
#0(x)x

Легко определить с помощью машины HAL - обратите внимание, что машине необходимо отслеживать два свойства: количество нулей в x против y и длину x , y (против z ). Он может помещать a в кучу для каждого нуля, который он видит в x (и затем позже высовывать любой ноль, видимый в y ); кроме того, он выдвигает любой бит в x , y (и позже появляется для любого бита z ). Так как все s выталкиваются в кучу, они не мешают подсчету. L×2xyx,yz0x0y1x,y1z10 служит разделителем и может быть практически проигнорирован.

Теперь пусть , обратный язык. То есть L = { z y x x , y , z { 0 , 1 } , # 0 ( x ) = # 0 ( y )  и  | х | + | у | = Г } Покажем , что ни HAL машина не может решить , L .L=L×2R

L={zyxx,y,z{0,1},#0(x)=#0(y) and |x|+|y|=z}
L

Интуиция заключается в следующем. Как и выше, машина должна отслеживать как длину и количество нулей в x , y . Однако в этом случае необходимо отслеживать их одновременно . Это не может быть сделано через кучу. Более подробно, после прочтения z , куча содержит информацию о длине | х | + | у | , при чтении y машина также должна держать в куче количество нулей в y . Однако эта информация не может влиять на информацию, которую куча уже имеет на ожидаемой нами длине xzx,yz|x|+|y|yyx быть. Очень интуитивно, либо информация о количестве нулей будет «ниже» информации о длине , и тогда мы не сможем получить к ней доступ при чтении х , либо она «выше» этой информации, делая последнюю недоступной, или две информации будут «смешаны» и станут бессмысленными.xx

Более формально, мы собираемся использовать какой-то «насосный» аргумент. То есть мы возьмем очень длинный ввод и покажем, что «состояние» машины должно повторяться во время обработки этого ввода, что позволит нам «заменить» ввод, когда машина повторяет свое «состояние».

Для формального доказательства нам нужно упростить структуру машины HAL, а именно, что она не содержит «петли» переходов 1 . Исходя из этого предположения, мы видим, что для каждого входного символа, который обрабатывает машина, содержимое кучи может увеличиваться / уменьшаться не более чем сε1c (для некоторой достаточно большой константы ).c

Доказательство.
Предположим , решает , L , и рассмотрим достаточно долго вход (скажем, длиной 4 л , при этом | х | = | у | = п , | г | = 2 п , не обращая внимания на сек и далее). Чтобы быть конкретным, зафиксируем z , y и предположим, что # 0 ( y ) = n / 2 . Обратите внимание, что есть ( пHL4n|x|=|y|=n|z|=2nz,y#0(y)=n/2различнаяй«ы такиечтогухL.(nn/2)xzyxL

Рассмотрим содержимое кучи сразу после обработки . Он содержит не более 3 n c символов (где каждый символ из фиксированного алфавита Γ ), по нашему предположению. Тем не менее, есть ( пzy3ncΓ(nn/2)xsx1,x2

  1. n/2x1x2
  2. By the time the machine reads a prefix of length n/2 of the x part, the heap looks the same for both x1 and x2, and also, the machine is in the same state (this must happen for some x1,x2, for large enough n, as there are more than 20.8n different options2 for x1,x2, and at most (3.5cn)|Γ||Q| different options for heap content and state3).

It is clear that the machine must accept the word zyx1px2s, where x1p is a prefix of x of length n/2 and x2s is a suffix of x2 of the same length. Note that the number of zeros in x1px2s 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.

1 Does this assumption damages generality? I don't think so, but this indeed requires a proof. If someone sees how to get around this extra assumption, I'd love to know.
2 Let's fix x1 so that it's prefix (of length n/2 has exactly n/4 zeros). Recall that using Stirling's approximation we know that log(nk)nH(k/n) where H() is the Binary entropy funciton. Since H(1/4)0.81 we have (nn/4)>20.8n for large enough n.
3 Assuming alphabet Γ, there are |Γ|n different strings of length n, so if this was a stack we were screwed. However, pushing "01" into a heap is equivalent to pushing "10" - the heap stores only the sorted version of the content. The number of different sorted strings of size n is (n+1|Γ|1)n|Γ|, for a constant |Γ|.

Ran G.
источник
Nice! Will have to read the formal part again later. 1) Ad ¹: See also here. 2) The argument breaks down if we allow non-deterministic choice of the returned heap symbol (among all symbols of the same priority).
Raphael