aula1_2019

Prévia do material em texto

Gramáticas
Uma gramática é uma quádrupla, G=(V, T, P, S), onde:
V é um conjunto de símbolos variáveis ou não-terminais.
T é um conjunto de símbolos terminais, disjunto de V.
P é um conjunto finito de regras de produção.
S é um elemento de V denominado “variável inicial”.
Exemplo:
 G = ( V = {S, X},
 T = {a, b},
 P = {S  a | aX, X  b | bX}, 
 S ).
Regras de Produção
São pares do tipo (a, b), representados por ab, onde a  (VT)+ e b  (VT)*.
Definem as condições de geração das palavras da linguagem.
Abreviação: ab1, ab2, ..., abn por ab1|b2|...|bn. 
Situação em que a produz ou b1 ou b2...
A aplicação de uma regra de produção denomina-se uma derivação.
Exemplo:
P= {SaX|bX, Xa|b|X} 
Derivação
Seja G=(V,T,P,S) uma gramática. Uma derivação é um par da relação denotada por , com domínio em (VT)+ e contradomínio em (VT)*.
Um par (a,b) da relação é denotado de forma infixa: ab.
Seqüência de Derivação
Seja G=(V,T,P,S)=({S,X},{a,b},{SaS|X,Xba|X},S).
Uma seqüência de derivação para produzir a palavra “aaba” nesta gramática é: S  aS  aaS  aaX  aaba. 
Definição Indutiva de Derivação 
Para toda produção da forma Sb, onde S é o símbolo inicial de G, tem-se que Sb.
Para todo par ab, onde b=uvw, se vt é regra de P, então autw.
Portanto uma derivação é a substituição de uma subpalavra, de acordo com uma regra de produção.
Notação
*	Zero ou mais passos de derivação sucessivos.
+ Um ou mais passos de derivação sucessivos.
n Exatamente n passos de derivação sucessivos.
Uma gramática é um formalismo gerador, pois permite derivar (gerar) todas as palavras da linguagem que representa.
Linguagem Gerada 
Seja G = (V, T, P, S) uma gramática.
A linguagem gerada pela gramática G, denotada por L(G) ou GERA(G), é composta por todas as palavras formadas por símbolos terminais deriváveis a partir do símbolo inicial S.
L(G) = {w  T* | S + w}.
Exemplo 
A gramática abaixo gera o conjunto dos números naturais:
G=(V,T,P,S)=({S, D}, {0,1,...,9}, {SD|DS, D0|1|...|9}, S). 
Por exemplo, gerar 593:
S DS  5S  5DS  59S  59D  593
Exemplo
L = {anbn| n ≥ 1}
G = ({S}, {a, b}, P, S)
P = {S → aSb | S → ε}.
S  aSb  aaSbb  aaεbb  aabb
L = {anbn | n ≥ 1}
Exemplo
Seja a gramática G, dada por suas regras:
S  AB
A  aaA | 
B  Bbb | 
As derivações para a seqüência aaaabb são:
S  AB  aaAB  aaaaAB  aaaaB  aaaaBbb  aaaabb.
Exemplo 1: Seja G a gramática:
S  AB
A  aA | a
B  b
Neste exemplo a gramática possui 4 regras: S  AB, A  aA, A  a e B  b
Utilizando a gramática pode-se obter a palavra aaab efetuando-se as seguintes substituições:
	S  AB : AB
	A  aA: aAB
	A  aA: aaAB
	A  a: aaaB
	B  b: aaab
Derivação. 
O processo de substituir um não-terminal por alguma de suas regras é chamado de derivação.
Árvore de derivação. A geração de uma palavra pelas sucessivas derivações pode ser representada através de uma árvore, chamada árvore de derivação, onde a raiz é o símbolo inicial S. 
Árvore de derivação para a palavra aaab do exemplo anterior.
	S  AB : AB
	A  aA: aAB
	A  aA: aaAB
	A  a: aaaB
	B  b: aaab
ou seja,
Tipos de Gramática: 
Uma gramática é representada por G = (Vn , Vt , P, S), onde :
Vn : Alfabeto finito conhecido como vocabulário não terminal que é usado pela gramática para definir construções auxiliares ou intermediárias na formação de sentenças.
Representação usual : Elementos de Vn em letras maiúsculas.
Vt : Alfabeto terminal, que são os símbolos dos quais as sentenças da linguagem são constituídas.
Representação usual : Elementos de Vt em letras minúsculas, números, delimitadores, operadores aritméticos (início, fim etc.).
P : É o conjunto finito de regras de produção, que são todas as leis de formação utilizadas pela gramática para definir a linguagem.
S: Símbolo não terminal inicial
Tipos de gramáticas
1) Gramática do tipo 0 (Irrestritas)
São aquelas às quais nenhuma limitação é imposta, exceto a existência de pelo menos 1 símbolo não terminal do lado esquerdo das regras. 
Todo o universo das linguagens é gerado por gramáticas deste tipo.
As produções são do tipo
 
Gramática do tipo 1 (Sensíveis ao Contexto)
	Se nas regras de produção for imposta a restrição de nenhuma substituição é aplicada sem causar a redução no tamanho da cadeia gerada, cria-se a classe de gramáticas sensíveis ao contexto.
	As produções são do tipo 
	
Exemplo :
	
3) Gramática do tipo 2 (Livres de Contexto)
	
Apresentam uma restrição adicional de que as regras de produção tem apenas 1(um) elemento não terminal do lado esquerdo ou seja : 	
Exemplo :
	
4) Gramática do tipo 3 (Regulares)
	
Possui a restrição de que as produções substituem um não terminal por uma cadeia de um terminal seguido (direita) (ou precedido (esquerda)), ou não, por um único não terminal.
	
	Produções do tipo : 
	Exemplo :
Ambiguidade
	Considerando a gramática com as seguintes regras:
E  E + E
E  E * E
E  (E)
E  a
Tomando-se a cadeia a+a+a
*
*
Ambiguidade
Duas árvores distintas para a sentença a+a+a, logo a sentença é ambígua e a gramática também.
E
E
E
E
E
E
E
E
E
E
+
+
+
+
a
a
a
a
a
a
*
*
Equivalência de Gramáticas
	Duas gramáticas G1 e G2 são equivalentes se L(G1)=L(G2)
	Equivalência não significa gramáticas iguais
*
*
Equivalência de Gramáticas
	Exemplo:
	Qual a linguagem gerada por cada uma das seguintes gramáticas:
G1
E  T
T  TF
T  F
F  aa
G2
E  aaF
F  E
F  
G3
E  ET
E  aa
T  aa
T  
G4
E  aa
E  Eaa
Equivalência de Gramáticas
	L(Gx)={a2n|n1}
	Portanto as quatro gramáticas são equivalentes
	Observe que G3 é ambígua (sentença aa)
Hierarquia de Chomsky
	Esta hierarquia define quatro tipos de gramáticas
	Os tipos são pois:
	Tipo 0 ou GEF - Gramática com Estrutura de Frase
	Tipo 1 ou GSC - Gramática Sensível ao Contexto
	Tipo 2 ou GLC - Gramática Livre de Contexto
	Tipo 3 ou GR - Gramática Regular
Hierarquia de Chomsky
GEF
LSC-GSC
LLC-GLC
LR-GR
Hierarquia de Chomsky
	Tipo 1 - exemplo:
		S  aSBC
		S  aBC
		CB  BC
		aB  ab
		bB  bb
		bC  bc
		cC  cc
	Qual é a linguagem gerada por esta gramática?
	L(G) = {anbncn|n1}
Hierarquia de Chomsky
	Tipo 2 - exemplo:
		S  aB
		S  bA
		A  a
		A  aS
		A  bAA
		B  b
		B  bS
		B  aBB
	Qual é a linguagem gerada por esta gramática?
	L(G) = {w{a,b}+| w contém número de a’s igual ao número de b’s}
Hierarquia de Chomsky
	Tipo 2 - exemplo 2:
		S  AB
		A  0A11
		A  
		B  0B
		B   
	Qual é a linguagem gerada por esta gramática?
	L(G) = {0n12n0m|n0, m0}
Hierarquia de Chomsky
	Tipo 2 - exemplo 3:
		S  AB
		A  aA
		A  a
		B  bB
		B  b 
	Descreva uma GLC capaz de gerar esta linguagem.
	Considere a seguinte linguagem:
L(G) = {ambn|n1, m1}
Hierarquia de Chomsky
	Tipo 3 - exemplo:
	S  aS
	S  bA
	A  c
	Qual é a linguagem gerada pela GR?
	L(G) = {anbc|n0}
Hierarquia de Chomsky
	Tipo 3 - exemplo 2:
	N  +D|-D
	D  0|1|2|3|4|5|6|7|8|9|0D|1D|2D|3D 	 |4D|5D|6D|7D|8D|9D
	Qual é a linguagem gerada pela GR?
	Números inteiros com sinal.
Hierarquia de Chomsky
	Tipo 3 - exemplo 3:
	N  +D|-D
	D  0|1|2|3|4|5|6|7|8|9|1E|2E|3E|4E 	 |5E|6E|7E|8E|9E
	E  0|1|2|3|4|5|6|7|8|9|0E|1E|2E|3E 	 |4E|5E|6E|7E|8E|9E
	Números inteiros com sinal sem ocorrência de zeros à esquerda.
Hierarquia de Chomsky
	Tipo 2 - exemplo 2:
	N  SD
	S  +|-
	D  ED|E
	E  0|1|2|3|4|5|6|7|8|9
	Gramática GLC equivalente ao exemplo 2 do tipo 3.