Existe-t-il des variantes d'automates visiblement pushdown qui permettent de pousser des mots sur la pile?

Je me demande s'il y a des articles ou des recherches traitant des automates visiblement pushdown, mais permettant aux mots, plutôt qu'aux lettres simples, d'être poussés sur la pile.

Alternativement, une construction qui a permis de symboles d'être poussé sur $\epsilon$ -Transitions pourrait atteindre le même objectif.

De toute évidence, de telles variations peuvent se former, mais je me demande si cela ruine les propriétés de fermeture et de décidabilité qui rendent les APV intéressants.

Je regarde une construction où utiliser la pile comme compteur, l'incrémenter par des constantes basées sur les symboles initiaux lus, puis décompter en fonction des autres symboles lus.

Pour ceux qui ne le savent pas, les automates visiblement déroulants sont ceux où l'alphabet peut être divisé en symboles poussants, symboles popping et symboles n'affectant pas du tout la pile. Le choix de pousser ou de sauter est entièrement déterminé par le symbole actuel lu. Ils sont fermés sous l'intersection, l'union, la concaténation, l'étoile et le complément, ce qui leur donne une multitude de propriétés décidables. Consultez cet article pour en savoir plus.

reference-request fl.formal-languages automata-theory context-free context-free-languages jmite
la source

il semble que la question évidente est de savoir si ces automates sont équivalents aux automates de refoulement standard avec les "mots" convertis en séquences d'états? afaik, oui? sinon, un exemple illustratif d'un cas où il échoue serait utile.

vzn

@vzn Ils ne peuvent pas être équivalents. Ces PDA visiblement semblent être plus faibles. La dernière fois que j'ai vérifié, les LFC n'étaient pas fermées sous l'intersection.

Kai

Ainsi, VPDAs sont fermés sous intersection, et sont connus pour être correctement entre

. Cependant, je n'ai aucune idée si ma variante est fermée sous intersection, elle pourrait donc être équivalente. J'en doute, mais je ne suis pas sûr.

R E G

$REG$

D C F L

$DCFL$

jmite

Cet article dx.doi.org/10.1145/1516512.1516518 donne une caractérisation grammaticale des VPDA et une construction pour la conversion entre les grammaires et les VPDA. Peut-être que la grammaire peut être utilisée pour simuler la poussée de mots entiers?

Evgenij Thorstensen

Pourquoi pousser un mot sur un symbole équivaudrait-il à autoriser des poussées sur les transitions eps?

domotorp

Réponses:

Avec epsilon pousse

Pour la version avec pushs sur epsilon-transitions, la preuve d'indécidabilité de l'universalité des pushdown-automata peut être adaptée à ce nouveau paramètre, nous perdons donc au moins les propriétés suivantes: fermeture sous complémentation, déterminisabilité, décidabilité de l'universalité et inclusion.

Schéma de preuve: Prenez une machine de Turing , nous voulons construire un VPA avec epsilon-push de sorte qu'il soit universel si et seulement si M n'a pas de cycle d'acceptation. $M$ $A$

Nous concevons tel qu'un mot n'est pas accepté si et seulement il est de la forme: $A$

où

# 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$

Chaque code une configuration valide de $C_i$ $M$
est initial, $C_0$ accepte $C_n$
$u^R$ est l'inverse d'un mot $u$
$\overline{u}$ est une copie de utilisant des lettres pop $u$
sont des symboles de séparation spéciaux qui ne sont pas dans l'alphabet de $\#,\&,\$$ $M$
est toujours une transition valide de $C_i\to C_{i+1}$ $M$

Le VPA est obligé de faire du pop sur des facteurs de la forme . peut deviner de manière non déterministe une violation de l'une ou l'autre propriété et la vérifier. La clé est qu'il peut soit appuyer sur , soit ne rien faire, ce qui permet de vérifier toutes les conditions (en fait deviner leurs violations). En particulier, il peut deviner que la première (ou la seconde) occurrence de ne correspond pas à , en ignorant l'autre composante. On peut aussi deviner que $A$ $C_i^R$ $A$ $C_i$ $C_i$ $(\overline{C_i})^R$ $C_i\to C_{i+1}$ n'est pas une transition valide, en poussant les deux occurrences de $C_i$ , puis en éclatant une, en poussant non et en comparant au contenu de la pile. Pour les autres qui ne font pas partie de la supposition, un composant est poussé et le est sauté. $C_{i+1}$ $(\overline{C_{i+1}})^R$ $C_j$ $(\overline{C_j})^R$

Pousser des mots

$(S,R,u)$ $u\in A^*$ $a$ $(S,R,va)$ $(S',R',v)$ $S'$ $R'$

Denis
la source