02LFA Linguagens gramaticas

Prévia do material em texto

Ciência da Computação 
Prof. Cristiano Bertolini 
Linguagens Formais e Autômatos 
Linguagens e gramáticas 
Prof. Cristiano Bertolini 
Roteiro 
  Alfabetos, Palavras e Linguagens 
  Gramáticas 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
  Alfabetos 
–  É um conjunto finito de símbolos 
–  Pode ser vazio 
–  Símbolo: Entidade básica sem definição formal 
–  Exemplos: Letras, dígitos, ícones, etc. 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
  Palavras 
–  É uma seqüência finita de símbolos (do alfabeto) 
justapostos 
–  Palavra vazia: ε 
–  Alfabeto: Σ 
–  Conjunto de todas as palavras possíveis sobre Σ: Σ* 
–  Σ+ = Σ* - {ε} 
–  Exemplos de palavras sobre Σ = {a, b}: ε, a, b, aa, ab, ba, 
bb, ... 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
  Tamanho de uma Palavra 
–  É o número de símbolos existentes na palavra 
–  Se w é uma palavra, o tamanho de w é 
representado por |w|. 
–  Por exemplo: Se w = aaba, então |w| = 4. 
–  |ε| = 0. 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
  Concatenação de Palavras 
–  Operação binária, sem representação. 
–  É a justaposição de duas ou mais palavras, 
produzindo uma terceira que é formada pelos 
símbolos da primeira, na ordem em que ocorrem, 
seguidos pelos símbolos da segunda, também na 
ordem em que ocorrem e assim sucessivamente. 
–  Exemplo: Se v=aa e w=ba então x=vw=aaba e 
y=wv=baaa. 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
  Propriedades da Concatenação 
–  Associatividade: v(wt) = (vw)t 
–  Elemento Neutro: εw = w = wε 
–  v=aa, w=b, t=a  v(wt) = (vw)t = aaba 
–  u=aaba  εu = aaba = uε 
Prof. Cristiano Bertolini 
Alfabetos, Palavras e 
Linguagens 
  Concatenação Sucessiva 
–  De uma palavra repetidas vezes com ela mesma 
–  Notação: wn, onde n ≥ 0 é o número de vezes que 
a palavra é repetida 
–  w3 = www 
–  w1 = w 
–  w0 = ε, para w ≠ ε 
–  (ab)3 = ababab 
Prof. Cristiano Bertolini 
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” 
Prof. Cristiano Bertolini 
Gramáticas 
  Exemplo: 
 G = ( V = {S, X}, 
 T = {a, b}, 
 P = {S  a | aX, 
 X  b | bX}, 
 S ) 
Prof. Cristiano Bertolini 
Gramáticas 
  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. 
–  A aplicação de uma regra de produção chama-se uma 
derivação 
–  P= {SaX|bX, Xa|b|X} 
Prof. Cristiano Bertolini 
Gramáticas 
  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 
Prof. Cristiano Bertolini 
Gramáticas 
  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 
Prof. Cristiano Bertolini 
Gramáticas 
  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 
Prof. Cristiano Bertolini 
Gramáticas 
  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 
Prof. Cristiano Bertolini 
Gramáticas 
  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}. 
Prof. Cristiano Bertolini 
Gramáticas 
  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 
Prof. Cristiano Bertolini 
Gramáticas 
  Gramáticas Equivalentes 
–  Duas gramáticas, G1 e G2 são ditas ser 
equivalentes se e somente se geram a mesma 
linguagem, isto é: 
–  GERA(G1) = GERA(G2) 
Prof. Cristiano Bertolini 
Leitura 
  Capítulo 2 do livro Linguagens Formais e 
Automatos 
  Exercícios página 39 
–  2.2, 2.7, 2.8