Existem variantes de autômatos de empilhamento visíveis que permitem inserir palavras na pilha?

Pergunto-me, existem documentos ou pesquisas que tratem de autômatos visivelmente pushdown, mas permitindo que palavras, em vez de letras únicas, sejam empurradas para a pilha.

Como alternativa, uma construção que permitisse que os símbolos fossem inseridos nas transições poderia atingir o mesmo objetivo. $\epsilon$

Obviamente, essas variações podem ser formadas, mas estou me perguntando se isso arruina as propriedades de fechamento e decidibilidade que tornam os VPAs interessantes.

Eu estou olhando para uma construção em que use a pilha como um contador, incrementando-a por constantes com base nos símbolos iniciais lidos e depois fazendo a contagem regressiva com base em outros símbolos lidos.

Para quem não sabe, os autômatos visivelmente pushdown são aqueles em que o alfabeto pode ser dividido em símbolos push, popping e símbolos que não afetam a pilha. A escolha de empurrar contra estalar é inteiramente determinada pelo símbolo atual que está sendo lido. Eles estão fechados sob interseção, união, concatenação, estrela e complemento, dando a eles uma riqueza de propriedades decidíveis. Veja este documento para mais informações.

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

parece que a pergunta óbvia é se esses autômatos são equivalentes aos autômatos de empilhamento padrão com as "palavras" convertidas em sequências de estados? afaik, sim? caso contrário, um exemplo ilustrativo de um caso em que falha seria útil.

vzn 19/07/2013

@vzn Eles não podem ser equivalentes. Esses PDAs visivelmente parecem ser estritamente mais fracos. A última vez que verifiquei, as CFLs não foram fechadas sob interseção.

Kai

Portanto, os VPDAs são fechados sob interseção e são conhecidos por estar adequadamente entre e . No entanto, não tenho idéia se minha variante está fechada sob interseção, portanto, pode ser equivalente. Duvido que seja, mas não tenho certeza.

R E G

$REG$

D C F L

$DCFL$

jmite

Este documento dx.doi.org/10.1145/1516512.1516518 fornece uma caracterização gramatical de VPDAs e uma construção para a conversão entre as gramáticas e VPDAs. Possivelmente a gramática pode ser usada para simular o envio de palavras inteiras?

Evgenij Thorstensen

Por que pressionar uma palavra em um símbolo seria equivalente a permitir empurrões nas transições eps?

23613 domotorp

Respostas:

Com empurra epsilon

Para a versão com empurrões nas transições epsilon, a prova indecidível da universalidade dos autômatos de empilhamento pode ser adaptada a essa nova configuração, de modo que perdemos pelo menos as seguintes propriedades: fechamento sob complementação, determinabilidade, decidibilidade da universalidade e inclusão.

Esquema de prova: Pegue uma máquina de Turing , queremos construir um VPA com empilhamento épsilon, de modo que seja universal se e somente se M não tiver execução aceitável. $M$ $A$

Nós projetamos modo que uma palavra não seja aceita se, e somente ela, tiver a forma: $A$

onde

# C_{0 0} & C_{0 0} $ (\bar{C_{0 0}})^{R} # C_{1 1} & C_{1 1} $ (\bar{C_{1 1}})^{R} # C_{2} & C_{2} $ (\bar{C_{2}})^{R} ... # 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$

Cada codifica uma configuração válida de $C_i$ $M$
é inicial, está aceitando $C_0$ $C_n$
é o inverso de uma palavra $u^R$ $u$
é uma cópia deusando letras pop $\overline{u}$ $u$
são símbolos especiais de separação que não estão no alfabeto de $\#,\&,\$$ $M$
é sempre uma transição válida de $C_i\to C_{i+1}$ $M$

O VPA é forçado a fazer pop em fatores da forma . não pode determinar de maneira determinística uma violação de nenhuma das propriedades e verificá-la. A chave é que ele pode pressionar ou não fazer nada, o que permite verificar todas as condições (na verdade, acho que suas violações). Em particular, pode-se adivinhar que a primeira (ou segunda) ocorrência de não corresponde , ignorando o outro componente. Também pode adivinhar que $A$ $C_i^R$ $A$ $C_i$ $C_i$ $(\overline{C_i})^R$ $C_i\to C_{i+1}$ não é uma transição válida, pressionando as duas ocorrências de , em seguida, exibindo uma, não pressione e compare com o conteúdo da pilha. Por outro que não são parte da suposição, um componente é empurrado e o é ser exibido. $C_i$ $C_{i+1}$ $(\overline{C_{i+1}})^R$ $C_j$ $(\overline{C_j})^R$

Empurrando palavras

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

Denis
fonte