Gramaticas livres de contexto

Prévia do material em texto

Gramática Livre de Contexto
2021.1
COMPILADORES
Máquina de Turing
 Uma máquina de Turing é um formalismo representa a 
realização de cálculos que são executados mecanicamente e 
em tempo finito. 
 Para isso, considerava-se um dispositivo que pudesse ler e 
escrever símbolos em uma fita. 
 A fita está dividida em quadrados e possui um tamanho 
ilimitado. 
Máquina de Turing
 A unidade de controle possui uma cabeça da fita para 
leitura/gravação, se movendo em torno da fita para frente ou 
para trás, passando um quadrado por vez. 
 Basicamente, pode-se resumir os passos de uma máquia de 
Turina em ler um símbolo de um quadrado de uma fita, alterar 
um símbolo em um quadrado de uma fita e mover a cabeça da 
fita para outro quadrado.
Máquina de Turing
 Fita: é uma estrutura de armazenamente dos símbolo de 
entrada, que podem ser infinitos. São seprados por células 
(quadrados), onde em cada célula possui um símbolo.
 Unidade de Controle: representa o estado atual da máquina. Por 
meio da cabeça da fita, tem acesso a cada célula da fita para 
leitura/gravação. Pode-se movimentar pela fita para a esquerda 
(para trás) ou para a direita (para frente).
 Programa (função de transição): é a função que define o estado 
da máquina, comandando as leituras, ravação e movimentação 
da cabeça da fita.
Máquina de Turing
Máquina de Turing
 Uma máquina de Turing é representada pela a tupla M = (Q, Σ, 
Γ , s, β, *, F, δ):
 - Q é um cojunto finito de estados da máquina
 - Σ é um alfabeto finito de símbolos da entrada
 - Γ é um alfabeto finito de símbolos da fita, Σ⊆Γ
 - s é o estado inicial, s∈Q
 - β é o símbolo ‘branco’, β∈Γ
 - * é o símbolo do marcador inicial da fita, *∈ Γ
 - F é o conjunto de estados finais, F⊆Q
 - δ é um cojunto de função de transição (programa), Q x (Γ U Σ) ⇒ Q x (Γ U Σ) x {← ,→ } 
onde←representa o movimento à esquerda e → representa o movimento à direita.
Classes de linguagens 
Gramática
 Uma gramática consiste em uma ou mais variáveis que 
representam linguagens.
 – Exemplo: linguagem dos palíndromos (permite a mesma 
leitura da esquerda para direita quanto da direita para 
esquerda).
 Ex: Anita latina
 Se w é um palíndromo, então 0w0 e 1w1 são palíndromos.
 Neste caso a linguagem é formada apenas por uma variável (w).
Gramáticas Irrestritas
 Uma linguagem L é uma Linguagem recursivamente enumerável 
 L, se somente se, L é gerada por uma gramática irrestrita.
 Linguagem recursivamente enumerável, linguagem tipo 0
 Uma linguagem aceita por uma máquina de Turing é dita 
linguagem recursivamente enumerável ou linguagem tipo 0 
(MENEZES, 2011)
 Definição 3: Uma gramática é considerada irrestrita se não 
houver restrições em suas produções (MENEZES, 2011).
Exemplo 1
 Considere a linguagem a seguir:
 L = {an bn cn| n ≥ 0}
 Gerada pela gramática irrestrita a seguir :
 G = ({S,C}, {a, b, c}, P, S)
 P = {
 S→ abc | ε ,
 ab → aabbC ,
 Cb → bC ,
 Cc → cc
 }
 Dada a palavra de entrada:
 w = aabbcc
 Podemos derivar a palavra conforme a seguir:
 S => abc => aabbCc => aabbcc
Exemplo 2
 Considere a linguagem a seguir:
 L = {an b2n an| n ≥ 1}
 Gerada pela gramática irrestrita a seguir :
 G = ({S,C}, {a, b, c}, P, S)
 P = { S→ aAbba ,
 aAb → aabbbA | ab ,
 bAb → bbA ,
 bAa → Bbaa ,
 bB → Bb ,
 aB → aA }
 Dada a palavra de entrada: w = aabbbbaa
 Podemos derivar a palavra conforme a seguir: S => aAbba => aabbbAba => aabbbbAa => aabbbBbaa => aabbBbaa => 
aabBbbbaa => aaBbbbbaa => aaAbbbbaa => aabbbbaa
Gramáticas Sensível ao Contexto
 Uma gramática sensível ao contexto, os símbolos terminais e 
não-terminais são consideradas no lado esquerdo das regras 
gramaticais , ou seja, consideram o seu contexto (Ramos, 
2008). 
 Definição 4: Gramática Sensível de Contexto
 Seja G = (V, T, S, P) uma gramática irrestrita então toda 
produção v → w em P tal que |v| ≤ |w|, ou seja, a forma 
setencial w tem comprimento maior ou igual a cadeia v (Acióly, 
2002), execeto para o caso S→ε.
Exemplo 3
 Considere a linguagem a seguir:
 L = {an b2n an| n ≥ 1}
 Gerada pela gramática irrestrita a seguir :
 G = ({S,C}, {a, b, c}, P, S)
 P = { S→ aAbba | abba ,
 aAb → aabbbB ,
 Bb → bB ,
 Ba → Caa | aa ,
 bCa → Cba ,
 bC → Cb ,
 aCb → aAb }
 Dada a palavra de entrada: w = aabbbbaa
 Podemos derivar a palavra conforme a seguir: S => aAbba => aabbbBba => aabbbbBa => aabbbbaa
Exemplo 4
 Considere a linguagem a seguir:
 L = {an bn an bn | n ≥ 1}
 Gerada pela gramática irrestrita a seguir : G = ({S,A, B, C, D, E}, {a, b}, P, S)
 P = { S → aAbab | abab 
 aAb → aabbB 
 Bb → bB 
 Ba → aC 
 aCb → Daabb | aabb 
 Da → aD 
 bDa → Eba 
 bE → Eb 
 aE → aA }
 Dada a palavra de entrada: w = aabbaabb
 Podemos derivar a palavra conforme a seguir: S => aAbab => aabbBab => aabbaCb => aabbaabb
Gramática Livre de Contexto
 Uma gramática sensível ao contexto, os símbolos terminais e 
não-terminais são consideradas no lado esquerdo das regras 
gramaticais , ou seja, consideram o seu contexto
 As gramáticas livres de contexto restringem o lado esquerdo 
das regras gramaticais um único símbolo não-terminal. Assim, 
estabelecem que todas as derivações sejam feitas 
considerando-se apenas o não-terminal selecionado para a 
substituição.
 Uma linguagem livre de contexto (LLC) é gerada por uma 
Gramática Livre de Contexto (GLC) 
Gramática Livre de Contexto
 Formalmente as gramáticas são caracterizadas como quádruplas 
ordenadas
 G = ( {V}, T, P, S)
 onde:
 V representa o vocabulário não terminal da gramática - variáveis.
 T é o vocabulário terminal, contendo os símbolos que constituem as 
sentenças da linguagem.
 P representa o conjunto de todas as leis de formação (regras de produção) 
utilizadas pela gramática para definir a linguagem.
 S representa o símbolo de início 
Exemplo 5
 Considere a linguagem a seguir:
 L = {a bn | n ≥ 1}
 Gerada pela gramática irrestrita a seguir :
 G = ( {S,A,B}, {a,b}, P, S )
 P={ 
 S → AB
 A → a | AB
 B → b 
 }
 Dada a palavra de entrada: w = abb
 Podemos derivar a palavra conforme a seguir: S → AB → ABB → aBB → abB → abb
Gramática Livre de Contexto
 Podem ser classificadas em gramáticas lineares à
 direita (GLD) ou à esquerda (GLE), cujas regras
 α → β são da forma:
– α ∈ V, α é um não terminal (Lado esquerdo deve ter apenas 
não terminais)
 GLD: β ∈ (T ∪ {ε}) (V ∪ {ε}) - A→wB ou A →w
 GLE: β ∈ (V ∪ {ε}) (T ∪ {ε}) - A→Bw ou A →w
Gramática Livre de Contexto
 Gramáticas lineares obedecem a regra α → β
 α ∈ V
 – o lado esquerdo da regra é formado por um símbolo não terminal
 GLD: β ∈ (T ∪ {ε}) (V ∪ { ε}) - A→wB ou A →w com |w| >= 0
 – o lado direito da regra é formado por N símbolos terminais seguido de UM 
símbolo não terminal OU formado apenas por N símbolos terminais
 GLE: β ∈ (V ∪ {ε}) (T ∪ {ε}) - A→Bw ou A →w com |w| >= 0
 – o lado direito da regra é formado por UM símbolo não terminal seguido de N 
símbolos terminais OU formado apenas por N símbolos terminais
Gramática Livre de Contexto
 GLD e GLE geram exatamente a mesma classe de linguagens. 
Portanto, é indiferente o emprego de uma ou outra dessas duas 
variantes de gramática, já que ambas possuem a mesma 
capacidade de representação de linguagens.
 As linguagens geradas por GLD e GLE são as linguagens 
regulares
 – Logo, GLD e GLE são equivalentes
Gramática Livre de Contexto
 Gramática Linear Unitária à Direita (GLUD)
 – Como na gramática linear à direita.
 – Adicionalmente |w| <= 1 no máximo um terminal do lado 
direito da regra
 Gramática Linear Unitária à Esquerda (GLUE)
 – Como na gramática linear à esquerda.
 – Adicionalmente |w| <= 1 no máximo um terminal do lado 
direito da regra
Exemplo
 Ex: dada a linguagem L = {a, aba, ababa, abababa, ababababa} 
 Faça as GLD, GLE, GLUD e GLUE que as reconhece.
 – mostre os passos para reconhecer a palavra ababa
Exemplo 6.1 GLD
 Considere a linguagem a seguir: L = {a (ab)n | n ≥ 0}
 Gerada pela gramática irrestrita a seguir :
 G = ( {S,A}, {a,b}, P, S )
 P = { 
 S → aA
 A → baA | ε 
 }
 Dada a palavra de entrada: 
 - w = ababa
 Podemos derivar a palavra conforme a seguir: 
 - S → aA → abaA → ababaA → ababaε
Exemplo 6.1 GLUD
 Considere a linguagem a seguir:
 L = {a (ab)n | n ≥ 0}
 Gerada pela gramática irrestrita a seguir :
 G = ( {S,A}, {a,b}, P, S )
 P = { 
 S → aA
 A → bB | ε
 B → aA 
 }
 Dada a palavra de entrada: 
 - w = ababa
 Podemos derivar a palavra conforme a seguir: 
 - S → aA → abB → abaA → ababB → ababaA → ababaε
Exemplo 6.1 GLE
 Considere a linguagem a seguir:
 L = {a (ab)n | n ≥ 0}
 Gerada pela gramática irrestrita a seguir :
 G = ( {S,A}, {a,b}, P, S )
 P = { 
 S → Sba | a 
 }
 Dada a palavra de entrada: 
 - w = ababa
 Podemos derivar a palavra conforme a seguir: 
 - S → Sba → Sbaba → ababa
Exemplo 6.1 GLUE
 Considere a linguagem a seguir:
 L = {a (ab)n | n ≥ 0}
 Gerada pela gramática irrestrita a seguir :
 G = ( {S,A}, {a,b}, P, S )
 P = { 
 S → Aa | a
 A → Sb 
 }
 Dada a palavra de entrada: 
 - w = ababa
 Podemos derivar a palavra conforme a seguir: 
 - S → Aa → Sba → Aaba → Sbaba → ababa
Árvore de Derivação
 A representação de uma determinada derivação de palavras de 
uma GLC na forma de árvores
 – A raiz é o símbolo inicial da gramática
 – Os vértices inferiores são as variáveis
 – Os folhas são os símbolos terminais, ou vazio
Ambiguidade
 Uma GLC é dita ambigua se existe uma palavra que possua 
uma ou mais árvore de derivação
Referência
 Capítulo 6 do Livro MENEZES, Paulo F. B., Linguagens Formais 
e Autômatos [recurso eletrônico, Minha Biblioteca]. Porto Alegre, 
Grupo A, 2011.
 http://www2.fct.unesp.br/docentes/dmec/olivete/lfa/
lfa_material_didatico.html
Desafi o
 Resolva a lista de exercícios passada pelo professor.
“Educação não transforma o mundo. Educação muda as 
pessoas. Pessoas transformam o mundo.”
Paulo Freire
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31