# DC-UFRPE/Licenciatura Plena em Computação/Teoria da Computação/Autômatos de pilha (AP)

Na teoria dos autômatos, um autômato com pilha é um autômato finito com uma memória auxiliar em forma de pilha.

## Operação

Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras:
* Eles podem fazer uso da informação que está no topo da pilha para decidir qual transição deve ser efetuada;
* Eles podem manipular a pilha ao efetuar uma transição.
Autômatos com pilha escolhem uma transição analisando o símbolo atual na cadeia de entrada, o estado atual e o topo da pilha. Máquinas de estados finitos convencionais apenas analisam o símbolo na cadeia de entrada e o estado atual. Autômatos com pilha adicionam a pilha como recurso auxiliar, deste modo, dado um símbolo da cadeia de entrada, o estado atual e um símbolo no topo da pilha, uma transição é selecionada.
Máquinas de estados finitos apenas escolhem um novo estado como resultado da sua transição, já os autômatos com pilha também podem manipular a pilha, como resultado de sua transição. A manipulação é feita através do desempilhamento de um símbolo da pilha ou através do empilhamento de um novo símbolo ao topo da mesma. Alternativamente, um autômato com pilha pode ignorar a pilha e deixá-la como está.
Os autômatos com pilha compreendem a classe das linguagens livres de contexto, de acordo com a Hierarquia de Chomsky e, portanto, são modelos de computação equivalentes às gramáticas livres de contexto.
Um autômato finito com acesso a duas pilhas possui capacidade de computação equivalente ao de uma máquina de Turing.Predefinição:Carece de fontes

## Definição formal

Um autômato de pilha é formalmente definido por uma 6-tupla:
    $M=(Q,\ \Sigma ,\ \Gamma ,\ \Delta ,\ q_{0},\ F)$
Onde:
* $\,Q$ é um conjunto finito de estados.
* $\,\Sigma$ é um conjunto finito de símbolos, denominado alfabeto de entrada.
* $\,\Gamma$ é um conjunto finito de símbolos, denominado alfabeto da pilha.
* $\,\Delta \subseteq (Q\times \Sigma ^{*}\times \Gamma ^{*})\times (Q\times \Gamma ^{*})$ é a relação de transição.
* $\,q_{0}\in \,Q$ é o estado inicial.
* $F\subseteq Q$ é o conjunto de estados finais (ou de aceitação).
Um elemento (p,a,α,q,β) é uma transição de M. Ela significa que M, estando no estado p, com o símbolo a na cadeia de entrada e com o símbolo α no topo da pilha, pode consumir o símbolo a, transitar para o estado q e desempilhar α substituindo-o por β. O ∑* e o Γ* denotam o fecho de Kleene do alfabeto de entrada e da pilha, respectivamente. Portanto, estes componentes são utilizados para formalizar que o autômato de pilha pode consumir qualquer quantidade de símbolos da cadeia de entrada e da pilha.

### Computações

A fim de formalizar a descrição semântica dos autômatos com pilha, introduziremos uma descrição da situação atual. Qualquer 3-upla $(p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}$ é chamada de uma descrição instantânea (ID) de $M$, que inclui o estado atual, a parte da cadeia de entrada que ainda não foi lida e o conteúdo da memória (o cabeçalho é escrito primeiro). A função de transição $\delta$ define a relação origina $\vdash _{M}$ de $M$ na descrição instantânea (ID). Para instruções $(p,a,A,q,\alpha )\in \delta$ existe um passo $(p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )$, para todo $x\in \Sigma ^{*}$ e todo $\gamma \in \Gamma ^{*}$.
Em geral, autômatos com pilha são não determinísticos, o que significa dizer que dada uma descrição instantânea $(p,w,\beta )$ pode haver diversos passos possíveis. Qualquer um desses passos pode ser escolhido durante uma computação. Com a definição acima, em cada passo um símbolo único (localizado no topo da pilha) é retirado e substituído por quantos símbolos forem necessário. Como consequência, nenhum passo é definido quando a pilha está vazia.
Computações dos autômatos com pilha são sequências de passos. A computação começa no estado inicial $q_{0}$com o símbolo inicial da pilha $Z$ na pilha e uma cadeia $w$ na fita de entrada e, portanto, com a descrição inicial $(q_{0},w,Z)$. Há duas maneiras de aceitar: O autômato com pilha aceita tanto por estado final, o que significa que depois de ler sua entrada, o autômato atinge um estado de aceitação (in $F$), quanto por pilha vazia ($\varepsilon$), o que significa que após ler a cadeia de entrada, o autômato esvazia sua pilha. O primeiro modo de aceitação usa a memória interna, os estados, e o segundo modo a memória externa, a pilha.
Definição formal:
* $L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )$ com $f\in F$ e $\gamma \in \Gamma ^{*}\$ (Estado final)
* $N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )$ com $q\in Q\$ (Pilha vazia)
Aqui $\vdash _{M}^{*}$ representa os fechos reflexivos e transitivos da relação origina$\vdash _{M}$ significando qualquer número de passos consecutivos (zero, um ou mais).
Para cada único autômato com pilha, essas duas linguagens não devem ter relação: eles podem ser iguais, mas normalmente não é o caso. Uma especificação do autômato deve também incluir o modo de aceitação pretendido. Entretanto, todos as condições de aceitação de um autômato com pilha definem uma mesma família de linguagem
Teorema Para todo autômato com pilha $M$ é possível construir um outro autômato com pilha $M'$ tal que $L(M)=N(M')$, e vice versa, para cada autômato com pilha $M$ é possível construir um autômato com pilha $M'$ tal que $N(M)=L(M')$

## Exemplo

A seguir é a descrição formal do AP, que reconhece a linguagem $\{0^{n}1^{n}\mid n\geq 0\}$ por estado final:
$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ p,\ Z,\ F)$, onde
$Q=\{p,q,r\}$
$\Sigma =\{0,1\}$
$\Gamma =\{A,Z\}$
$F=\{r\}$
$\delta$ consiste nas seis instruções seguintes:
$(p,0,Z,p,AZ)$, $(p,0,A,p,AA)$, $(p,\epsilon ,Z,q,Z)$, $(p,\epsilon ,A,q,A)$, $(q,1,A,q,\epsilon )$, e $(q,\epsilon ,Z,r,Z)$.
Ou seja, no estado $p$ para cada símbolo $0$ que for lido, um $A$ é colocado na pilha. Empilhar um símbolo $A$ no topo de um outro $A$ é formalizado como trocar o símbolo $A$ por $AA$. No estado $q$, para cada símbolo $1$ lido, um $A$ a é desempilhado. Em um outro momento, o autômato se move do estado $p$ para o estado $q$, enquanto ele pode mover do estado $q$ para o estado de aceitação $r$ somente quando a pilha possuir um único $Z$.
Representamos a instrução $(p,a,A,q,\alpha )$ como uma ponte que sai do estado $p$ para o estado $q$ rotulada por $a;A/\alpha$ (leia $a$; substitui $A$ por $\alpha$).

## Entendendo o processo de computação

A seguir ilustramos como o AP acima computa sobre diferentes cadeias de entrada.
(a) Cadeia de entrada = 0011. Há várias computações, dependendo do momento em que é feita a mudança do estado $p$ para o estado $q$. Apenas uma dessas computações aceita.
    (i) $(p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)$. O estado final é o de aceitação, mas a entrada não é aceita pois a cadeia não terminou de ser lida completamente.
    (ii) $(p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)$. Não há mais estados possíveis..
    (iii) $(p,0011,Z)\vdash (p,011,AZ)\vdash (p,11,AAZ)\vdash (q,11,AAZ)$ $\vdash (q,1,AZ)\vdash (q,\epsilon ,Z)$ $\vdash (r,\epsilon ,Z)$. Computação de aceitação: termina em um estado de aceitação e a cadeia de entrada é lida totalmente.
(b) Cadeia de entrada = 00111. Novamente, há várias computações, mas nenhuma delas é uma computação de aceitação.
    (i) $(p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)$. O estado final é o de aceitação, mas a entrada não é aceita já que não foi lida.
    (ii) $(p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)$. Não há mais estados possíveis.
    (iii) $(p,00111,Z)\vdash (p,0111,AZ)\vdash (p,111,AAZ)\vdash (q,111,AAZ)$ $\vdash (q,11,AZ)\vdash (q,1,Z)$ $\vdash (r,1,Z)$. O estado final é o de aceitação, mas a entrada não é aceita pois a cadeia não terminou de ser lida completamente.

## AP e Linguagens livres de contexto

Toda gramática livre de contexto pode ser transformada em um autômato com pilha equivalente. O processo de derivação da gramática é simulada de uma forma mais à esquerda. Onde a gramática reescreve um não-terminal, o AP toma o não-terminal do topo da pilha pilha e substitui-la pelo lado direito de uma regra gramatical. Onde a gramática gera um símbolo terminal, o PDA lê um símbolo de entrada quando é o símbolo mais alto na pilha. De certa forma, a pilha do PDA contém os dados não transformados da gramática, correspondente a um percurso pré-ordem de uma árvore de derivação.
Tecnicamente, dada uma gramática livre de contexto, o AP é construído da seguinte forma:
* $(1,\varepsilon ,A,1,\alpha )$ para cada regra $A\to \alpha$ (expand)
* $(1,a,a,1,\varepsilon )$ para cada símbolo de terminal $a$ (match)
Como resultado, obtemos um autômato com pilha de um único estado. O estado aqui é $1$, aceitando a linguagem livre de contexto por pilha vazia. O símbolo inicial da pilha é igual ao axioma da gramática livre do contexto.
O inverso, encontrar uma gramática para um AP dado, não é tão simples. O truque é codificar dois estados do AP em símbolos não-terminais da gramática.
Teorema Para cada autômato com pilha $M$ é possível construir uma gramática livre do contexto $G$ tal que $N(M)=L(G)$.

## Autômato com Pilha Generalizado

Um Autômato com Pilha Generalizado APG é um AP que escreve uma cadeia inteira de um tamanho qualquer conhecido na pilha ou remove uma cadeia inteira da pilha em um único passo.
Um APG é formalmente definido como uma 6-upla:
    $M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)$
onde Q, $\Sigma \,$, $\Gamma \,$, q$_0$ e F são definidos da mesma forma que um AP.
    $\,\delta$: $Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow P(Q\times \Gamma ^{*})$
é a função de transição.
Regras de computação para um APG são as mesmas que para AP, exceto que a$_{i+1}$'s e b$_{i+1}$'s são agora cadeias ao invés de símbolos.
APGs e APs são equivalentes, ou seja, se uma linguagem é reconhecida por um AP, ela também é reconhecida por um APG, e vice-versa.
Podemos formular uma prova analítica da equivalência entre APGs e APs usando a seguinte simulação:
Faça $\delta$(q$_1$, w, x$_1$x$_2$...x$_m$) $\longrightarrow$ (q$_2$, y$_1$y$_2$...y$_n$) ser uma transição do APG
Onde $q_{1},q_{2}\in Q$, $w\in \Sigma _{\epsilon }$, $x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{*}$, $m\geq 0$, $y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{*}$, $n\geq 0$.
Construa as seguintes transições para o AP:
       $\delta ^{'}$(q$_1$, w, x$_1$) $\longrightarrow$ (p$_1$, $\epsilon$)
       $\delta ^{'}$(p$_1$, $\epsilon$, x$_2$) $\longrightarrow$ (p$_2$, $\epsilon$)
             $\vdots$
       $\delta ^{'}$(p$_{m-1}$, $\epsilon$, x$_m$) $\longrightarrow$ (p$_m$, $\epsilon$)
       $\delta ^{'}$(p$_m$, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (p$_{m+1}$, y$_n$)
       $\delta ^{'}$(p$_{m+1}$, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (p$_{m+2}$, y$_{n-1}$)
             $\vdots$
       $\delta ^{'}$(p$_{m+n-1}$, $\epsilon$, $\epsilon$ ) $\longrightarrow$ (q$_2$, y$_1$)

## Softwares

* SCTMF- Software para Criação e Teste de Modelos Formais.
* JFlap- Software americano para testes com interface gráfica.
Predefinição:Teoria da computação