automatosdepilhaNaodeterministicos

Prévia do material em texto

LINGUAGENS 
FORMAIS E 
AUTÔMATOS
OBJETIVOS DE APRENDIZAGEM
 > Definir a classe dos autômatos de pilha não determinísticos.
 > Exemplificar a construção de autômatos de pilha não determinísticos.
 > Classificar as linguagens reconhecidas por autômatos de pilha não de-
terminísticos.
Introdução
A classe de linguagens livres de contexto possui um tipo específico de autô-
mato capaz de reconhecê-la: os autômatos de pilha não determinísticos, tam-
bém chamados “autômatos de pilha”. Tais autômatos podem ser vistos como 
uma extensão dos autômatos finitos não determinísticos com movimento vazio, 
a qual é precisamente uma estrutura de pilha que atua como uma “memória” 
simples. Símbolos podem ser lidos, empilhados ou desempilhados do topo da 
pilha (HOPCROFT; MOTWANI; ULLMAN, 2003; SIPSER, 2007).
A importância do estudo de autômatos de pilha está relacionada com o 
uso desses formalismos reconhecedores dentro de analisadores sintáticos. 
Analisadores sintáticos são programas que determinam se o código de um 
programa está de acordo com as regras sintáticas da linguagem de programação 
em questão. Por exemplo, quando se escreve o código de um programa em 
linguagem de programação Java, esse código precisa ser analisado antes de ser 
traduzido para o formato intermediário bytecode (SEBESTA; TORTELLO, 2018). 
A análise sintática determina se não foi esquecido um ; ao final de um comando 
ou se para todo símbolo delimitador { existe um respectivo }, por exemplo.
Autômatos de pilha 
não determinísticos
Diego Vrague Noble
Neste capítulo, apresentaremos o conceito formal que define um autômato 
de pilha não determinístico, as técnicas para a construção de um autômato 
desse tipo e as formas de classificar as linguagens que são reconhecidas por 
esse tipo específico de autômato.
Introdução aos autômatos de pilha 
não determinísticos
Um autômato de pilha é, em essência, um autômato finito não determinístico 
com movimentos vazios ε e uma funcionalidade a mais: uma memória em 
forma de pilha capaz de armazenar uma cadeia de símbolos. Tal memória 
possibilita a esse tipo de autômato “lembrar” uma quantidade infinita de 
informação. No entanto, diferentemente de um computador de uso geral, 
essa pilha não pode ser acessada de forma arbitrária. Para se acessarem 
os símbolos da pilha, deve-se obedecer ao protocolo de pilha, o qual define 
que o autômato só pode acessar o elemento empilhado mais recentemente. 
Esse protocolo também é chamado “LIFO”, do inglês last in, first out — que, 
traduzido, significa que o último a entrar na pilha é também o primeiro a sair 
(MENEZES, 2011; HOPCROFT; MOTWANI; ULLMAN, 2003; SIPSER, 2007).
Como consequência dessa memória na forma de pilha, os autômatos 
de pilha reconhecem exatamente um conjunto de linguagens chamado lin-
guagens livres de contexto (LLCs). Muitas linguagens estão nesse conjunto, 
incluindo todas as linguagens regulares e algumas linguagens não regulares. 
Há, portanto, linguagens não regulares que não são LLCs, como, por exemplo, 
a linguagem {0n1n2n│n ≤ 1}.
A Figura 1 apresenta um esquema simplificado de autômato de pilha. 
Nele, é possível observar que a pilha pode ser escrita e lida pelo controle 
do autômato.
Figura 1. Esquema simplificado de autômato de pilha.
Fonte: Adaptada de Hopcroft, Motwani e Ullman (2003).
Autômatos de pilha não determinísticos2
A partir da Figura 1, podemos verificar que todo autômato de pilha tem 
um controle de estados, o qual é responsável por ler um símbolo por vez da 
entrada. Por meio do controle de estados, é permitido ao autômato ler o 
símbolo que ocupa o topo da pilha e, com base no símbolo de entrada e no 
símbolo no topo da pilha, realizar a transição correta. De forma alternativa, 
o autômato pode realizar um movimento vazio ε em vez de ler um símbolo 
de entrada e/ou um símbolo da pilha.
De maneira geral, a cada transição, o autômato de pilha realiza os processos 
apresentados a seguir (HOPCROFT; MOTWANI; ULLMAN, 2003).
a) Consome um símbolo da entrada de acordo com a transição. Se ε é 
usado na transição, nenhum símbolo da entrada é consumido.
b) Muda para um estado novo, que pode ou não ser o mesmo estado 
anterior.
c) Substitui o símbolo no topo da pilha por qualquer símbolo ou cadeia de 
símbolos. Essa substituição pode usar ε, que efetivamente desempilha 
o símbolo no topo da pilha. A substituição pode manter o símbolo an-
terior no topo da pilha, fazendo que o topo da pilha não mude de uma 
transição para outra. A substituição pode usar um símbolo diferente 
ou, ainda, uma cadeia de símbolos, havendo, neste caso, o efeito de 
desempilhar o topo e empilhar todos os símbolos da cadeia.
Definição e notação gráfica
Um autômato de pilha pode ser definido por uma sétupla (sequência com 
sete elementos), que pode ser especificada da seguinte maneira (HOPCROFT; 
MOTWANI; ULLMAN, 2003; SIPSER, 2007):
P = (Q, Σ, Γ, δ, q0, Z, F)
onde cada um dos elementos é definido da forma apresentada a seguir.
1. Q é um conjunto finito de estados.
2. Σ é o alfabeto de símbolos de entrada.
3. Γ é o alfabeto da pilha, que define quais símbolos podem ser empilhados.
4. δ é a função de transição, que define o comportamento do autômato. 
δ (lê-se “delta”) tem como entrada uma tripla δ(q, a, X), onde:
 ■ q é um estado de Q;
 ■ a é um símbolo do alfabeto de entrada Σ, ou ε;
Autômatos de pilha não determinísticos 3
 ■ X é um símbolo do alfabeto da pilha Γ.
 A função δ tem como saída um conjunto finito de duplas (p, γ), onde p é 
o novo estado e γ (lê-se “gama”) é a cadeia de símbolos que substituirá 
X, que é o topo da pilha antes da transição. Por exemplo, supondo-se 
que o topo da pilha contenha o símbolo X, se γ = ε, então X é desempi-
lhado; se γ = X, então a pilha permanece inalterada; e, se γ = YZ, então X 
é substituído por Z e Y é empilhado, tornando-se o novo topo da pilha.
5. q0 é o estado inicial do autômato. O autômato é inicializado no estado q0.
6. Z é o símbolo inicial da pilha. Inicialmente, a pilha contém apenas o 
símbolo Z no topo.
7. F é o conjunto de estados finais, também chamados “estados de acei-
tação”. Note que F ⊆ Q.
É usual anotar um autômato de pilha na forma gráfica de um diagrama 
de transição para autômatos de pilha, onde:
 � os círculos, ou nós, correspondem aos estados do autômato;
 � um triângulo indica o estado inicial, e estados com dois círculos con-
cêntricos representam os estados finais;
 � os arcos correspondem às transições do autômato — um arco rotulado 
a, X; Y de um estado q para um estado r significa que, para o símbolo 
lido de entrada a e o símbolo X no topo da pilha, a transição deve 
substituir X por Y e trocar do estado q para o estado r (Figura 2).
Figura 2. Exemplo de um diagrama com duas transições, 
particularmente a transição do estado q para o estado r 
a partir do símbolo de entrada a e do símbolo no topo da 
pilha X. Após a transição, X é substituído por Y no topo 
da pilha e r é o novo estado. Em notação matemática, 
esse arco é o mapeamento δ(q, a, X) = (r, Y).
Autômatos de pilha não determinísticos4
Podemos descrever o “momento” em que um autômato de pilha se en-
contra durante a computação. Essa ideia informal de momento do autômato 
é chamada descrição instantânea (DI) de um autômato. Quando se trata de 
autômatos finitos, a DI pode ser descrita por duas informações: o estado atual 
e os símbolos que ainda precisam ser lidos. No caso de autômatos de pilha, 
além dessas duas informações, é preciso, ainda, especificar o conteúdo da 
pilha. Mais especificamente, a DI é descrita por uma tripla (q, w, γ), onde q é 
o estado atual, w é o restante da cadeia a ser processada e γ é o conteúdo da 
pilha. Inicialmente, q é o estado inicial, w é toda a cadeia de entrada e γ é Z.
Dado um autômato de pilha P = (Q, Σ, Γ, δ, q0, Z, F) que, entre outras transi-
ções, possui uma transição δ(q, a, X) = (p, β), definimos um passo unitário de 
computação de P⊦p para qualquer w ∈ Σ* e γ ∈ Γ* como (HOPCROFT; MOTWANI; 
ULLMAN, 2003):
(q, aw, Xγ) ⊦p (p,βγ)
O conceito de passo unitário reflete a ideia de que, ao consumir o símbolo 
de entrada a da entrada e ao trocar o topo da pilha X por β, o autômato pode, 
então, trocar do estado q para o estado p. Note que o restante da entrada 
— ou seja, w e o restante da pilha (isto é, γ) — não influencia no passo nem 
é consumido ou alterado durante o passo.
Autômatos de pilha são, por padrão, não determinísticos. Isso implica 
que o autômato pode, em determinadas situações, ter nenhuma ou 
duas ou mais transições válidas a partir de um estado. No entanto, é indis-
pensável salientar que existem autômatos de pilha que se comportam como 
determinísticos.
Esses autômatos de pilha determinísticos possuem exatamente um caminho 
de computação a partir de uma combinação de estado, símbolo lido na entrada e 
símbolo no topo da pilha. Diferentemente dos autômatos finitos, o determinismo 
nos autômatos de pilha reduz o poder computacional desse tipo particular de 
autômato de pilha.
O conjunto de linguagens reconhecidas por autômatos de pilha determinís-
ticos se chama “linguagens livres de contexto determinísticas” (SIPSER, 2007). 
Esse conjunto de linguagens inclui todas as linguagens regulares e é subconjunto 
próprio do conjunto de LLCs. Por exemplo, a linguagem {w#wr|w ∈ {0,1}*} é uma 
linguagem livre de contexto determinística, porque podemos usar o símbolo # 
para determinar o meio da cadeia, descartando, assim, a necessidade do não 
determinismo para “adivinhar” onde está o meio.
Autômatos de pilha não determinísticos 5
Construção de um autômato de pilha 
não determinístico
A construção de um autômato de pilha inicia de maneira informal e intuitiva. 
Em outras palavras, é preciso, em primeiro lugar, mentalizar uma estratégia 
de computação de símbolos que necessariamente faça uso da pilha para 
determinar se uma cadeia pertence ou não à linguagem em questão. A partir 
dessa estratégia, construímos o diagrama de estados.
Para mostrar esse processo na prática, será construído um autômato 
de pilha para a LLC {wwR│w está em {0,1}*}. Essa linguagem, chamada “w-w-
-reverso”, é composta de cadeias de tamanho par formadas sobre um alfabeto 
binário de tal forma que a cadeia é um palíndromo. Lembre-se de que wwR 
significa que qualquer cadeia binária w está concatenada com ela mesma 
em ordem reversa. Por exemplo, as cadeias 011110, 1001 e a cadeia ε fazem 
parte dessa linguagem.
De maneira informal, podemos imaginar um autômato de pilha que usa 
a pilha para armazenar a primeira metade da cadeia e, ao prosseguir para 
a segunda metade, desempilha cada símbolo para conferir se o símbolo do 
topo da pilha é o mesmo da entrada. Como a pilha vai armazenar a primeira 
metade, mas vai desempilhar cada elemento em ordem reversa (do último 
símbolo para o primeiro), esse símbolo deve ser igual ao símbolo que está 
sendo lido atualmente. O problema está em saber onde termina a primeira 
metade da cadeia de entrada e onde começa a segunda parte. Não há um 
contador para sabermos o índice do elemento do meio; o autômato dispõe 
apenas de uma pilha. Nesse caso, vamos empregar o não determinismo como 
mecanismo usado para “adivinhar”, a cada transição, onde está o final da 
primeira metade da cadeia. Essa abordagem vai gerar vários caminhos de 
computação que vão rejeitar a entrada; porém, eventualmente uma delas 
vai “acertar” quando chegar a metade da cadeia de entrada. Para que um 
autômato não determinístico aceite a entrada, é preciso que pelo menos uma 
configuração entre em estado de aceitação.
Essa estratégia é ilustrada na Figura 3, em que se observa que a entrada 
deve ser aceita e que o conteúdo da pilha, quando desempilhado, é igual ao 
conteúdo restante da cadeia de entrada.
Autômatos de pilha não determinísticos6
Figura 3. Estado do autômato 
quando ele atingir a metade da 
entrada 001100. Os símbolos 
em cinza representam os sím-
bolos lidos.
Com uma ideia mais bem formada da estratégia, podemos refiná-la em 
quatro etapas, que são descritas a seguir.
1. Começa-se no estado inicial p, que representa o “chute” de que a 
metade da cadeia ainda não foi atingida. É a partir dessa metade que o 
reverso da primeira metade começa. Enquanto estiver no estado inicial 
p, devem-se ler os símbolos da cadeia de entrada e os empilhar na 
pilha. Efetivamente, toda a entrada é copiada para a pilha neste estado.
2. A qualquer momento, deve-se assumir que a metade da cadeia foi 
atingida. Nesse momento, a primeira parte da cadeia estará na pilha, 
conforme ilustrado na Figura 3. Para capturar esse momento, é criado 
um estado q, para o qual a máquina deve fazer a transição. Como o 
autômato é não determinístico, são feitos dois “chutes” a cada instante: 
um de que a metade da cadeia foi atingida (e o autômato vai para o 
estado q) e outro de que a metade não foi atingida (e o autômato fica 
no estado p).
3. No estado q, a entrada restante é comparada ao conteúdo da pilha, um 
símbolo por vez. Quando o símbolo lido é igual ao símbolo do topo da 
pilha, o símbolo do topo da pilha é desempilhado e a máquina continua 
no estado q. Caso contrário, o “chute” está errado, e esse ramo não 
determinístico vai morrer. Quando a cadeia pertencer à linguagem, 
eventualmente um ramo acertará o “chute” da metade da cadeia de 
entrada; nos demais casos, os ramos vão morrer.
Autômatos de pilha não determinísticos 7
4. Se a pilha estiver vazia, necessariamente foi vista uma cadeia w seguida 
de sua reversa wR. A entrada deve ser, portanto, aceita.
Traduzindo esse processo para um autômato de pilha na forma de diagrama, 
obtemos o autômato ilustrado na Figura 4. No exemplo, pode-se observar que, 
a cada transição do autômato no estado p lendo um símbolo 0 ou um símbolo 
1 da entrada com o mesmo símbolo no topo da pilha, um autômato fica em 
p e outro vai para q. Dessa maneira, por meio da transição para o estado q, 
o autômato tenta “adivinhar” quando chegou ao símbolo do meio da entrada.
Figura 4. Exemplo de autômato de pilha não determinístico capaz de 
reconhecer a linguagem wwR.
Fonte: Adaptada de Hopcroft, Motwani e Ullman (2003).
O autômato da Figura 4 pode ser descrito formalmente da seguinte maneira:
P = ({p, q, r}, {0,1}, {0,1, Z}, δ, p, Z, {r})
onde a função δ é descrita pelas regras de transições apresentadas a seguir.
1. δ(p, 0, Z) = {(p, 0Z)} e δ(p, 1, Z) = {(p, 1Z)}. Uma dessas transições é feita 
inicialmente, já que a pilha contém apenas o símbolo inicial Z no topo 
da pilha. O primeiro símbolo é lido e empilhado, empurrando Z para 
a base da pilha.
2. δ(p, 0, 0) = {(p, 00)}, δ(p, 1, 1) = {(p, 11)}, δ(p, 1, 0) = {(p, 10)} e δ(p, 0, 1) = 
{(p, 01)}. Essas transições servem para ler os símbolos e os empilhar no 
topo da pilha enquanto o autômato permanece no estado .
Autômatos de pilha não determinísticos8
3. δ(p, ε, Z) = {(q, Z)}, δ(p, ε ,0) = {(q, 0)} e δ(p, ε ,1) = {(q, 1)}. Essas transições 
permitem que o autômato faça uma transição espontânea ε para o 
estado q sem consumir símbolos de entrada. Nenhuma dessas tran-
sições altera o topo da pilha.
4. δ(q, 1, 1) = {(q, ε)} e (q, 0, 0) = {(q, ε)}. Essas transições desempilham os 
símbolos da pilha quando acontece o pareamento, ou seja, o símbolo 
desempilhado é igual ao símbolo lido. É de se esperar que muitas 
máquinas fiquem no estado q e “morram” por não haver transições.
5. δ(q, ε, Z) = {(r, Z)}. Essa transição final garante que a transição para 
o estado final q seja feita assim que o símbolo inicial da pilha Z é 
desempilhado. Caso a entrada não contenha mais símbolos a serem 
lidos, o autômato aceita a entrada; caso contrário, rejeita-a.
Um exemplo de passo a passo do autômato até um DI de aceitação é:
(p, 0110, Z) ⊦ (p, 110,0Z) ⊦ (p, 10, 10Z) ⊦ (q, 0,0Z) ⊦ (q, ε, Z) ⊦ (r, ε, Z)
Observe que, nesse passo a passo, não estão incluídos os caminhos que 
levam a uma rejeição. A seguir, está um exemplo de passo a passo que leva 
a um caminho de DI de rejeição para a mesma entrada:
(p, 0110, Z) ⊦ (q, 0110, Z)
Esse caminho do autômato levoua um DI de rejeição porque a máquina 
fez a mudança de estado para “adivinhar” a metade da entrada logo de início. 
A descrição instantânea leva a uma configuração de rejeição em que não há 
uma transição para ser feita, já que, no estado q, não há uma seta com 0 na 
entrada e Z no topo da pilha.
A classe de LLCs é exatamente a mesma classe gerada pelas gra-
máticas livres de contexto. O modelo de gramáticas é um modelo 
gerador, cuja maior vantagem é que ele expõe as estruturas de uma linguagem 
de maneira mais intuitiva e direta. Esse modelo, que é capaz de gerar recursi-
vamente todas as cadeiras possíveis de uma linguagem, opera diferentemente 
dos modelos reconhecedores, como os autômatos finitos e os autômatos de 
pilha. Estes são ditos reconhecedores porque reconhecem uma palavra por vez, 
ainda que também possam ser usados para definir uma linguagem.
Autômatos de pilha não determinísticos 9
Gramáticas livres de contexto são muito usadas para descrever as estru-
turas sintáticas das linguagens de programação, ao passo que autômatos de 
pilha servem como base para a implementação de analisadores sintáticos, os 
quais, por sua vez, verificam se um programa em particular obedece às regras 
sintáticas da linguagem.
Para mais informações, sugerimos a obra Conceitos de Linguagens de Pro-
gramação, de Sebesta e Tortello (2018).
Linguagens reconhecidas por autômatos 
de pilha não determinísticos
As linguagens reconhecidas por autômatos de pilha pertencem à classe das 
LLCs (HOPCROFT; MOTWANI; ULLMAN, 2003; SIPSER, 2007; MENEZES, 2011). 
Como mencionamos anteriormente, essa classe inclui todas as linguagens 
regulares, além de algumas linguagens não regulares. A relação entre essas 
linguagens dá origem ao que chamamos “hierarquia de linguagens formais”, 
ilustrada na Figura 5, em que se pode observar que as linguagens regulares 
são também LLCs, mas que nem toda LLC é uma linguagem regular.
Figura 5. Hierarquia de linguagens.
Todo autômato de pilha pode funcionar como um autômato finito, desde 
que não se use a pilha. Ou seja, para converter um autômato finito, seja ele 
determinístico ou não, basta trocar toda transição δ(q, a) = p por δ(q, a, Z) = 
(p, Z). Em outras palavras, a cada transição, o autômato empilha e desempi-
lha o símbolo inicial de pilha, efetivamente não fazendo uso da pilha como 
dispositivo de memória. Esse fato mostra que o autômato de pilha é capaz 
de simular o autômato finito, sendo, portanto, mais poderoso computacio-
nalmente (SIPSER, 2007).
Autômatos de pilha não determinísticos10
Dizemos que a linguagem aceita por um autômato de pilha P = (Q, Σ, Γ, 
δ, q0, Z, F) é toda linguagem aceita por P quando o autômato, partindo do 
estado inicial q0 e com pilha contendo apenas o símbolo inicial Z0, atinge um 
estado final por meio de zero ou mais transições e não há mais símbolos a 
serem lidos na entrada.
Assumindo que r ∈ F, ou seja, r é um estado final, denota-se que L(P) é 
a linguagem aceita pela máquina P por estado final quando (HOPCROFT; 
MOTWANI; ULLMAN, 2003):
{w|(q0, w, Z) ⊦P* (r, ε, ζ)}
onde ⊦P* denota “por meio de zero ou mais passos de computação de P” e ζ 
representa qualquer sequência de símbolos restantes na pilha.
Observe que a descrição instantânea inicial do autômato informa que o 
autômato parte do estado inicial q0, com a cadeia w na entrada e Z no topo 
da pilha, e termina quando o autômato atinge o estado final r, sem nenhum 
símbolo a ser lido na entrada.
Autômatos de pilha têm dois critérios de aceitação: terminação por estado 
final e terminação por pilha vazia. O critério de aceitação por estado final é 
o critério apresentado neste capítulo e é o mais usual: o autômato termina 
a execução aceitando a cadeia de entrada quando toda a cadeia é lida e o 
último estado é também um estado final. Quando essas duas condições 
forem satisfeitas, o conteúdo restante da pilha será irrelevante. No critério 
de aceitação por pilha vazia, o autômato aceita a cadeia de entrada quando 
toda a cadeia é lida e a pilha está vazia (é preciso desempilhar o símbolo 
inicial da pilha, o Z). Esses dois tipos de aceitação e parada são equivalen-
tes, no sentido de que um autômato pode ser convertido no outro e ambos 
reconhecem exatamente o mesmo conjunto de linguagens.
Para mais informações, sugerimos a obra Introdução à teoria de 
autômatos, linguagens e computação, de Hopcroft, Motwani e Ullman 
(2003). Nela, há um capítulo que aborda especificamente esse tipo de autômato 
de pilha.
Autômatos de pilha não determinísticos 11
Exemplos de LLC
Um exemplo de LLC é a linguagem dos parênteses balanceados. Nessa lingua-
gem, todo símbolo ( tem um respectivo símbolo consecutivo ) que aparece na 
cadeia. Os pares de parênteses podem não aparecer de forma imediatamente 
consecutiva, e nenhum símbolo ) deve estar fora de um par. São exemplos de 
cadeias que pertencem a essa linguagem: ((())), (()()) e ()()(). São exemplos 
de cadeias que não pertencem à linguagem: (())), (()( e ))((.
A estratégia para construir o autômato que reconhece a linguagem começa 
pela definição de como a pilha será usada. Nesse caso, a pilha pode ser usada 
para armazenar todo símbolo ( e determinar o seu respectivo ). Para tal, 
toda vez que encontrarmos na entrada um símbolo (, deveremos consultar o 
topo da pilha para determinar se devemos empilhar ou desempilhar o topo. 
A seguir, apresentamos todas as possibilidades de símbolos de entrada e 
símbolos no topo da pilha.
1. Símbolo lido na entrada ( e símbolo do topo da pilha (: empilha ((.
2. Símbolo lido na entrada ( e símbolo do topo da pilha ): desempilha (.
3. Símbolo lido na entrada ( e símbolo do topo da pilha Z: empilha (Z.
4. Símbolo lido na entrada ) e símbolo do topo da pilha ): rejeita.
5. Símbolo lido na entrada ) e símbolo do topo da pilha (: desempilha (.
6. Símbolo lido na entrada ) e símbolo do topo da pilha Z: rejeita.
Ao convertermos essas possibilidades em um autômato de pilha não de-
terminístico, obtemos o autômato apresentado na Figura 6. Nele, é possível 
observar que a transição para o estado final q ocorre somente quanto a pilha 
tem o símbolo inicial de topo da pilha Z. Essa situação acontece duas vezes 
em uma cadeia não vazia: uma vez no início e outra no final.
Figura 6. Autômato de pilha não deter-
minístico reconhecedor da linguagem 
dos parênteses balanceados.
Autômatos de pilha não determinísticos12
Outro exemplo de LLC é a linguagem 0n1n, onde n > 0. Nessa linguagem, 
existem n símbolos 0 concatenados necessariamente com n símbolos 1. 
Os símbolos 0 e 1 não podem aparecer alternados; primeiramente, devem 
aparecer os símbolos 0 e, depois, os símbolos 1. São exemplos de cadeias 
que pertencem a essa linguagem: 000111, ε e 01. São exemplos de cadeias 
que não pertencem à linguagem: 00, 1100 e 0101.
A estratégia para a construção desse autômato está em empilhar os sím-
bolos quando o símbolo lido for igual ao símbolo anterior e desempilhar os 
símbolos quando o símbolo lido for diferente do símbolo de topo da pilha. 
Ao convertermos essa estratégia para um autômato de pilha, obtemos o 
diagrama apresentado na Figura 7, em que se pode observar que a transição 
para o estado final r ocorre somente quando a pilha tem o símbolo inicial 
de topo da pilha Z.
Figura 7. Autômato de pilha não determinís-
tico da linguagem 0n1n, onde n > 0.
Autômatos de pilha são máquinas formais e abstratas úteis para o reco-
nhecimento de LLCs, podendo esse tipo de modelo ser usado, inclusive, para 
definir o conjunto de LLCs. Fora do escopo abstrato, os autômatos de pilha 
são aplicados na construção de analisadores sintáticos. Neste capítulo, você 
pôde compreender o conceito de autômatos de pilha, bem como os aspectos 
ligados à sua construção e as implicações na hierarquia de linguagens formais 
que derivam do seu estudo.
Autômatos de pilha não determinísticos 13
Referências
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introdução à teoria de autômatos, linguagens 
e computação. Rio de Janeiro: Elsevier,2003.
MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011.
SEBESTA, R. W.; TORTELLO, J. E. N. Conceitos de linguagens de programação. 11. ed. 
Porto Alegre: Bookman, 2018.
SIPSER, M. Introdução à teoria da computação. 2. ed. São Paulo: Cengage Learning, 2007.
Leitura recomendada
VIEIRA, N. J. Introdução aos fundamentos da computação. São Paulo: Cengage Learning, 
2006.
Autômatos de pilha não determinísticos14