01.LFA.IntroduçãoLFA

Prévia do material em texto

DCC013 
 
Linguagens Formais 
e Autômatos 
Introdução a Linguagens Formais 
 
 
 Definições Prévias 
 Linguagens 
 Gramática 
 
Linguagens Formais 
2 
Definições Prévias 
 Alfabeto ou Vocabulário: Conjunto finito não 
vazio de símbolos. Símbolo é um elemento 
qualquer de um alfabeto. E 
 Exemplo: 
 {a, b} 
 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
 Cadeia: Concatenação de símbolos de um 
alfabeto. Define-se como cadeia vazia ou nula 
uma cadeia que não contém nenhum símbolo. 
 
Linguagens Formais 
3 
Definições Prévias 
 Exemplo 
 aab 
 123094 
  (cadeia nula) 
 Comprimento de cadeia: Número de símbolos de 
uma cadeia. 
 Exemplo 
 |aab| = 3 
 |123094| = 6 
 |  | = 0 
Linguagens Formais 
4 
Definições Prévias 
 Concatenação de cadeias: Define-se a 
concatenação z de uma cadeia x com uma cadeia 
y, como sendo a concatenação dos símbolos de 
ambas as cadeias, formando a cadeia z = xy. 
Assim, |z| = |x| + |y| 
 Exemplo 
 x = abaa; y = ba  z = abaaba 
 x = ba; y =   z = ba 
Linguagens Formais 
5 
Definições Prévias 
 Produto (concatenação) de alfabetos: É o 
produto cartesiano de 2 conjuntos (alfabetos). 
 Exemplo 
 V1 = {a, b} e V2 = {1, 2, 3} 
 V1.V2 = V1  V2 = {a1, a2, a3, b1, b2, b3} 
 Exemplo 
 Observe que V1  V2  V2  V1 
 
 
Linguagens Formais 
6 
Definições Prévias 
 Exponenciação de alfabetos: São todas as 
cadeias de comprimento n sobre V (Vn). V0={}, 
V1 = V, Vn = Vn-1.V 
 Exemplo 
 V = {0, 1} 
 V3 = V2.V = (V.V).V = {00, 01, 10, 11}.{0, 1} = 
 {000, 001, 010, 011, 100, 101, 110, 111} 
 
Linguagens Formais 
7 
Definições Prévias 
 Fechamento (Clausura) de um Alfabeto: Seja A 
um alfabeto, então o fechamento de A é definido 
como A* = A0  A1  A2  ...  An  ... 
 Portanto A* = conjunto das cadeias de qualquer 
comprimento sobre o alfabeto A. 
 Exemplo 
 A = {1} 
 A* = {, 1, 11, 111, ...} 
 Fechamento Positivo de A = A+ = A* - {} 
Linguagens Formais 
8 
Linguagens 
 Linguagem é uma coleção de cadeias de 
símbolos (de comprimento finito). Estas cadeias 
são denominadas sentenças da linguagem e são 
formadas pela justaposição de elementos 
individuais do alfabeto da linguagem. 
 Linguagem é um subconjunto do fechamento de 
um alfabeto. 
Linguagens Formais 
9 
Linguagens 
 Exemplos: 
  = {a, b}, L1 = {ab, bc} 
 (linguagem formada pelas cadeias ab e bc) 
  = {a, b}, L2 = {abn ou anb | n ≥ 0} 
 
(linguagem formada por todas as cadeias que começam 
com "a" seguido de um número qualquer de "b" ou 
começam com um número qualquer de "a” seguidos de 
um "b", por exemplo ab, abb, aab, aaab, ...) 
 
 
Linguagens Formais 
10 
Linguagens – Métodos de Representação 
 Uma linguagem pode ser representada através 
de três mecanismos básicos: 
1. enumeração das cadeias de símbolos que formam as 
suas sentenças (somente linguagens finitas podem ser 
representadas por este método) 
2. através de um conjunto de leis de formação das 
cadeias (ao conjunto de leis de formação dá-se o 
nome de Gramática) 
3. através de regras de aceitação de cadeias (às regras 
de aceitação dá-se o nome de Reconhecedor) 
Linguagens Formais 
11 
Linguagens – Enumeração 
 Enumeração das cadeias de símbolos que 
formam as suas sentenças: 
 todas as sentenças da linguagem aparecem 
explicitamente na enumeração; 
 a decisão acerca da pertinência ou não de uma 
cadeia à linguagem se faz por meio de uma busca da 
cadeia em questão no conjunto de sentenças da 
linguagem; 
 Exemplo: L = {a, b, ab, ba} 
 (linguagem formada pelas cadeias a, b, ab e ba) 
 
Linguagens Formais 
12 
Linguagens – Leis de Formação 
 Através de um conjunto de leis de formação das 
cadeias (ao conjunto de leis de formação dá-se o 
nome de Gramática). 
 Dada uma cadeia de símbolos, só é possível 
afirmar que tal cadeia pertence à linguagem se 
for possível, aplicando-se as leis de formação 
que compõem a gramática da linguagem, derivar 
(sintetizar) a cadeia em questão. 
 
Linguagens Formais 
13 
Linguagens – Leis de Formação 
 Ao processo de obtenção de uma sentença a 
partir da gramática dá-se o nome de derivação 
da sentença. 
 Exemplos: 
 G = ( {A, B}, {0, 1}, P, A) 
 P : A  0A 
 A  B 
 B  1B 
 B   
 
 
Linguagens Formais 
14 
Linguagens – Leis de Formação 
 Exemplos: 
 G = ( {A, B}, {0, 1}, P, A) 
 P : A  0A 
 A  B 
 B  1B 
 B   
 
L(G) = {0n1m | n, m  e n,m > 0} 
 
Linguagens Formais 
15 
Linguagens – Regras de aceitação de 
cadeias 
 Através de regras de aceitação ou 
reconhecimento de cadeias (reconhecedor ou 
autômato): para decidir se uma cadeia é uma 
sentença da linguagem, basta aplicar a ela as 
regras de aceitação, as quais deverão fornecer a 
decisão acerca da pertinência da cadeia à 
linguagem. 
 
Linguagens Formais 
16 
Linguagens – Regras de aceitação de 
cadeias 
 Exemplo (autômato finito): 
M = ({A, B}, {0, 1}, f, A, {B}) 
f: 
 f(A,0)  A 
 f(A, 1)  B 
 f(B, 1)  B 
 f(B, 0)  A 
 
 
Linguagens Formais 
17 
Gramáticas 
 Formalmente, as gramáticas são caracterizadas 
como quádruplas ordenadas 
G = (N, T, P, S) 
 N representa o vocabulário não terminal 
(variáveis) da gramática. Este vocabulário 
corresponde ao conjunto de todos os símbolos 
dos quais a gramática se vale para definir as leis 
de formação das sentenças da linguagem. 
 Serão denotados em letras maiúsculas: A,X,B,C,… 
Linguagens Formais 
18 
Gramáticas – G = (N, T, P, S) 
 T é o vocabulário terminal (alfabeto), 
contendo os símbolos que constituem as 
sentenças da linguagem. Dá-se o nome de 
terminais aos elementos de T. 
 Letras minúsculas: a, b,…, z, 0, 1,…9, … 
Linguagens Formais 
19 
Gramáticas – G = (N, T, P, S) 
 P representa o conjunto de todas as leis de 
formação (regras) utilizadas pela gramática 
para definir a linguagem. 
 A cada uma destas regras de formação que 
compõem o conjunto P dá-se o nome de 
produção 
 Cada produção P tem a forma: 
   , onde 
 (N T)+ e (N T)* 
Linguagens Formais 
20 
Gramáticas – G = (N, T, P, S) 
 SN é dito o símbolo inicial ou o axioma da 
gramática. Indica onde se inicia o processo de 
geração de sentenças. 
 
 Exemplo 1: 
 G = ({S, A, B}, {a, b}, P, S) 
 P: {S  AB, A  a, B  b} 
Linguagens Formais 
21 
Gramáticas – G = (N, T, P, S) 
 Def 1 – derivação: Uma cadeia  deriva (gera) 
diretamente () uma cadeia  se existe a 
produção 
     P tal que ,(N T)* e (N T)+ 
 Exemplos: 
 aB  ab (pois existe a regra B  b) 
 S  AB (pois existe a regra S  AB) 
 Def 1 – derivação: Uma 
Linguagens Formais 
22 
Ex.1: 
G = ({S, A, B}, {a, b}, P, S) 
P: {S  AB, A  a, B  b} 
Gramáticas – G = (N, T, P, S) 
 Def 2 – vários passos de derivação: Uma cadeia 
 deriva (*) uma cadeia  se 
 1, 2,...,n, tal que =12... n-1n= , n0 
 Se n = 0 então  = , portanto  *, . 
 aB  ab (pois existe a regra B  b) 
 S  AB (pois existe a regra S  AB) 
 Exemplo: Na gramática do exemplo 1: 
S *ab S *aB AB *ab ab *ab 
Linguagens Formais 
23 
Ex.1: 
G = ({S, A, B}, {a, b}, P, S) 
P: {S  AB, A  a, B  b} 
Gramáticas – G = (N, T, P, S) 
 Exemplo (derivação). gramáticas para descrever 
estruturas sintáticas da língua natural. Poderia-
se escrever regras (produções) como: 
 
<frase>  <artigo><substantivo><verbo><artigo><substantivo>.| 
 <artigo><substantivo><verbo>. 
<verbo>  dorme | escuta | ama 
<substantivo>  gato | rádio | rato 
<artigo>  o | a | os | as 
Linguagens Formais 
24 
Gramáticas – G = (N, T, P, S) 
 Desta gramática pode-se obter derivações como: 
 <frase>  <artigo><substantivo><verbo><artigo><substantivo>. 
  o<substantivo><verbo><artigo><substantivo>. 
  o gato <verbo><artigo><substantivo>. 
  o gato ama <artigo><substantivo>. 
  o gato ama o<substantivo>. 
  o gato ama o rato. 
 
 Entretanto, a mesma gramática também permite 
derivar “o gato dorme o rato”, 
 
 
 
Linguagens Formais 
25 
Gramáticas – G = (N, T, P, S) 
 Def 3 – forma sentencial: Uma cadeia (N T)* 
é uma forma sentencial de G se S * ou seja,  
é um embrião para uma cadeia gerada pela 
gramática. 
 Exemplo: Na gramática do exemplo 1: 
aB, AB, Ba, S, ab são formas sentenciais. 
Linguagens Formais 
26 
Gramáticas – G = (N, T, P, S) 
 Def 4 – sentença: Uma forma sentencial, , é 
uma sentença de G se S* e T*. Ou seja, as 
cadeias geradas pela gramática são as sentenças 
de G. 
 Def 5 – L(G): A Linguagem L gerada por uma 
gramática G é definida como o conjunto de 
cadeias geradas por G. Ou seja, 
 L(G) = {xєT* | S *x} ou {x|x é sentença de G} 
 Cadeia e sentença terão o mesmo significado. 
Linguagens Formais 
27 
Gramáticas – G = (N, T, P, S) 
 Exemplo. Gramática G1 = (N1, T1, P1, A), onde: 
 N1 = {A, B} 
 T1 = {0, 1} 
 P1: 
 A  0A 
 A  B 
 B  1B 
 B   
 Verificar que L(G1) = {0n1n | n,m0}. 
Linguagens Formais 
28 
Gramáticas – G = (N, T, P, S) 
 Def 6 – Equivalência de grmáticas: Duas 
gramáticas G1 e G2 são equivalentes sse 
L(G1)=L(G2) 
 Exemplo. 
G1 G3 
S  SSS | a | b L  S 
G2 S  aA | bA | a | b 
S  aSa | aSb | bSa | bSb | a | b A  aS | bS 
 L(G1)=L(G2)=L(G3) = {x | x{a,b}* e |x| mod 2 = 1} 
 
Linguagens Formais 
29 
Gramáticas – Técnicas de definição 
 Lista simples: xxxxx...x 
 A  xA | x ou 
 A  Ax | x 
 
 Exemplo: números naturais 
 N  DN | D 
 D  0 | 1 | 2 | 3 | ... | 9 
 
 
Linguagens Formais 
30 
Gramáticas – Técnicas de definição 
 Lista com separadores: xSxSxSxS...Sx 
 A  xSA | x 
 
 Exemplo:cadeias de a’s separadas por $. 
 S  A$S | A 
 A  aA | a 
 
Linguagens Formais 
31 
Gramáticas – Técnicas de definição 
 Opção, união de duas linguagens: G1ou G2: 
 A  B | C 
 
 Exemplo1: comentário em pascal. 
 C  H | P 
 H  {M} 
 P  (*M*) 
 M  LM | L 
 L  a | b | c |...| z | ‘A’ | ‘B’ | ... | ‘Z’ |  
Linguagens Formais 
32 
Gramáticas – Técnicas de definição 
 Opção, união de duas linguagens: G1ou G2: 
 A  B | C 
 
 Exemplo2: conjunto de números inteiros. 
 Z  P | N 
 P  U | +U 
 N  -U 
 U  DU | D 
 D  0 | 1 |...|9 
Linguagens Formais 
33 
Gramáticas – Técnicas de definição 
 Concatenação de 2 linguagens: 
 C  AB 
 
 Exemplo: números em ponto flutuante. 
 R  N.N | N | .N | N. 
 N  DN | D 
 D  0 | 1 | 2 | 3 | ... | 9 
Linguagens Formais 
34 
Gramáticas – Técnicas de definição 
 Auto aninhamento: 
 A  aAf | c A  aAf | 
 
 Exemplo: expressões aritméticas. 
 
 E  N | E+E | E*E | E/E | E-E | (E) 
 N  DN | D 
 D  0 | 1 | 2 | 3 | ... | 9 
Linguagens Formais 
35 
Gramáticas – Técnicas de definição 
 Auto aninhamento com lista simples: 
 A  aAf | c A  aAf | 
 
 Exemplo: gramática que gera todas as cadeias 
que equilibram adequadamente os parênteses 
da esquerda com os da direita. 
 
 S  SS | (S) |  
Linguagens Formais 
36 
Gramáticas – Técnicas de definição 
 Exercícios. Relações quantitativas. 
1) {aib2i | i  0} = {, abb, aabbbb, ...} 
2) {aibj | j  0 e i > j} = {a, aab, aaaa, aaaabb ...} 
3) {aibj | j = 2i ou i > j} = {, aab, aaaa, aaaabb, abb ...} 
4) {aibjckdm | i = m e j = 3k} = {abbbcd, aabbbcdd, 
 aabbbbbbccdd,...} 
5) {aibj | i  j e i,j > 0} = {abbb, aab, aaabbbb, aaaab...} 
6) {aibjci+j| i,j > 0} = {abcc, aabccc, aabbbccccc, ...} 
7) {anbncn| n  0} = {abc, aabbcc, aaabbbccc, ...}. Não é 
LLC. 
 
Linguagens Formais 
37 
Gramáticas – Classes Gramaticais 
 Até este ponto não foi imposta qualquer 
restrição sobre a gramática ou sobre as 
produções que denotam as leis de formação da 
linguagem que está sendo definida. 
Linguagens Formais 
38 
Gramáticas – Classes Gramaticais 
 As gramáticas gerais têm limitações em relação 
à sua aplicabilidade no contexto do estudo dos 
compiladores, devido às dificuldades que 
acarretam em seu tratamento, sendo que as 
linguagens de programação de interesse não 
exigem toda a generalidade que as gramáticas 
gerais definidas acima são capazes de oferecer. 
 Sendo assim, dividimos as gramáticas em quatro 
classes, que serão vistas a seguir. 
Linguagens Formais 
39 
Gramáticas – Classes Gramaticais 
 Conforme as restrições impostas ao formato das 
produções de uma gramática, a classe de 
linguagens que tal gramática gera varia 
correspondentemente. 
 A teoria mostra que há quatro classes de 
gramáticas capazes de gerar quatro classes 
correspondentes de linguagens, de acordo com a 
denominada Hierarquia de Chomsky. 
Linguagens Formais 
40 
Gramáticas – Classes Gramaticais 
 Hierarquia de Chomsky: 
 Gramáticas com Estrutura de Frase (irrestritas) ou 
do Tipo 0. 
 Gramáticas Sensíveis ao Contexto ou do Tipo 1. 
 Gramáticas Livres de Contexto ou do Tipo 2. 
 Gramáticas Regulares ou do Tipo 3. 
Linguagens Formais 
41