aula 4 - Automato de Pilhas

Prévia do material em texto

27/05/2021
1
UFRPE
Unidade Acadêmica de Serra 
Talhada UAST
Teoria da Computação
Prof Sérgio Paiva
Linguagens Livres de Contexto
Linguagens Livre de Contexto
• Observe o exemplo abaixo:
– L1={w | w possui apenas um 1}
– L2={w | w possui apenas um 1 na posição n/2 , 
sendo n=|w|}
– L1 é regular?
– L2 é regular?
– Qual a classe de Linguagens representada por L2?
2
27/05/2021
2
Linguagens Livre de Contexto
• Compreende um universo mais amplo de 
linguagens
– Parênteses Balanceados
– Construções bloco-estruturadas
• Algoritmos simples e eficientes
• Aplicações em linguagens artificiais, 
analisadores sintáticos, tradutores de 
linguagens e processadores de textos.
3
Linguagens Livre de Contexto
• Contém a classe de linguagens regulares
• Formalismos associados:
– Gramáticas Livres de Contexto
– Autômato com Pilha
4
27/05/2021
3
Gramática Livre de Contexto
• Definição Formal
– Uma Gramática é uma 4-upla G = (V,Σ,R,P), onde
– V é um conjunto finito de elementos denominado 
Varáveis
– Σ é um alfabeto (V ∩ Σ = )
– R é a regra com a forma X -> w, em que X Є V e w 
Є (V U Σ)* 
– P Є V é símbolo de partida
5
Gramática Livre de Contexto
• Regra de Produção:
– Uma linguagem formal é considerada “livre do 
contexto” quando suas regras de produções 
podem ser aplicadas independentemente do 
contexto do simbolo não terminal. Não importa 
quais símbolos existem na GLC, um único símbolo 
não terminal existente no lado esquerdo de uma 
regra pode sempre ser substituído pelo lado 
direito. E isso é o que distingue a GLC 
da gramática sensível ao contexto (GSC)
(fonte: wikipedia)
6
27/05/2021
4
Gramática Livre de Contexto
• Exemplo 1. 
– L={0n/210n/2|n ε N} tem uma GLC 
G={{P,S},{0,1},R,P} em que R :
– P -> 0P0 | 0S0
– S-> 1
– Mostre a derivação da palavra w=00100 gerada 
por G.
7
Gramática Livre de Contexto
• Exemplo 2. Duplo Balanceamento
– L={0n1n |n ε N} tem uma GLC G={{P},{0,1},R,P} 
em que R :
– P -> 0P1 | ε
– Mostre a derivação da palavra w=0011 gerada por 
G.
• Analogia com linguagens de programação
– Linguagens bloco-estruturada {n }n
– Parenteses balanceados (n )n
8
27/05/2021
5
Gramática Livre de Contexto
• Exemplo 3.
– Faça a gramática que gere L = {w Є {0,1}* | w = w 
r} Que são palíndromos sobre {0,1}*
9
Gramática Livre de Contexto
• Exemplo 3.
– G={{P},{0,1},R,P} em que R :
– P -> 0P0 | 1P1 | 0 | 1 | ε
– Mostre a derivação da palavra w=00100 gerada 
por G.
10
27/05/2021
6
Gramática Livre de Contexto
• Exemplo 4 Expressões aritméticas com 
colchetes balanceados, dois operadores e um 
operando.
– G={{P},{+,*,[,],x},R,P} em que R :
– P -> P+P | P*P | [P] | x 
– Mostre a derivação da palavra w=[x+x]*x gerada 
por G.
11
Gramática Livre de Contexto
• BNF – Backus Naur Form
• É uma maneira usual de de representar GLC.
– As váriaveis são palavras delimitadas pelos 
símbolos 
– As palavras não-delimitadas são terminais
– Uma regra de produção A -> x é representado por 
: A ::= x.
12
27/05/2021
7
Gramática Livre de Contexto
13
Gramática Livre de Contexto
14
27/05/2021
8
Gramática Livre de Contexto
15
BNF
• Exercício sobre BNF da linguagem C 
(Simplificada)
16
27/05/2021
9
Gramática Livre de Contexto
Derivações e Ambigüidade
Um conceito útil é o da árvore de Derivação (AD). 
Uma AD captura a essência de uma derivação, ou 
seja a história da obtenção de uma forma sentencial 
que não depende da ordem de aplicação das regras 
da GLC.
A uma derivação vai corresponder uma única AD. 
Uma AD poderá corresponder a várias derivações.
Duas derivações são ditas equivalentes se e somente 
se correspondem a mesma AD.
17
Gramática Livre de Contexto
• Árvore de Derivação
– Patindo-se do simbolo inicial como raiz 
– Os vétices interiores são, obrigatoriamente, 
variáveis. Se A é um vértice interior e x1,x2,...,xn 
são “Filhos” de A então:
• A->x1x2...xn é uma produção da gramática
• Os vértices x1x2...xn são ordenados da esquerda para 
direita
– Terminando-se com os símbolos terminais ou o 
símbolo vazio como folhas da árvore.
18
27/05/2021
10
Gramática Livre de Contexto
19
Gramática Livre de Contexto
• Exemplo 1.
– L={anbn |n ε N} tem uma GLC G={{P},{a,b},R,P} 
em que R :
– P -> aPb | ε
– fAça a arvore de derivaçãoda palavra w=aabb 
gerada por G.
20
27/05/2021
11
Gramática Livre de Contexto
• Exemplo 1.
21
Gramática Livre de Contexto
• Exemplo 2 Expressões aritméticas que podem 
possui colchetes balanceados, dois 
operadores e um operando.
– G={{P},{+,*,[,],x},R,P} em que R :
– P -> P+P | P*P | [P] | x 
– Mostre a árvore de derivação para w=[x+x]*x 
gerada por G.
22
27/05/2021
12
Gramática Livre de Contexto
23
Autômato com Pilha
• Uma autômato com pilha pode ser visto 
como um AF que tem uma estrutura 
auxiliar de pilha.
24
27/05/2021
13
Autômato com Pilha
• A pilha é independente da fita. Não possui 
tamanho limite
• O último simbolo gravado é o primeiro lido 
(FILO=Pilha)
• Base fixa e topo variável
25
Autômato com Pilha
• A pilha é dividida em células, guardando cada 
uma um símbolo do alfabeto auxiliar (pode ser 
igual ao alfabeto de entrada)
• A leitura exclui o símbolo lido
• É possível testar se a pilha esta vazia
• É possível armazenar uma palavra de mais de 
um símbolo em uma mesma gravação, sendo 
que o topo da pilha será a letra mais a esquerda
26
27/05/2021
14
Autômato com Pilha
• O programa ou função estendida comanda a 
leitura da fita, leitura e gravação da pilha e o 
estado da máquina. Permite mudar de estado 
sem leitura da pilha
• O programa é um função parcial tal que:
– Dependendo do estado corrente, símbolo lido na fita 
e símbolo lido na pilha, determina um novo estado e 
a palavra ( ou símbolo) a ser escrito na pilha
27
Autômato com Pilha Deterministico
• Definição Formal Autômato com pilha deterministico:
• M = (Σ, Q, δ, q0, F, V)
• Σ - alfabeto de símbolos) de entrada
• Q - conjunto de estados possíveis o qual é finito
• δ - (função) programa ou função de transição função 
parcial
• δ: Q x (Σ U { ε }) x (V U { ε }) → QxV*
• δ(p, x, y) = (q, v) transição
• q0 - elemento distinguido de Q: estado inicial
• F - subconjunto de Q: conjunto de estados finais
• V - alfabeto auxiliar ou alfabeto da pilha
28
27/05/2021
15
Autômato com Pilha
29
Autômato com Pilha
• Exemplo 1:
• A linguagem L= {anbn | n ε N} é aceita pelo seguinte 
APD.
• Qual o critério de aceitação de uma palavra?
30
27/05/2021
16
Autômato com Pilha
• Exemplo 2:
• A linguagem L= {w ε {0,1} | o número de zeros é igual ao 
número de uns}.
• A máquina M={{I,D},{0,1},{Z,U,F},,I,{I}}
• Tente gerar a regra do autômato tal que:
– Dois estados (Diferente = D e Igual = I} que indicam números 
diferentes de 0 e uns.
– Z = zero na pilha e U = um na pilha.
– F é um símbolo para determinar o fim da pilha
– I é estado inicial e final
31
Autômato com Pilha
• Exemplo 2:
• Com :
1. (I,0,λ) = [D,ZF] 
2. (I,1,λ) = [D,UF]
3. (D,0,Z) = [D,ZZ]
4. (D,0,U) = [D, λ]
5. (D,1,U) = [D,UU]
6. (D,1,Z) = [D, λ]
7. (D, λ,F) = [I, λ]
32
27/05/2021
17
Autômato com Pilha
• Exemplo 2:
• Desenhar o diagrama de transições 
• Computar a palavra w=001110
33
Autômato com Pilha Não Determinístico
• Definição Formal Autômato com pilha não deterministico:
• M = (Σ, Q, δ, I, F, V)
• Σ - alfabeto de símbolos) de entrada
• Q - conjunto de estados possíveis o qual é finito
• δ - (função) programa ou função de transição função parcial
• δ: Q x (Σ U { ε }) x (V U { ε}) → QxV*
• δ(p, x, y) = (q, v) transição
• I – subconjunto de Q : estados iniciais
• F - subconjunto de Q: conjunto de estados finais
• V - alfabeto auxiliar ou alfabeto da pilha
34
27/05/2021
18
Autômato com Pilha Não Determinístico
• Exemplo 1:
• A linguagem L= {w ε {0,1} | o número de zeros é 
igual ao número de uns}.
35
Autômato com Pilha Não Determinístico
• Exemplo 1:
• Onde está o “não-determinismo” ?
• Construa as regras, e oformalismo.
36
27/05/2021
19
Autômato com Pilha Não Determinístico
• Exemplo 2:
• Observe o seguinte APN e diga se ele é 
equivalente ao outro. Escreva seu formalismo.
37
?
Autômato com Pilha Não Determinístico
• Exemplo 2:
• A resposta é SIM se consideramos ( e devemos fazê-lo) o 
estado final com a pilha vazia. Porque?
38
27/05/2021
20
Lema do Bombeamento
Linguagens LC
• Seja L uma LLC. Então, existe um número n, 
que só depende de L, tal que qualquer cadeia 
z de L com comprimento maior ou igual a n 
pode ser decomposta de maneira que z = 
uvwxy e
– |vx| ≥1
– |vwx| ≥ n
– para todo i ≥ 0, uviwxiy pertence a L.
39
Lema do Bombeamento
Linguagens LC
• Exemplo : Seja a gramática G abaixo, dada por 
suas regras. 
– E -> E + T | T
– T -> T * F | F
– F -> ( E ) | a
• Gere a árvore de derivação para a palavra 
a*(a+a)+a.
40
27/05/2021
21
Lema do Bombeamento
Linguagens LC
41
Gere a árvore de derivação para a palavra a*(a+a)+a.
Lema do Bombeamento
Linguagens LC
• Para a arvore de derivação acima, olhemos para 
as derivações indicadas. Estes pontos podem ser 
“bombeados” que a palavra continuará 
pertencente a linguagem L de G(L).
– E -> T+a
– E -> a*(T+a)
42
27/05/2021
22
Lema do Bombeamento
Linguagens LC
• Decompondo z=a*(a+a)+a
– u = ε v = a*(
– w = a x = +a) y=+a 
• As seguintes cadeias devem pertencer a 
linguagem:
43
Lema do Bombeamento
Linguagens LC
• Exemplo: Vamos agora mostrar que L = { ambmcm | 
n≥0 } não é livre de contexto, usando o teorema 
acima. A demonstração é por contradição: 
suporemos que L é livre de contexto, e 
deduziremos um absurdo.
• Se L é llc, L satisfaz o teorema acima para algum n. 
Suponha que a cadeia z=akbkck é suficientemente 
longa: | z | ≥ n. Então z pode ser decomposta, z = 
uvwxy, de forma que para qualquer i, zi = uviwxiy 
pertence a L. 
44
27/05/2021
23
Lema do Bombeamento
Linguagens LC
• A contradição está em que qualquer 
decomposição, existem cadeias zi que não 
pertencem a L: ou tem o número errado de a's, 
b's, e c's, ou aparecem símbolos fora da ordem a 
- b - c: as combinações ba,cb e ca não podem 
ocorrer em L. 
45
Lema do Bombeamento
Linguagens LC
• Para eliminar todas as decomposições:
– se v e x não tem o mesmo número de a's, b's e c's, 
algum zi terá números diferentes dos três símbolos;
– se v e x tem o mesmo número de a's, b's e c's, 
devemos ter v = aj e x = bjcj
j, ou v= ajbj e x=cj No 
primeiro caso, z2 contém x2= bjcjbjcj, que contém a 
combinação cb, que não ocorre em L; 
– no segundo caso, de forma semelhante, ocorre a 
combinação ba.
• Logo, L não é uma llc.
46
27/05/2021
24
Lema do Bombeamento
Linguagens LC
– Para as Linguagens, mostre se são ou não LLC 
utilizando o Lema do Bombeamento
– A) L ={0i1j2i3j | i>=1, j>=1}
– B) L ={ww | w pertence a {0,1}}
47
Conversão
• De gramática para ADP
– Seja uma gramática G={V,T,Q,S}, um PDA que 
aceite L(G) por pilha vazia é dada pelas regras 
abaixo: 
– P={{q},T,V U T, δ,I,P}
– 1) δ( I, λ, λ)=(q,P)
– 2) Se P-> λ pertence a R, δ( q, λ, P) = (q, λ)
– 3) Para cada terminal a e X pertencente a V, δ (q,a,X) = {(q,y 
) | y pertence a V* e X -> ay pertence a R}
– OS : Aceitar por pilha vazia implica em apenas um 
estado para o ADP (Vamos olhar apenas a pilha)
48
27/05/2021
25
Conversão
• De gramática para ADP
– Exemplo : Dada G={{E,I},T,P,E} uma CFG, onde a 
regra de produção é :
– P -> 0PUP | 1PZP | ε
– U -> 1
– Z -> 0
– construa um PDA que aceite L(G) por pilha vazia
49
Conversão
• Resposta
– P -> 0PUP | 1PZP | ε
– U -> 1
– Z -> 0
– Regras : 
• δ(I, ε, ε) = (q,P)
• δ(q, ε,P) =(q, ε)
• δ(q, 0,P) = (q,PUP) ; 
• δ(q, 1,P) =(q,PZP); 
• δ(q, 1,U) = (q, ε)
• δ(q,0,Z) = (q, ε)
50
Regra de Conversão:
1) δ( i, λ, λ)=(q,P)
2) Se P-> λ pertence a R, δ( q, λ, P) = (q, λ)
3) Para cada terminal a e X pertencente a 
V, δ (q,a,X) = {(q,y ) | y pertence a V* e 
X -> ay pertence a R}
27/05/2021
26
Conversão
• Faça o Diagrama para o PDA acima.
• Crie uma palavra W que pertença a L(G)
• Utilizando uma palavra w que pertença a L(G), 
verifique se o PDA acima a reconhece.
51
Conversão
• Exemplo :
– Dada a Gramática 
• G = ({ S, B }, { a, b }, P, S)
• P = { S → aB | aSB, B → b }
– Crie um ADP a partir de G.
52
Regra de Conversão:
1) δ( i, λ, λ)=(q,P)
2) Se P-> λ pertence a R, δ( q, λ, P) = (q, λ)
3) Para cada terminal a e X pertencente a 
V, δ (q,a,X) = {(q,y ) | y pertence a V* e 
X -> ay pertence a R}
27/05/2021
27
Conversão
• Solução :
• G = ({ S, B }, { a, b }, P, S)
• P = { S → aB | aSB, B → b }
• Transições do AFD:
• δ(I, λ, λ) = (q,S) ; 
• δ(q, a,S) =(q,B); 
• δ(q, a,S) =(q, SB)
• δ(q, b,B) = (q, λ)
53
Regra de Conversão:
1) δ( i, λ, λ)=(q,P)
2) Se P-> λ pertence a R, δ( q, λ, P) = (q, λ)
3) Para cada terminal a e X pertencente a V, δ 
(q,a,X) = {(q,y ) | y pertence a V* e X -> ay
pertence a R}
54