Существуют ли варианты визуально выпадающих автоматов, которые позволяют помещать слова в стек?

Мне интересно, есть ли какие-либо статьи или исследования, посвященные явно выталкивающим автоматам, но позволяющие помещать слова, а не отдельные буквы, в стек.

С другой стороны, конструкция, которая позволяла нажимать символы на $\epsilon$ переходы, могла бы достичь той же цели.

Очевидно, что такие вариации могут быть сформированы, но мне интересно, разрушает ли это свойства замыкания и разрешимости, которые делают VPA интересными.

Я смотрю на конструкцию, в которой стек используется в качестве счетчика, увеличивая его на константы на основе начальных прочитанных символов, а затем производя обратный отсчет на основе других прочитанных символов.

Для тех, кто не знает, очевидно, что автоматы «пуш-ап» - это те, в которых алфавит можно разделить на символы толчка, символы выталкивания и символы, не влияющие на стек вообще. Выбор нажатия или выталкивания полностью определяется текущим символом, который читается. Они закрыты на пересечении, объединении, объединении, звезде и дополнении, что дает им множество разрешимых свойств. Смотрите эту статью для получения дополнительной информации.

reference-request fl.formal-languages automata-theory context-free context-free-languages jmite
источник

Кажется очевидным вопрос: эквивалентны ли такие автоматы стандартным автоматам с понижением «слова», преобразованным в последовательности состояний? афаик, да? если нет, то будет полезен иллюстративный пример случая, когда он терпит неудачу.

1913 года

@vzn Они не могут быть эквивалентными. Эти явно КПК кажутся более слабыми. В прошлый раз, когда я проверял, КЛЛ не были закрыты на пересечении.

Кай

Так, VPDAs закрыты под пересечением, и , как известно, должным образом между

. Тем не менее, я понятия не имею, если мой вариант закрыт на пересечении, поэтому он может быть эквивалентным. Я сомневаюсь, что это так, но я не уверен.

R E G

$REG$

D C F L

$DCFL$

jmite

В этой статье dx.doi.org/10.1145/1516512.1516518 дается грамматическая характеристика VPDA и конструкция для преобразования между грамматиками и VPDA. Возможно, грамматику можно использовать для симуляции нажатия целых слов?

Евгений Торстенсен

Почему нажатие слова на символ эквивалентно разрешению нажатия на eps-переходы?

Домоторп

Ответы:

С эпсилон толчками

Для версии с толчками на эпсилон-переходах доказательство неразрешимости универсальности pushdown-автоматов может быть адаптировано к этому новому параметру, поэтому мы теряем по крайней мере следующие свойства: замыкание при дополнении, определимость, разрешимость универсальности и включение.

Схема доказательства: возьмем машину Тьюринга , мы хотим построить VPA с эпсилон-толчками так, чтобы он был универсальным тогда и только тогда, когда у M нет принимающего пробега. $M$ $A$

Мы проектируем , что слово не принимается, если и только оно имеет форму: $A$

где

# C_{0} & C_{0} $ (\bar{C_{0}})^{R} # C_{1} & C_{1} $ (\bar{C_{1}})^{R} # C_{2} & C_{2} $ (\bar{C_{2}})^{R} \dots # C_{n} & C_{n} $ (\bar{C_{n}})^{R}

$\#C_0\&C_0\$(\overline{C_0})^R\#C_1\&C_1\$(\overline{C_1})^R\#C_2\&C_2\$(\overline{C_2})^R\dots\#C_n\&C_n\$(\overline{C_n})^R$

Каждый кодирует действительную конфигурацию $C_i$ $M$
является начальным, принимает $C_0$ $C_n$
обратное слово $u^R$ $u$
является копиейпомощью попбуквы $\overline{u}$ $u$
являются специальными символами разделения не в алфавите $\#,\&,\$$ $M$
всегда допустимый переход $C_i\to C_{i+1}$ $M$

VPA вынужден делать поп на факторы вида . может недетерминированно угадать нарушение любого свойства и проверить его. Ключ в том, что он может либо нажать на , либо ничего не делать, что позволяет проверить все условия (фактически угадать их нарушения). В частности, можно предположить , что первый (или второй) вхождение не соответствует , игнорируя другой компонент. Также можно догадаться, что $A$ $C_i^R$ $A$ $C_i$ $C_i$ $(\overline{C_i})^R$ $C_i\to C_{i+1}$ это недопустимый переход, нажав оба вхождения , затем нажав один, не нажимая $C_i$ $C_{i+1}$ $(\overline{C_{i+1}})^R$ $C_j$ $(\overline{C_j})^R$

Толкая слова

$(S,R,u)$ $u\in A^*$ является префиксом слова, которое может быть передано в соответствии с функцией перехода. При совании письма $a$ , $(S,R,va)$ превращается в $(S',R',v)$ , где $S'$ и $R'$ обновляются нормально, чтобы отразить текущее состояние конструкции блока питания. Тем не менее, на этот раз мы априори получаем детерминированный автомат нажатия, который не является явно нажатием. По крайней мере, это означает, что эквивалентность и универсальность разрешимы.

Денис
источник