automato-com-pilha

Prévia do material em texto

Linguagens Livres do Contexto – Autômato com
Pilha
Linguagens Formais, Autômatos e Computabilidade
Filipe Saraiva
Filipe Saraiva | UFPA | 1 / 27
Conteúdo
Introdução
Autômato com Pilha
Exemplos
Conclusões
Filipe Saraiva | UFPA | 2 / 27
Conteúdo
Introdução
Autômato com Pilha
Exemplos
Conclusões
Filipe Saraiva | UFPA | 3 / 27
Introdução
Nesta unidade serão desenvolvidos os formalismos relacionados com
o reconhecedor de Linguagens Livres do Contexto, o Autômato com
Pilha (AP).
Linguagens Livres do Contexto permitem produções menos restritas
que as Linguagens Regulares (p. ex., com balanceamento). Portanto,
precisamos de reconhecedores específicos para essas linguagens.
Filipe Saraiva | UFPA | 4 / 27
Introdução
O Autômato com Pilha utiliza uma estrutura de dados do tipo Pilha que
serve como memória auxiliar do processamento de palavras.
Pilha é uma estrutura onde os elementos a serem processados são
exclusivamente alocados em um dos lados de um vetor ou lista (o que
chama-se topo). Tanto a leitura quanto a escrita em uma pilha ocorrem
apenas no elemento na extremidade desse lado.
Filipe Saraiva | UFPA | 5 / 27
Introdução
Ao contrário dos Autômatos Finitos, um Autômato com Pilha poderá ler
símbolos da fita (a palavra a ser processada) mas também ler e
escrever na pilha.
Filipe Saraiva | UFPA | 6 / 27
Conteúdo
Introdução
Autômato com Pilha
Exemplos
Conclusões
Filipe Saraiva | UFPA | 7 / 27
Autômato com Pilha
Existem 2 definições amplamente aceitas de Autômato com Pilha:
Filipe Saraiva | UFPA | 8 / 27
Autômato com Pilha
Definição 1
O Valor Inicial da Pilha é vazio e o autômato para aceitando a palavra
ao atingir um Estado Final.
Filipe Saraiva | UFPA | 9 / 27
Autômato com Pilha
Definição 2
A Pilha contém, inicialmente, um símbolo especial chamado símbolo
inicial da Pilha. Não há estados finais, o autômato aceita a palavra
quando a Pilha estiver vazia.
Filipe Saraiva | UFPA | 10 / 27
Autômato com Pilha
As definições apresentadas são equivalentes. Para nossos estudos,
utilizaremos a Definição 1 (com estados finais).
Filipe Saraiva | UFPA | 11 / 27
Autômato com Pilha
Um Autômato com Pilha tem, além dos componentes de um Autômato
Finito, uma estrutura do tipo Pilha que serve para ler e escrever
símbolos.
Filipe Saraiva | UFPA | 12 / 27
Autômato com Pilha
Autômato com Pilha
Um AP que nomearemos M é uma 6-upla ordenada do tipo:
M = (
∑
, Q, δ, q0, F, V)
Onde:
• ∑ – alfabeto de símbolos de entrada;
• Q – conjunto de estados possíveis do autômato;
• δ – função de transição ou programa;
• q0 – estado inicial, subconjunto de Q;
• F – subconjunto de Q com os estados finais;
• V – alfabeto auxiliar ou alfabeto da pilha.
Filipe Saraiva | UFPA | 13 / 27
Autômato com Pilha
A Função de Transição δ de um AP tem 3 valores como argumento: o
primeiro é o estado origem; segundo o símbolo a ser lido da palavra
em processamento; o terceiro o símbolo a ser lido da pilha.
O resultado do processamento é uma tupla de 2 elementos: o primeiro
é o estado resultante do processamento; o segundo informa se algum
caractere será escrito na Pilha.
δ(p, a, b) = {(q, b)}
Filipe Saraiva | UFPA | 14 / 27
Autômato com Pilha
δ(p, a, b) = {(q, b)}
No exemplo da expressão acima, parte-se do estado p lendo-se da
palavra o símbolo a e da pilha o símbolo b. O resultado é que o estado
atingido será o q e o símbolo b será escrito na pilha.
Filipe Saraiva | UFPA | 15 / 27
Autômato com Pilha
É possível que o AP não leia e nem escreva nada na pilha: nesse caso
o símbolo que indicará isso será o ε.
O símbolo ε também indica movimento vazio, a exemplo de um AFDNε.
Quando o símbolo de leitura for ?, significa que o AP realizará o teste
da pilha vazia ou toda palavra de entrada lida.
Filipe Saraiva | UFPA | 16 / 27
Autômato com Pilha
δ(p, a, b) = {(q, b)}
Tomando a expressão acima como exemplo, é comum representar as
transições de um AP da seguinte forma:
Filipe Saraiva | UFPA | 17 / 27
Autômato com Pilha
Após o processamento, um AP pode atingir 3 estados possíveis:
Aceita: algumas das linhas de processamento atingem um estado
final; a palavra é aceita pelo AP.
Rejeita: nenhuma linha de processamento atinge um estado final; a
palavra é rejeitada.
Loop: o AP fica processando indefinidamente a partir do estado inicial.
Filipe Saraiva | UFPA | 18 / 27
Conteúdo
Introdução
Autômato com Pilha
Exemplos
Conclusões
Filipe Saraiva | UFPA | 19 / 27
Exemplos – Autômato com Pilha
Vejamos nessa seção alguns exemplos de APs bem como o
processamento de palavras.
Filipe Saraiva | UFPA | 20 / 27
Exemplos – Autômato com Pilha
O Seguinte AP reconhece o duplo balanceamento entre a e b
M1 = ({a, b}, {q0, q1, qf }, δ, q0, {qf }, {B})
Função de Transição:
δ(q0, a, ε) = {(q0, B)}
δ(q0, b, B) = {(q1, ε)}
δ(q0, ?, ?) = {(qf , ε)}
δ(q1, b, B) = {(q1, ε)}
δ(q1, ?, ?) = {(qf , ε)}
Filipe Saraiva | UFPA | 21 / 27
Exemplos – Autômato com Pilha
Alguns exemplos de palavras sendo processadas em M1:
a:
δ(q0, a, ε) = {(q0, B)} – Pilha: B
FIM – RECUSADA
ab:
δ(q0, a, ε) = {(q0, B)} – Pilha: B
δ(q0, b, B) = {(q1, ε)} – Pilha: ε
δ(q1, ?, ?) = {(qf , ε)} – Pilha: ε
FIM – ACEITA
abab:
δ(q0, a, ε) = {(q0, B)} – Pilha: B
δ(q0, b, B) = {(q1, ε)} – Pilha: ε
FIM – RECUSADA
Filipe Saraiva | UFPA | 22 / 27
Exemplos – Autômato com Pilha
Este AP reconhece uma palavra e sua reversa.
M2 = ({a, b}, {q0, q1, qf }, δ, q0, {qf }, {a, b})
Função de Transição:
δ(q0, a, ε) = {(q0, a)}
δ(q0, b, ε) = {(q0, b}
δ(q0, ε, ε) = {(q1, ε)}
δ(q1, a, a) = {(q1, ε)}
δ(q1, b, b) = {(qf , ε)}
δ(q1, ?, ?) = {(qf , ε)}
Filipe Saraiva | UFPA | 23 / 27
Exemplos – Autômato com Pilha
Alguns exemplos de palavras sendo processadas em M2:
ab:
δ(q0, a, ε) = {(q0, a)} – Pilha: a
δ(q0, b, ε) = {(q0, b)} – Pilha: ab
FIM – RECUSADA
aa:
δ(q0, a, ε) = {(q0, a), (q1, a)} –
Pilha: a
δ(q1, a, a) = {(q1, ε), (qf , ε)} – Pilha:
ε
FIM – ACEITA
Filipe Saraiva | UFPA | 24 / 27
Conteúdo
Introdução
Autômato com Pilha
Exemplos
Conclusões
Filipe Saraiva | UFPA | 25 / 27
Conclusões
• Autômatos com Pilha são ferramentas voltadas para o
reconhecimento de linguagens livre de contexto;
• No Autômato com Pilha há uma estrutura de dados auxiliar do tipo
pilha, que permite a leitura e escrita de dados pelo autômato;
• Nesse autômato uma palavra pode ser aceita, recusada ou entrar
em loop;
• Para verificar se uma palavra é aceita, é necessário verificar se a
transição vazia que corresponde ao teste da pilha vazia é
possível.
Filipe Saraiva | UFPA | 26 / 27
Linguagens Livres do Contexto – Autômato com
Pilha
Linguagens Formais, Autômatos e Computabilidade
Filipe Saraiva
Filipe Saraiva | UFPA | 27 / 27
	Introdução
	Autômato com Pilha
	Exemplos
	Conclusões