Parte 7

Prévia do material em texto

Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Texto base 
7 
 
Teoria da Computação 
Ana Paula Ferreira da Rocha 
Resumo 
A transição para um novo estado permite realizar os movimentos sem consumir qualquer 
caractere da entrada quando utilizamos a teoria de epsilon ou movimentos vazios, este 
tipo de transição fornece de maneira convincente a modelagem de sistemas cujo estados 
atuais não são conhecidos com precisão. Associada a teoria dos autômatos com pilha 
conseguimos um aumento do poder computacional, sendo o autômato com pilha um 
formalismo da classe de linguagens livres de contexto e semelhante ao autômato finito, 
teremos um resultado interessante já que qualquer linguagem livre do contexto pode ser 
reconhecida por um autômato com pilha utilizando apenas um estado para este 
reconhecimento. 
Introdução 
 Abordaremos a teoria das transições em epsilon, também conhecida como 
movimentos vazios e dos autômatos em pilha. Você verá a relação entre as duas teorias e 
suas equivalências bem como o poder computacional que podemos ter com os algoritmos 
utilizando ambas as teorias. 
 
 
7.1. Transições em epsilon 
Na teoria dos autômatos, um autômato finito não determinístico com transições ε (AFN-
ε) (também conhecido como AFN-λ), é uma extensão (variação) de um autômato finito 
não determinístico (AFND), que permite a transição para um novo estado sem consumir 
qualquer caractere da entrada. As transições que não consomem nenhum caractere de 
entrada são chamadas de transições ε ou transições λ. Transições ε fornecem uma maneira 
conveniente de modelagem de sistemas cujos estados atuais não são conhecidos com 
precisão. Uma vez que um AFN-ε sempre pode ser transformado em um AFN, as 
propriedades testadas nos AFN-ε são igualmente válidas para AFNs. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Devemos observar que os autômatos finitos não determinísticos com transições ε também 
são chamados de autômatos finitos com movimentos vazios. Movimentos vazios 
generalizam os movimentos não determinísticos. Um movimento vazio é uma transição 
sem a leitura de símbolo da fita. Pode ser interpretado como um não determinismo interno 
ao autômato, constituindo uma transição encapsulada, executando-se por uma eventual 
mudança de estados, nada mais pode ser observado sobre um movimento vazio. Uma das 
vantagens dos autômatos finitos com movimentos vazios no estudo das linguagens 
formais é o fato de facilitarem algumas construções e demonstrações relacionadas com 
os autômatos. 
No caso dos autômatos finitos a facilidade de movimentos vazios não aumenta o poder 
de reconhecimento de linguagens, qualquer autômato finito com movimentos vazios pode 
ser simulado por um autômato finito não determinístico. 
Um AFN-ε ou simplesmente autômato finito com movimentos vazios M é uma 5-upla 
ordenada: 
 M = (∑, Q, 𝜹, q0, F) 
Onde: 
• ∑ é um alfabeto de símbolos de entrada; 
• Q é um conjunto de estados possíveis do autômato o qual é finito; 
• 𝜹 é uma função programa, ou ainda função de transição: 
 𝜹: Q x (∑ ∪ {𝜺}) → 2Q 
• A qual é uma função total, assim para um estado p e o símbolo especial 𝜺: 
 𝜹(p, 𝜺) = {q1, q2, ..., qn} 
• É um movimento vazio ou transição vazia do autômato; 
• q0 é um elemento distinguido de Q, denominado estado inicial; 
• F é um subconjunto de Q, denominado conjunto de estados finais. 
Portanto executando-se pela função programa 𝜹 as componentes ∑, Q, F e q0 são como 
na definição de AFN. 
A representação da função programa como um diagrama é semelhante à do autômato 
finito não determinístico, por exemplo supondo que: 
 𝜹(q, 𝜺) = {p0} 𝜹(q, a1) = {p1} ... 𝜹(q, an) = {pn} 
Já a representação do diagrama seria: 
 
Figura 1.1 – Diagrama AFN-𝜺 – função programa com movimentos vazios 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Fonte: Paulo Blauth Menezes, 2011. 
A computação de um autômato finito com movimentos vazios é semelhante à de um 
autômato finito não determinístico, adicionalmente o processamento de uma transição 
para uma entrada vazia também é não determinístico. Assim um AFN-𝜺 ao processar uma 
entrada vazia assume simultaneamente os estados destino e origem. Portanto a origem de 
um movimento vazio é sempre um caminho alternativo. 
Autômato finito com movimentos vazios: a’s antecedem b’s 
Considere a seguinte linguagem sobre o alfabeto {a, b}: 
 L7 = {w | qualquer símbolo a antecede qualquer símbolo b} 
O autômato finito com movimentos vazios: 
 M7 = ({a, b}, {q0, qf}, 𝜹7, q0, {qf}) 
Onde 𝜹7 é dada conforme tabela abaixo: 
 
Tabela 1.1 – Função programa AFN-𝜺 – qualquer símbolo a antecede qualquer símbolo b 
𝜹7 a b 𝜺 
q0 {q0} ∅ {qf} 
qf ∅ {qf} ∅ 
Fonte: Paulo Blauth Menezes, 2011. 
 
Tal que ACEITA(M7) = L7 conforme demonstrado pela figura abaixo: 
 
Figura 1.2 – Diagrama AFN-𝜺 – qualquer símbolo a antecede qualquer símbolo b 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
A definição formal das computações de um autômato finito com movimentos vazios, é 
facilitada se primeiro for definida a computação exclusivamente de transições vazias, 
desde um estado ou de um conjunto finito de estados. 
 
Computação vazia 
Seja M = (∑, Q, 𝜹, q0, F) um autômato finito com movimentos vazios. 
• A computação vazia ou função fecho vazio, a partir de um estado é representada 
por: 
 𝜹𝜺: Q ⟶ 2Q 
É definida como segue: 
 𝜹𝜺(q) = {q} ∪ 𝜹(q, 𝜺) ∪ (∪p∈ 𝜹(q,𝜺)𝜹𝜺(p)) 
Portanto 𝜹𝜺(q) = {q} se 𝜹(q, 𝜺) = ∅ ou seja indefinida; 
• A computação vazia ou função fecho vazio, desde um conjunto de estados finito 
é representada por: 
 𝜹𝜺*: 2Q ⟶ 2Q 
É tal que: 
 𝜹𝜺*(P) = ∪ q∈P 𝜹𝜺(q) 
Como sempre por simplicidade as funções 𝜹𝜺 e 𝜹𝜺* são ambas representadas por 𝜹𝜺. 
Considere o autômato finito com movimentos vazios M7, o mesmo utilizado na definição 
autômato finito com movimentos vazios: a’s antecedem b’s, então: 
 𝜹𝜺(q0) = {q0, qf} 
 𝜹𝜺(qf) = {qf} 
 𝜹𝜺({q0, qf}) = {q0, qf} 
A computação de um autômato finito com movimentos vazios, para uma palavra de 
entrada w, consiste na sucessiva aplicação da função programa para cada símbolo de w, 
da esquerda para a direita, cada passo de aplicação intercalado com computações vazias, 
até ocorrer uma condição parada. Assim para cada conjunto de estados alternativos 
assumido pelo autômato, antes de processar a próxima transição, é necessário determinar 
todos os demais estados atingíveis exclusivamente por movimentos vazios. 
 
Função programa estendida, computação 
Seja M = (∑, Q, 𝜹, q0, F) um autômato finito com movimentos vazios, a função programa 
estendida ou computação de M é representada por: 
 𝜹*: 2Q x ∑* → 2Q 
É a função programa 𝜹: Q x (∑ ∪ {𝜺}) → 2Q estendida para um conjunto finito de estados 
e para uma palavra e é indutivamente definida como segue: 
 𝜹*(P, 𝜺) = 𝜹𝜺(P) 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 𝜹*(P, wa) = 𝜹𝜺(R) onde R = {r | r ∈ 𝜹(s, a) e s ∈ 𝜹*(P, w)} 
A parada do processamento de um autômato finito com movimentos vazios é semelhante 
à do autômato finito não determinístico, assim como as definições de linguagem aceita e 
linguagem rejeitada. 
 
Linguagem aceita, linguagem rejeitada 
Seja M = (∑, Q, 𝜹, q0, F) um autômato finito com movimentos vazios, a linguagem aceita 
ou linguagem reconhecida por M é representada por: 
 ACEITA(M) ou L(M) 
É o conjunto de todas as palavras pertencentes a ∑* tais que existe pelo menos um 
caminho alternativo que aceita a palavra a partir de {q0}, ou seja: 
 ACEITA(M) = {w | 𝜹*({q0}, w) ∩ F ≠ ∅} 
Equivalente a linguagem rejeitada por M é representada por: 
 REJEITA(M) 
É o conjunto de todas as palavras pertencentes a ∑* rejeitadas portodos os caminhos 
alternativos de M a partir de {q0}, ou seja: 
 REJEITA(M) = {w | 𝜹*({q0}, w) ∩ F ≠ ∅} 
 
Computação vazia, computação 
Considere a seguinte linguagem sobre o alfabeto {a, b, c}: 
 L8 = {w | w possui como sufixo a ou bb ou ccc} 
O autômato finito com movimentos vazios: 
 M8 = ({a, b, c}, {q0, q1, q2, q3, q4, q5, q6, qf}, 𝜹8, q0, {qf}) 
Conforme demonstrado na figura abaixo: 
 
Figura 1.3 – Diagrama AFN-𝜺 – possui como sufixo a ou bb ou ccc 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Fonte: Paulo Blauth Menezes, 2011. 
 
É tal que: 
 ACEITA(M8) = L8 
Relativamente à computação vazia, vale que, por exemplo: 
 𝜹𝜺({q0}) = {q0, q1, q2, q4} 
A computação da entrada aab a partir do estado inicial q0, é como segue: 
 𝜹*({q0}, abb) = 𝜹𝜺({r | r ∈ 𝜹(s, b) e s ∈ 𝜹*({q0}, ab)}) (1) 
Sendo que: 
 𝜹*({q0}, ab) = 𝜹𝜺 ({r | r ∈ 𝜹(s, b) e s ∈ 𝜹* ({q0}, a)}) (2) 
Sendo que: 
 𝜹*({q0}, a) = 𝜹𝜺 ({r | r ∈ 𝜹(s, a) e s ∈ 𝜹* ({q0}, 𝜺)}) (3) 
Como: 
 𝜹*({q0},𝜺) = 𝜹𝜺 ({q0}) = {q0, q1, q2, q4} 
O qual quando considerado em (3): 
 𝜹*({q0}, a) = {q0, q1, q2, q4, qf} 
O qual quando considerado em (2): 
 𝜹*({q0}, ab) = {q0, q1, q2, q3, q4} 
O qual quando considerado em (1) resulta na computação desejada: 
 𝜹*({q0}, abb) = {q0, q1, q2, q3, q4, qf} 
Assim como o não determinismo a facilidade de movimentos vazios não aumenta o poder 
computacional dos autômatos finitos. De fato, para cada AFN𝜺 é possível construir um 
AFN equivalente que realiza o mesmo processamento, o contrário é trivialmente 
verdadeiro. 
 
Equivalência entre AFN e AFN𝜺 
A classe dos autômatos finitos com movimentos vazios é equivalente à classe dos 
autômatos finitos não determinísticos. 
 
Prova – por indução 
A prova consiste em mostrar que a partir de um AFN𝜺 M qualquer, é possível construir 
um AFN MN que realiza as mesmas computações, ou seja MN simula M, a ideia central 
do algoritmo é a construção de uma função programa sem movimentos vazios na qual o 
conjunto de estados destino de cada transição não vazia é ampliado com todos os demais 
estados possíveis de serem atingidos exclusivamente por transições vazias. O contrário, 
construir um AFN𝜺 a partir de um AFN não necessita ser mostrado, pois decorre 
trivialmente das definições. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Seja M = (∑, Q, 𝜹, q0, F) um AFN𝜺 qualquer: 
 MN = (∑, Q, 𝜹N, q0, FN) 
Um AFN construído a partir de M como segue: 
• 𝜹N: Q x ∑ → 2Q é tal que: 
 𝜹N (q, a) = 𝜹*({q}, a) 
FN é o conjunto de todos os estados q pertencentes a Q tal que: 
 𝜹𝜺 (q) ∩ F ≠ ∅ 
Ou seja, todos os estados que atingem estados finais via computações vazias. 
A demonstração de que de fato o AFN MN simula o AFN𝜺 M é feita por indução no 
tamanho da palavra. Portanto uma linguagem aceita por um autônomo com movimentos 
vazios é uma linguagem regular. 
 
Construção de um AFN a partir de um AFN𝜀 
Considere o autômato finito com movimentos vazios: 
 M9= ({a, b}, {q0, q1, q2}, 𝜹9, q0, {q2}) 
Como ilustrado na figura abaixo: 
 
Figura 1.4 – Diagrama – autômato finito com movimentos vazios 
 
Fonte: Paulo Blauth Menezes, 2011. 
Sendo que 𝜹9 é dado conforme tabela abaixo: 
 
Tabela 1.2 – Função programa AFN-𝜺 
𝜹9 a b 𝜺 
q0 {q0} ∅ {q1} 
q1 ∅ {q1} {q2} 
q2 {q2} ∅ ∅ 
Fonte: Paulo Blauth Menezes, 2011. 
O correspondente AFN: 
 M9N = ({a, b}, {q0, q1, q2}, 𝜹9N q0, FN) 
Construído conforme algoritmo apresentado na prova da equivalência entre AFN e AFN𝜺 
conforme figura abaixo: 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Figura 1.5 – Diagrama – autômato finito não determinístico equivalente 
 
Fonte: Paulo Blauth Menezes, 2011. 
FN = {q0, q1, q2}, pois: 
 𝜹𝜺(q0) = {q0, q1, q2} 
 𝜹𝜺(q1) = {q1, q2} 
 𝜹𝜺(q2) = {q2} 
Na construção de 𝜹9N, note-se que: 
 𝜹9*({q0}, 𝜺) = {q0, q1, q2} 
 𝜹9*({q1}, 𝜺) = {q1, q2} 
 𝜹9*({q2}, 𝜺) = {q2} 
Assim 𝜹9N é tal que: 
 𝜹9N (q0, a) = 𝜹9*({q0}, a) = 𝜹𝜺({r | r ∈ 𝜹(s, a) e s ∈ 𝜹*({q0}, 𝜺)}) = {q0, q1, q2} 
 𝜹9N (q0, b) = 𝜹9*({q0}, b) = 𝜹𝜺({r | r ∈ 𝜹(s, b) e s ∈ 𝜹*({q0}, 𝜺)}) = {q1, q2} 
 𝜹9N (q1, a) = 𝜹9*({q1}, a) = 𝜹𝜺({r | r ∈ 𝜹(s, a) e s ∈ 𝜹*({q0}, 𝜺)}) = {q2} 
 𝜹9N (q1, b) = 𝜹9*({q1}, b) = 𝜹𝜺({r | r ∈ 𝜹(s, b) e s ∈ 𝜹*({q1}, 𝜺)}) = {q1, q2} 
 𝜹9N (q2, a) = 𝜹9*({q2}, a) = 𝜹𝜺({r | r ∈ 𝜹(s, a) e s ∈ 𝜹*({q2}, 𝜺)}) = {q2} 
 𝜹9N (q2, b) = 𝜹9*({q2}, b) = 𝜹𝜺({r | r ∈ 𝜹(s, b) e s ∈ 𝜹*({q2}, 𝜺)}) = ∅ 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre Autômato Finito Não Determinístico com 
Transição em Epsilon, também chamados Transições em Vazio? Assista ao vídeo 
Autômato Finito Não Determinístico com Transições em Vazio e a sua transformação 
em um AFND sem movimentos vazios – com Prof. Ivan Suptitz. Disponível em: 
< https://www.youtube.com/watch?v=Ep_QfyPOaoY >. Acesso em: 27 abr. 2023. 
 
7.2. Autômatos de pilhas 
Semelhante as linguagens regulares, a classe das linguagens livres de contexto pode ser 
associada a um formalismo do tipo autômato denominado autômato com pilha. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
O autômato com pilha é semelhante ao autômato finito, incluindo uma pilha como 
memória auxiliar e a facilidade de não determinismo. A pilha é independente da fita de 
entrada e não possui limite máximo de tamanho, o que implica uma noção de tão grande 
quanto se queira. Portanto é baseada na noção de conjunto infinitamente contável. 
Estruturalmente sua principal característica é que o ultimo símbolo gravado é o primeiro 
a ser lido como demonstrado na figura abaixo: 
 
Figura 1.6 – Estrutura do tipo pilha 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
A base de uma pilha é fixa e define o seu início, o topo é variável e define a posição do 
último símbolo gravado. A facilidade de não determinismo é importante e necessária pois 
aumenta o poder computacional dos autômatos com pilha, permitindo reconhecer 
exatamente a classe de linguagens livres do contexto. Por exemplo, o reconhecimento da 
linguagem na qual a segunda metade de cada palavra é a reversa da primeira metade, ou 
seja, suponha que wr é w escrita de forma reversa: 
 
 {wwr | w é palavra sobre {a, b}} 
Só é possível um autômato com pilha não determinístico. 
Um resultado interessante é que qualquer linguagem livre do contexto pode ser 
reconhecida por um autômato com pilha com somente um estado, ou três estados 
dependendo da definição, isso significa que a estrutura de pilha é suficiente como única 
memória não sendo necessário usar os estados para memorizar informações passadas. Ou 
seja, a estrutura de estados no autômato com pilha poderia ser excluída sem se reduzir o 
poder computacional e como consequência podemos considerar que a pilha não possui 
tamanho máximo, o autômato com pilha pode assumir tantos estados quanto se queira. 
O modelo autômato com pilha possui duas definições universalmente aceitas que diferem 
no critério de parada do autômato, como segue: 
• O valor inicial da pilha é vazio e o autômato para aceitando ao atingir um estado 
final; 
• A pilha contém um símbolo especial denominado símbolo inicial da pilha. Não 
existem estados finais e o autômato para aceitando quando a pilha estiver vazia. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
As duas definições são equivalentes, possuem o mesmo poder computacional, sendo fácil 
modificar um autômato com pilha para satisfazer a outra definição. Um autômato com 
pilha não determinístico ou autômato com pilha é composto por quatro partes: 
• Fita – semelhante à do autômato finito; 
• Pilha – memória auxiliar do tipo pilha que pode ser usada para leitura e gravação; 
• Unidade de controle – reflete o estado damáquina, possui uma cabeça de fita e 
uma cabeça de pilha; 
• Programa, função programa ou função transição – comanda a leitura da fita, 
leitura e gravação da pilha, e define o estado da máquina. 
A pilha é dividida em células, armazenando cada uma um símbolo do alfabeto auxiliar, 
podendo ser igual ao alfabeto de entrada. A leitura ou gravação é sempre no topo, não 
possui tamanho fixo, nem máximo, sendo seu tamanho corrente igual ao tamanho da 
palavra armazenada, seu valor inicial é vazio, contém a palavra vazia. 
A unidade de controle possui um número finito e predefinido de estados, possui uma 
cabeça de fita e uma cabeça de pilha: 
• Cabeça da fita – unidade de leitura que acessa uma célula da fita de cada vez e se 
movimenta exclusivamente para a direita, é possível testar se a entrada foi 
completamente lida; 
• Cabeça da pilha – unidade de leitura e gravação a qual se move para a esquerda, 
ou para cima, ao gravar e para a direita, ou para baixo, ao ler um símbolo. Acessa 
um símbolo de cada vez estando sempre posicionada no topo, a leitura exclui o 
símbolo lido. É possível testar se a pilha está vazia em uma mesma gravação é 
possível armazenar uma palavra composta por mais de um símbolo, neste caso o 
símbolo do topo é o mais à esquerda da palavra gravada. 
Embora a unidade de controle possua um número finito e predefinido de estados, tal 
unidade não é dita de controle finito, em oposição aos autômatos finitos, pois o conteúdo 
da pilha também caracteriza o estado geral do sistema. O programa é uma função parcial 
tal que dependendo do estado corrente, símbolo lido da fita e símbolo lido da pilha, 
determina o novo estado e a palavra a ser gravada na pilha. Possui a facilidade de 
movimento vazio permitindo mudar de estado sem ler da fita. 
 
Autômato com pilha 
Um autômato com pilha não determinístico ou simplesmente autômato com pilha 
abreviado por AP, M é uma 6-upla: 
 M = (∑, Q, 𝜹, q0, F, V) 
Na qual: 
• ∑ é um alfabeto de símbolos de entrada; 
• Q é um conjunto de estados possíveis de autômato o qual é finito; 
• 𝜹 é uma função programa, programa ou função transição, suponha que 𝜺 e ? não 
são símbolos do alfabeto de entrada: 
 𝜹: Q x (∑ ∪ {𝜺, ?}) x (V ∪ {𝜺, ?}) → 2QxV* 
A qual é uma função total, sendo assim para p ∈ Q, x ∈ ∑ ∪ {𝜺, ?} e y ∈ V ∪ {𝜺, ?}: 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 𝜹(p, x, y) = {(q1, v1), ..., (qn, vn)} 
É uma transição do autômato; 
• q0 é um elemento distinguido de Q chamado de estado inicial; 
• F é um subconjunto de Q chamado conjunto de estados finais; 
• V é um alfabeto auxiliar ou alfabeto da pilha. 
As seguintes características da função programa deve ser consideradas: 
• Se para p ∈ Q, x ∈ ∑ ∪ {𝜺, ?} e y ∈ V ∪ {𝜺, ?} ocorre 𝜹(p, x, y) = ∅, então afirma-
se que a transição é indefinida para (p, x, y), o autômato para rejeitando a entrada; 
• Trata-se de uma função parcial pode ser indefinida para alguns argumentos do 
conjunto de partida; 
• A omissão do parâmetro de leitura representada por ? indica o teste de pilha vazia 
ou toda palavra de entrada lida; 
• O símbolo 𝜺 na leitura indica a facilidade de movimento vazio da fita ou da pilha, 
o autômato não lê nem move a cabeça, devemos notar que para o movimento ser 
considerado não determinístico é suficiente que o movimento seja vazio na fita; 
• O símbolo 𝜺 na gravação indica que nenhuma gravação é realizada na pilha e não 
move a cabeça. 
Por exemplo: 
 𝜹(p, ?, 𝜺) = {(q, 𝜺)} 
Indica que no estado p se a entrada foi completamente lida não lê da pilha e assume o 
estado q e não grava na pilha. 
Semelhante aos autômatos finitos a função programa de um autômato com pilha pode ser 
representada na forma de um diagrama, sendo assim suponha a transição: 
 𝜹(p, x, y) = {(q, v)} 
 
Figura 1.7 – Diagrama AP – transição 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
A computação de um autômato com pilha para uma palavra de entrada w consiste na 
sucessiva aplicação da função programa para cada símbolo de w, da esquerda para a 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
direita, até ocorrer uma condição de parada. É possível que um autômato com pilha nunca 
atinja uma condição de parada, neste caso fica processando indefinidamente, por exemplo 
um ciclo infinito é um programa que empilha e desempilha um mesmo símbolo 
indefinidamente sem ler da fita. 
Um autômato com pilha pode parar aceitando ou rejeitando a entrada ou ficar em loop 
infinito: 
• Aceita a entrada w, pelo menos um dos caminhos alternativos atinge um estado 
final, não importa se leu ou não toda a entrada, o autômato para e a palavra w é 
aceita; 
• Rejeita a entrada w, todos os caminhos alternativos rejeitam a entrada, a função 
programa é indefinida para cada caso, o autômato para e a palavra w é rejeitada; 
• Fica em loop para a entrada w, pelo menos um caminho alternativo está em loop 
infinito e os demais rejeitam ou também estão em loop infinito o autômato está 
em loop infinito. 
Para definir formalmente o comportamento de um autômato com pilha, é necessário 
estender a definição da função programa usando-se como argumento um estado e uma 
pilha. 
 
Linguagem aceita, linguagem rejeitada, linguagem loop 
Seja M = (∑, Q, 𝜹, q0, F, V) um autômato com pilha então: 
• A linguagem aceita ou linguagem reconhecida por M é representada por: 
 ACEITA(M) ou L(M) 
É o conjunto de todas as palavras pertencentes a ∑* aceitas por M, desde o estado inicial 
q0; 
• A linguagem rejeitada por M ´representada por: 
 REJEITA(M) 
É o conjunto de todas as palavras pertencentes a ∑* rejeitadas por M, a partir do estado 
inicial q0; 
• A linguagem loop de M, é representada por: 
 LOOP(M) 
É o conjunto de todas as palavras pertencentes a ∑* as quais M fica processando 
indefinidamente desde o estado inicial q0. 
Cada autômato com pilha M definido sobre o alfabeto ∑ induz uma partição do conjunto 
de todas as palavras ∑* em três classes de equivalência: ACEITA(M), REJEITA(M) e 
LOOP(M) conforme demonstrado na tabela abaixo: 
 
Tabela 1.3 – Partição de ∑* - induzida por um autômato com pilha M 
 
∑* 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
ACEITA(M) REJEITA(M) LOOP(M) 
Fonte: Paulo Blauth Menezes, 2011. 
 
Autômato com pilha: duplo balanceamento 
Considere o seguinte autômato: 
 M1 = ({a, b}, {q0, q1, qf}, 𝜹1, q0, {qf}, {B}) 
No qual 𝜹1 é como abaixo, é tal que ACEITA(M1) = L1, o conjunto LOOP(M1) é vazio: 
 𝜹1 (q0, a, 𝜺) = {(q0, B)} 
 𝜹1 (q0, b, B) = {(q1, 𝜺)} 
 𝜹1 (q0, ?, ?) = {(qf, 𝜺)} 
 𝜹1 (q1, b, B) = {(q1, 𝜺)} 
 𝜹1 (q1, ?, ?) = {(qf, 𝜺)} 
O diagrama do autômato é apresentado na figura abaixo: 
Figura 1.8 – Diagrama AP – duplo balanceamento 
 
Fonte: Paulo Blauth Menezes, 2011. 
Podemos observar que o autômato é determinístico, no estado q0, para cada símbolo a 
lido da fita, é armazenado um símbolo B na pilha. No estado q1 é realizado um batimento 
verificando se para cada símbolo b da fita existe um correspondente B na pilha. O 
algoritmo somente aceita se ao terminar de ler toda a palavra de entrada a pilha estiver 
vazia. 
 
Autômato com pilha: palavra e sua reversa 
Considere a seguinte linguagem sobre o alfabeto {a, b}: 
 L3 = {wwr | w pertence a {a, b}*} 
O autômato M3 é tal que ACEITA(M3) = L3, LOOP(M3) é vazio, o autômato é não 
determinístico devido ao movimento vazio de q0 para q1. O alfabeto auxiliar é igual ao 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
de entrada, em q0 é empilhado o reverso do prefixo a cada símbolo empilhado ocorre um 
movimento não determinístico para q1 o qual verifica se o sufixo da palavra é igual ao 
conteúdo da pilha. Como apresentado na figura abaixo: 
 
Figura 1.9 – Diagrama AP – wwr 
 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Autômato com pilha: anbman+mConsidere a seguinte linguagem sobre o alfabeto {a, b}: 
 L4 = {anbman+m | n ≥ 0, m ≥ 0} 
O autômato não determinístico M4 ilustrado abaixo: 
Figura 1.10 – Diagrama AP – anbman+m 
 
Fonte: Paulo Blauth Menezes, 2011. 
É tal que ACEITA(M4) = L4, o conjunto LOOP(M4) é vazio, M4 empilha um símbolo 
auxiliar X para cada a ou b em q0 ou q1 respectivamente, após em q2 verifica se o número 
de a no sufixo é igual ao de X empilhado. 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre Autômatos com Pilha? Assista ao vídeo 
Autômatos com pilha. Disponível em: 
< https://www.youtube.com/watch?v=-rfslM7ouzY>. Acesso em: 27 abr. 2023. 
 
 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Considerações finais 
 Como vimos a transição para um novo estado permite realizar os movimentos sem 
consumir qualquer caractere da entrada quando utilizamos a teoria de epsilon ou 
movimentos vazios, este tipo de transição fornece de maneira convincente a modelagem 
de sistemas cujo estados atuais não são conhecidos com precisão. Associada a teoria dos 
autômatos com pilha conseguimos um aumento do poder computacional, sendo o 
autômato com pilha um formalismo da classe de linguagens livres de contexto e 
semelhante ao autômato finito, teremos um resultado interessante já que qualquer 
linguagem livre do contexto pode ser reconhecida por um autômato com pilha utilizando 
apenas um estado para este reconhecimento. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Referências 
DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: 
máquinas universais e computabilidade. Porto Alegre: Bookman, 2011. 
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. 6. ed. Porto Alegre: 
Bookman, 2011. 
SIPSER, Michael. Introdução à Teoria da Computação. 2. ed. São Paulo: Cengage 
Learning, 2007.