automatos_pilha2

Prévia do material em texto

(1 – 1 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Linguagens Formais e Autoˆmatos
Autoˆmato Finito com Pilha
Prof. Leandro Alexandre, MSc
3 de outubro de 2013
Prof. Leandro Alexandre, MSc PDA
(2 – 5 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Autoˆmato Finito com Pilha
Prof. Leandro Alexandre, MSc PDA
(3 – 5 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Esquema Ba´sico
Prof. Leandro Alexandre, MSc PDA
(4 – 5 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Definic¸a˜o 1:
Um Autoˆmato com Pilha (Pushdown Automaton - PDA) e´ uma
sextupla P = < Σ, Γ, S, s0, δ, F >onde:
Σ: alfabeto de entrada;
Γ: alfabeto da pilha;
S 6= ∅;
s0 ∪ S ;
δ: S x (Σ ∈ ε x (Γ ∈ ε)): func¸a˜o de transic¸a˜o;
F ⊆ S : conjunto de estados finais (ou de aceitac¸a˜o).
Prof. Leandro Alexandre, MSc PDA
(5 – 5 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Processamento de um PDA
δ (si, a, x) = {(si, y), (sk, z)}.
Duas transic¸o˜es poss´ıveis quando o autoˆmato esta´ no estado
si, lendo o s´ımbolo a de entrada e com x no topo da pilha.
A transic¸a˜o (sj , y) ∈ δ(si, a, x).
Mudar o estado corrente de si para sj ;
Processar o s´ımbolo a (avanc¸ar a cabec¸a de leitura da fita);
Remover o s´ımbolo x do topo da pilha; e
Colocar o s´ımbolo y no topo da pilha.
Prof. Leandro Alexandre, MSc PDA
(6 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Representac¸a˜o Gra´fica
Prof. Leandro Alexandre, MSc PDA
(7 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
a, b → c :
a = ε: transic¸a˜o sem ler s´ımbolo de entrada.
b = ε: transic¸a˜o sem ler s´ımbolo da pilha.
c = ε: transic¸a˜o sem escrever na pilha.
δ (si, a, x) = {(sj , y)}
O PDA muda do estado si para o sj , leˆ a da fita de entrada,
desempilha x e empilha y.
Prof. Leandro Alexandre, MSc PDA
(8 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
δ (si, ε, x) = {(si, ε)}
Se a posic¸a˜o de entrada e´ ε, a transic¸a˜o na˜o processa um
s´ımbolo de entrada, mas desempilha o x.
Prof. Leandro Alexandre, MSc PDA
(9 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
δ (si, ε, ε) = {(si, x)}
Se a posic¸a˜o de entrada e´ ε, a transic¸a˜o na˜o processa um
s´ımbolo de entrada, mas empilha o x.
Prof. Leandro Alexandre, MSc PDA
(10 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
δ (si, a, ε) = {(sj , ε)}
Transic¸a˜o equivalente a transic¸a˜o de um DFA.
Efeito determinado somente pelo estado corrente e pelo
s´ımbolo de entrada.
Transic¸a˜o na˜o consulta e na˜o altera a pilha.
Prof. Leandro Alexandre, MSc PDA
(11 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Definic¸a˜o 2:
Tripla [si, w, α], onde si e´ o estado corrente, w ∈ Σ* e´ o conjunto
de s´ımbolos ainda na˜o processados e α e´ o conteu´do da pilha.
Prof. Leandro Alexandre, MSc PDA
(12 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Exemplo 1:
< Σ = {a, b}, Γ = {x}, S = {s0, s1}, s0, δ, F = {s0, s1}>,
onde:
δ(s0, a, ε) = {(s0, x)}.
δ(s0, b, x) = {(s1, ε)}.
δ(s1, b, x) = {(s1, ε)}.
L(P) = {aibi | i ≥ 0}.
[s0, aabb, ε] → [s0, abb, x ] → [s0, bb, xx ] → [s1, b, x ] →
[s1, ε, ε].
Prof. Leandro Alexandre, MSc PDA
(13 – 13 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Exemplo 1:
< Σ = {a, b}, Γ = {x}, S = {s0, s1}, s0, δ, F = {s0, s1}>,
onde:
δ(s0, a, ε) = {(s0, x)}.
δ(s0, b, x) = {(s1, ε)}.
δ(s1, b, x) = {(s1, ε)}.
L(P) = {aibi | i ≥ 0}.
[s0, aabb, ε] → [s0, abb, x ] → [s0, bb, xx ] → [s1, b, x ] →
[s1, ε, ε].
Prof. Leandro Alexandre, MSc PDA
(14 – 17 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Linguagem aceita por um DFA
Prof. Leandro Alexandre, MSc PDA
(15 – 17 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Definic¸a˜o 3:
Seja P = < Σ, Γ, S, s0, δ, F > um PDA. Uma cadeia w ∈ Σ* e´
aceita por P se existe um processamento:
[s0, w, ε] → [si, ε, ε]
onde si ∈ F. A linguagem de P, denotada L(P), e´ o conjunto de
cadeias aceitas por P.
Prof. Leandro Alexandre, MSc PDA
(16 – 17 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Exemplo 2:
L(P) = {wcwR | w ∈ {a, b}*},
< Σ = {a, b, c}, Γ = {a, b}, S = {s0, s1}, s0, δ, F =
{s1}>.
Prof. Leandro Alexandre, MSc PDA
(17 – 17 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Exemplo 2:
L(P) = {wcwR | w ∈ {a, b}*},
< Σ = {a, b, c}, Γ = {a, b}, S = {s0, s1}, s0, δ, F =
{s1}>.
Prof. Leandro Alexandre, MSc PDA
(18 – 24 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Determin´ıstico e Na˜o Determin´ıstico
Prof. Leandro Alexandre, MSc PDA
(19 – 24 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Determin´ıstico
Definic¸a˜o 4:
Um PDA e´ determin´ıstico se existe no ma´ximo uma transic¸a˜o
para cada combinac¸a˜o de estado, s´ımbolo de entrada e
s´ımbolo no topo da pilha.
Um PDA e´ determin´ıstico se na˜o conte´m transic¸o˜es
compat´ıveis distintas.
Prof. Leandro Alexandre, MSc PDA
(20 – 24 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Na˜o Determin´ıstico
Definic¸a˜o 5:
Um PDA e´ na˜o determin´ıstico se existe mais uma transic¸a˜o
para cada combinac¸a˜o de estado, s´ımbolo de entrada e
s´ımbolo no topo da pilha.
Prof. Leandro Alexandre, MSc PDA
(21 – 24 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceitapor um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Na˜o Determin´ıstico
Exemplo 3:
L(P) = {ai | i ≥ 0} ∪ {aibi | i ≥ 0}.
A transic¸a˜o ε a partir de s0 permite chegar a s2 depois de
processar toda a cadeia de entrada.
Esta transic¸a˜o introduz o na˜o determinismo ao PDA.
Prof. Leandro Alexandre, MSc PDA
(22 – 24 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Na˜o Determin´ıstico
Exemplo 3:
L(P) = {ai | i ≥ 0} ∪ {aibi | i ≥ 0}.
A transic¸a˜o ε a partir de s0 permite chegar a s2 depois de
processar toda a cadeia de entrada.
Esta transic¸a˜o introduz o na˜o determinismo ao PDA.
Prof. Leandro Alexandre, MSc PDA
(23 – 24 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Na˜o Determin´ıstico
Exemplo 4:
L(P) = {wwR | w ∈ {a, b}*}.
O na˜o determinismo permite ao PDA ”adivinhar”quando a
metade da cadeia de entrada foi processada.
Prof. Leandro Alexandre, MSc PDA
(24 – 24 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Na˜o Determin´ıstico
Exemplo 4:
L(P) = {wwR | w ∈ {a, b}*}.
O na˜o determinismo permite ao PDA ”adivinhar”quando a
metade da cadeia de entrada foi processada.
Prof. Leandro Alexandre, MSc PDA
(25 – 28 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Processamento de um PDA
Prof. Leandro Alexandre, MSc PDA
(26 – 28 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Processamento de um PDA
Definic¸a˜o formal na˜o conte´m mecanismos para testar pilha
vazia.
Um PDA pode simular esse mecanismo com o s´ımbolo $:
$ e´ o primeiro s´ımbolo a ser colocado na pilha.
Quando o PDA ler novamente o $, enta˜o a pilha esta´ vazia.
Prof. Leandro Alexandre, MSc PDA
(27 – 28 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Na˜o Determin´ıstico
Exemplo 5:
L(P) = {aibjck | i, j e k ≥ 0 e i = j ou i = k}.
Prof. Leandro Alexandre, MSc PDA
(28 – 28 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
PDA Na˜o Determin´ıstico
Exemplo 5:
L(P) = {aibjck | i, j e k ≥ 0 e i = j ou i = k}.
Prof. Leandro Alexandre, MSc PDA
(29 – 31 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Bibliografia
Prof. Leandro Alexandre, MSc PDA
(30 – 31 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
M. Sipser.
Introduc¸a˜o a Teoria da Computac¸a˜o 2007,
PWS Publishing Company.
Prof. Leandro Alexandre, MSc PDA
(31 – 31 de 31)
Autoˆmato Finito com Pilha
Representac¸a˜o Gra´fica
Linguagem aceita por um DFA
PDA Determin´ıstico e Na˜o Determin´ıstico
Processamento de um PDA
Bibliografia
Agradecimentos
Prof. Dr. Humberto Longo (Universidade Federal de Goia´s).
Prof. Leandro Alexandre, MSc PDA
	Autômato Finito com Pilha
	Representação Gráfica
	Linguagem aceita por um DFA
	PDA Determinístico e Não Determinístico
	Processamento de um PDA
	Bibliografia