Teoria da Computação aula 8

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Teoria da Computação
Aula 8 – Autômatos de Pilha 
Remis Balaniuk
Estrutura de um AFD/AFN
“Memória” é finita (estados do autômato)
Autômato com pilha
Autômato cuja estrutura básica é análoga à do Autômato Finito, adicionando uma memória auxiliar tipo pilha (a qual pode ser lida ou gravada)
O autômato com pilha pode ser Determinístico ou não-Determinístico
Estrutura de um AP
Memória é infinita (pilha)
Autômato com pilha
O Autômato de Pilha (AP) consegue:
ler, através da cabeça de leitura, os símbolos da fita seqüencialmente sempre da esquerda para a direita,
armazenar (push) símbolos na Pilha e 
retirar (pop) símbolos da Pilha.
Pilha do Autômato
Operações sobre pilhas
ou $
Intuitivamente 
Exemplo:
Sintaxe 
Sintaxe
Estado de um AP
(q,w,u)
q=estado atual
w=parte não lida da entrada
u=conteúdo da pilha
Movida 
Movida
Aceitação estado final
Aceitação por pilha vazia
Transições
Funções de transição
Utiliza-se ε ou λ para indicar movimento vazio (“nada”)
Exemplo 
19
Exemplo 
Leia-se: 
Entrada = o que eu devo tirar da entrada
Pilha = o que eu devo tirar da pilha (pop)
Ɛ=movimento vazio ou ‘nada’ se for na pilha
20
Exemplo 
Leia-se: 
-estando no estado q2
-e lendo na entrada 0
-não consuma nada da pilha
-continue no estado q2
-faça uma push de 0
21
Exemplo 
O que quer dizer?
22
Representação gráfica
Representação gráfica
Leia-se: (a,bc) a=o que eu tiro da entrada, 
 b=o que eu tiro da pilha (pop), 
 c=o que eu coloco na pilha (push)
Exemplo 
Qual a sequência de estados e conteúdo da pilha para: 
0011
00011
Formalização 
Formalização do exemplo
Outro exemplo
Palíndromos :
Qual a gramática?
AP para os palíndromos
AP para os palíndromos
Construa a tabela de transições correspondente
AP é generalização de AFD/AFN
Exercício 1 
Defina a gramática e construa um AP para a linguagem em {0,1}:
L={w|w tem tamanho ímpar e o único 0 fica no meio}
Mostre de forma gráfica e tabular
Exercício 2 
Defina a gramática e construa um AP para a linguagem em {a,b}:
Mostre de forma gráfica e tabular
L={anbman+m | n >= 0, m>= 0}
Exercício 3 
Defina a gramática e construa um AP para a linguagem em {a,b}:
L = { w  { a, b }*, com o mesmo no de a´s e b´s },
Mostre de forma gráfica e tabular
Exercício 4
Defina a gramática e construa um AP para a linguagem em {0,1}:
L = { 0n12n | n > 0} por pilha vazia. 
Exercício 5 
Dada a seguinte gramática:
SaSA|a
A bB
B b
Defina a linguagem criada pela gramática
Crie um AP que a reconheça
Mostre de forma gráfica e tabular
AP não determinístico
AP não determinístico
Exercício 6 
Defina a gramática e construa um AP para a linguagem em {0,1}:
L={w|w tem tamanho ímpar e tem um 0 no meio}
Mostre de forma gráfica e tabular