Autômato com pilha embutida

Um autômato com pilha embutida ou EPDA é um modelo computacional para linguagens de parsing geradas por gramáticas de adjunção de árvores (TAGs). Ele é similar ao parsing de autômato com pilha para gramática livre de contexto , exceto que ao invés de usar uma simples pilha para armazenar símbolos, ele tem uma pilha de iterações de pilhas que armazena símbolos, dando às TAGs uma capacidade de geração entre gramáticas livres do contexto e gramáticas sensíveis ao contexto, ou um subconjunto de gramáticas levemente sensíveis ao contexto.

História e aplicações

Autômatos com pilha embutida foram descritos primeiramente por K. Vijay-Shanker em sua tese de doutorado, em 1988. Eles têm sido aplicados desde a descrições mais completas de classes de gramáticas levemente sensíveis ao contexto e têm tido importante papel na extensão e refinamento da hierarquia de Chomsky para esta classe. Várias subgramáticas, tais como uma gramática indexada, podem então ser definidas. Eles também estão começando a exercer um importante papel no processamento de linguagens naturais.

Enquanto linguagens naturais tradicionalmente tem sido analisadas usando gramáticas livres de contexto (veja gramática transformacional e linguística computacional), este modelo (GLCs) não funciona bem para linguagens com dependências cruzadas, como holandês(??), situações para as quais um EPDA se adapta bem. Uma análise detalhada está disponível em.

Teoria

Um EPDA é uma máquina de estados finita com um conjunto de pilhas que podem ser acessadas por elas mesmas através de plhas embutidas. Cada pilha contém elementos do alfabeto de pilha, representado por $\,\Gamma$, e então nós definimos um elemento da pilha por $\,\sigma _{i}\in \Gamma ^{*}$, onde a estrela é Fecho de Kleene do alfabeto.

Cada pilha pode então ser definida em termos de seus elementos, então denotamos a $\,j$-ésimos pilha no autômato, usando um símbolo de cruz dupla: $\,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}$, onde $\,\sigma _{j,k}$ poderia ser o próximo símbolo acessível na pilha. A pilha embutida de $\,m$ pilhas pode então ser denotado por $\,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}$.

Nós definimos um autômato com pilha embutida como uma sétupla (7-tupla)

$\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})$ onde

• $\,Q$ é o conjunto finito de estados;
• $\,\Sigma$ é o conjunto finito do alfabeto de entrada;
• $\,\Gamma$ é o alfabeto finito da pilha;
• $\,q_{0}\in Q$ é o estado inicial;
• $\,Q_{\textrm {F}}\subseteq Q$ é o conjunto de estados finais (ou como chamamos, estados de aceitação);
• $\,\sigma _{0}\in \Gamma$ é o símbolo inicial da pilha
• $\,\delta :Q\times \Sigma \times \Gamma \rightarrow S$ é a função de transição, onde $\,S$ são os subconjuntos finitos de $\,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}$.

Assim, a função de transição pega um estado, o próximo símbolo da cadeia de entrada, e o símbolo do topo da pilha atual e gera o próximo estado, as pilhas que serão empurradas e retiradas para a pilha embutida, o ato de empurrar e retirar da pilha atual, e as pilhas para serem consideradas as pilhas atuais na próxima transição. Mais conceitualmente, a pilha embutida é empurrada e retirada, a pilha atual é opcionalmente empurrada de volta para a pilha embutida, e algumas outras pilhas poderiam que poderiam ser empurradas para o topo da quela, com a última pilha sendo uma leitura da próxima iteração. Portanto, pilhas podem ser empurradas para cima e para baixo na pilha atual. A configuração dada é definida por

$\,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}$

onde $\,q$ é o estado atual, os $\,\Upsilon$s são as pilhas na pilha embutida, com $\,\Upsilon _{m}$, o estado atual, e para a cadeia de entrada $\,x=x_{1}x_{2}\in \Sigma ^{*}$, $\,x_{1}$ é a porção da cadeiajá processada pela máquina e $\,x_{2}$ a porção a ser processada, com sua cabeça sendo o símbolo lido atualmente. Note que a cadeia vazia that $\,\epsilon \in \Sigma$ é implicitamente definicado como um símbolo de término, onde, se a máquina está no estado final, quando cadeia vazia é lida, a cadeia de entrada inteira é aceita; senão, é rejeitada. Tais cadeias aceitas são elementos da linguagem

$\,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}$

onde $\,q_{\textrm {F}}\in Q_{\textrm {F}}$ e $\,\rightarrow _{M}^{*}$ definem a função de transição aplicadass mais vezes que o necessário para analisar a cadeia.