Autômato com pilha
Na teoria dos autômatos, um autômato com pilha é um autômato finito com uma memória auxiliar em forma de pilha.
Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras: 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á.
Um autômato de pilha é formalmente definido por uma 6-tupla: 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 , β ) ∈ Q × Σ ∗ × Γ ∗ {\displaystyle (p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}} é chamada de uma descrição instantânea (ID) de M {\displaystyle 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 δ {\displaystyle \delta } define a relação origina ⊢ M {\displaystyle \vdash _{M}} de M {\displaystyle M} na descrição instantânea (ID). Para instruções ( p , a , A , q , α ) ∈ δ {\displaystyle (p,a,A,q,\alpha )\in \delta } existe um passo ( p , a x , A γ ) ⊢ M ( q , x , α γ ) {\displaystyle (p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )} , para todo x ∈ Σ ∗ {\displaystyle x\in \Sigma ^{*}} e todo γ ∈ Γ ∗ {\displaystyle \gamma \in \Gamma ^{*}} .
A seguir é a descrição formal do AP, que reconhece a linguagem { 0 n 1 n ∣ n ≥ 0 } {\displaystyle \{0^{n}1^{n}\mid n\geq 0\}} por estado final: M = ( Q , Σ , Γ , δ , p , Z , F ) {\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ p,\ Z,\ F)} , onde Q = { p , q , r } {\displaystyle Q=\{p,q,r\}} Σ = { 0 , 1 } {\displaystyle \Sigma =\{0,1\}} Γ = { A , Z } {\displaystyle \Gamma =\{A,Z\}} δ {\displaystyle \delta } consiste nas seis instruções seguintes: ( p , 0 , Z , p , A Z ) {\displaystyle (p,0,Z,p,AZ)} , ( p , 0 , A , p , A A ) {\displaystyle (p,0,A,p,AA)} , ( p , ϵ , Z , q , Z ) {\displaystyle (p,\epsilon ,Z,q,Z)} , ( p , ϵ , A , q , A ) {\displaystyle (p,\epsilon ,A,q,A)} , ( q , 1 , A , q , ϵ ) {\displaystyle (q,1,A,q,\epsilon )} , e ( q , ϵ , Z , r , Z ) {\displaystyle (q,\epsilon ,Z,r,Z)} . Ou seja, no estado p {\displaystyle p} para cada símbolo 0 {\displaystyle 0} que for lido, um A {\displaystyle A} é colocado na pilha. Empilhar um símbolo A {\displaystyle A} no topo de um outro A {\displaystyle A} é formalizado como trocar o símbolo A {\displaystyle A} por A A {\displaystyle AA} . No estado q {\displaystyle q} , para cada símbolo 1 {\displaystyle 1} lido, um A {\displaystyle A} a é desempilhado. Em um outro momento, o autômato se move do estado p {\displaystyle p} para o estado q {\displaystyle q} , enquanto ele pode mover do estado q {\displaystyle q} para o estado de aceitação r {\displaystyle r} somente quando a pilha possuir um único Z {\displaystyle Z} .
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 {\displaystyle p} para o estado q {\displaystyle q} . Apenas uma dessas computações aceita. (b) Cadeia de entrada = 00111. Novamente, há várias computações, mas nenhuma delas é uma computação de aceitação.
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: Como resultado, obtemos um autômato com pilha de um único estado. O estado aqui é 1 {\displaystyle 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.
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: onde Q, Σ {\displaystyle \Sigma \,} , Γ {\displaystyle \Gamma \,} , q0 e F são definidos da mesma forma que um AP. Regras de computação para um APG são as mesmas que para AP, exceto que ai+1's e bi+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 δ {\displaystyle \delta } (q1, w, x1x2...xm) ⟶ {\displaystyle \longrightarrow } (q2, y1y2...yn) ser uma transição do APG Onde q 1 , q 2 ∈ Q {\displaystyle q_{1},q_{2}\in Q} , w ∈ Σ ϵ {\displaystyle w\in \Sigma _{\epsilon }} , x 1 , x 2 , … , x m ∈ Γ ∗ {\displaystyle x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{*}} , m ≥ 0 {\displaystyle m\geq 0} , y 1 , y 2 , … , y n ∈ Γ ∗ {\displaystyle y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{*}} , n ≥ 0 {\displaystyle n\geq 0} .
