64201

Prévia do material em texto

Módulo 02 - Conceitos Fundamentais: Alfabetos, Cadeias, Linguagem e 
Gramática 
 Definições de Alfabeto, Cadeias, Linguagens 
 Gramática: dispositivo gerador de uma Linguagem. 
 Derivação de cadeias e árvores de derivação. 
2.1 Definições de Alfabeto, Cadeias, Linguagens 
Alfabeto é um conjunto finito de símbolos. Cada símbolo é portanto, uma unidade 
atômica empregada na construção de cadeias e se trata de um conceito primitivo, 
sendo a sua representação visual irrelevante. São exemplos de alfabetos: 
1 = { a, e, i, o, u} 
2 = {0, 1, 2} 
3 = {+, =, #} 
Uma cadeia de caracteres, é uma sequência finita de símbolos de um alfabeto 
justapostos. Exemplo: Seja 1 = { a, e, i, o, u}. São exemplos de cadeias: a, aa, ai, oi, 
ui, eaea, ia, uaa. 
Uma cadeia vazia é uma cadeia sem símbolos e é representada pelo símbolo . 
O comprimento de uma cadeia , é o número de símbolos justapostos que se 
apresentam na mesma. Representa-se como ||. Exemplos: 
Para  = aaaa tem-se que || = 4. 
Para  = a, tem-se que || = 1. 
Para  = , tem-se que || = 0. 
Duas cadeias definidas sobre o mesmo alfabeto podem ser combinadas e formar 
uma terceira a partir da operação de concatenação. A concatenação das cadeias v e 
 é representada por v e é formada pela justaposição de v e . 
Exemplo: 
Seja o alfabeto  = {a, s, m, o, r} 
Seja 1 = somar e 2 = as. Tem-se que 12 = somaras. 
A operação de concatenação é associativa, ou seja (uv)w = u(vw) quaisquer que 
sejam as cadeias u, v e w. 
Uma cadeia v é uma subcadeia de uma cadeia  se e somente se há cadeias x e 
y tal que = xvy. 
Um prefixo (respectivamente, sufixo) de uma cadeia é qualquer seqüência de 
símbolos inicial (respectivamente, final) da cadeia. 
Considere, por exemplo,  = ramos. São prefixos da cadeia : r, ram, ramo, 
ramos. São sufixos de : ramos, amos, mos, os, s.. 
Para cada cadeia  e cada número natural i, define-se i conforme se segue: 

0 =  (cadeia vazia) 

i+1 = i  
Exemplo: Sejam o alfabeto  = {1, 0} e a cadeia  = 01. Tem-se que: 

3 = =010101 

1 =  = 01 

0 =  
O reverso de uma cadeia , denotada por R, é definido como: 
(1) se  = , então R = = .. 
(2) Se  é uma cadeia de comprimento n+1 > 0, então  = ua para algum a  
e w e wR = auR. 
Exemplos: 
Sejam o alfabeto  = {a, b} e  = ba. Tem-se que R = ab. 
Sejam o alfabeto  = {a, t, o, r} e  = ator. Tem-se que R = rota. 
Linguagem formal é um conjunto finito ou infinito, de cadeias de comprimento 
finito, sobre um alfabeto finito e não vazio.. 
Seja o alfabeto  = {a, b}. A seguir, são apresentados exemplos de Linguagens, 
cujas cadeias são definidas sobre o alfabeto . 
a) L1 =  
b) L2 = {} 
c) L3 = {a,ab,ba, bb, aaa} 
 
Além das operações definidas para conjuntos apresentadas no capítulo 1, definem-
se a seguir as operações de concatenação e fechamentos; 
Sejam L1, L2, duas linguagens, a concatenação L1.L2 , ou simplesmente L1L2 é 
definida formalmente como: 
L1L2 = {w = w1w2 | w1 L1 e w2  L2 } 
O fechamento recursivo e transitivo de um alfabeto  é definido como o conjunto 
infinito que contém todas as possíveis cadeias que podem ser construídas sobre o 
alfabeto dado, incluindo a cadeia vazia, e é denotado por *. 
O fechamento transitivo denotado por + representa o conjunto de todas as 
cadeias sobre o alfabeto  excetuando-se a cadeia vazia, ou seja: 

+ = * - {} 
Exemplo: Seja o alfabeto unário  = { 0 }, tem-se que : 
* = {, 0, 00, 000, 0000, 00000, ...} 

+ = {0, 00, 000, 0000, 00000, ...} 
 A complementação de uma linguagem L definida sobre um alfabeto é: 
L’ = * - L 
Exemplo: Seja o alfabeto  = { 0, 1 }, seja a Linguagem L definida sobre o alfabeto 
, com L = {w | w começa com o símbolo 0}. Tem-se que: 
L’ = {w | w começa com o símbolo 0}  {} 
 
2.2 Gramática: dispositivo gerador de uma Linguagem. 
 
Gramáticas são dispositivos geradores das cadeias que pertencem a uma 
Linguagem. 
Formalmente, uma gramática é uma quádrupla G = (V, , P, S), onde: 
V = conjunto finito de símbolos não-terminais. 
 = conjunto finito de símbolos terminais da gramática. Este conjunto também é 
denominado alfabeto. 
S  V e é denominado símbolo inicial ou raiz da gramática; 
P = conjunto de produções ou regras de substituição da gramática. 
Uma regra de produção é representada da seguinte forma: 
 onde,   (V )+ e  (V )*. 
Naturalmente,   (V  )+ informa que no lado esquerdo da produção deve existir 
um ou mais símbolos, terminais ou não-terminais. Analogamente, a expressão   
(V T)* indica que no lado direito da produção podem figurar quaisquer cadeias de 
símbolos terminais, não-terminais e até mesmo isoladamente, a cadeia vazia. 
Exemplo: Seja G1 = (V, , P, S), onde: 
 V = {S, X, Y} 
  = {a, b, c } 
 P = { S  a X 
 X  c Y | bX 
Y  c Y |  } 
 S é o símbolo inicial da gramática. 
Observação: O símbolo “|” é traduzido como “ou”. Assim sendo, escrever 
X  c Y | bX , equivale a representar o seguinte conjunto de regras: 
X  cY ; X  b X ; 
Exemplo: 
 G2 = (V, , P, S), onde: 
 V = {Declaracao, Tipo, Lista, Id} 
  = {int, real, x, y, ; , , } 
Declaracao é o símbolo inicial da gramática. 
O conjunto das produções é representado por: 
P = { Declaracao  Tipo Lista ; 
Tipo  int | real 
 Lista  Id | Id, Lista 
 Id  x | y 
 } 
2.3 Derivação de cadeias e árvores de derivação. 
A aplicação de uma regra de produção  é denominada derivação. A derivação 
é representada pelo símbolo  . 
Exemplo: Considere a Linguagem: 
L = {w | w começa com o símbolo a ou b e termina com a subcadeia aa} 
A gramática geradora da Linguagem L é G3 = (V,  , P, S}, 
onde: V = {S, X, Y, Z} é o conjunto dos símbolos não terminais; 
 = {a, b} é o alfabeto; 
S é o símbolo inicial da gramática; 
P = { S  aX | bX; X  bX | aY; Y aZ | bX; ZaZ | } é o conjunto das 
produções. 
Naturalmente, a palavra w = bbaa pertence a L, o que pode ser verificado através 
da seguinte sequência de aplicações das produções: 
S  b X  a  bbX  bbaY  bbaaZ  bbaaZ  bbaa  bbaa 
Exemplo: Considere a gramática G2 apresentada na seção anterior. 
A seguir, a título de ilustração, são apresentadas aplicações sucessivas das regras 
da gramática G2. Para ainda mais claramente se explanar, as produções são 
apresentadas novamente, enumeradas. 
Declaracao  Tipo Lista ; (regra 1) 
Tipo  int (regra 2) 
Tipo  real (regra 3) 
Lista  Id (regra 4) 
Lista  Id , Lista (regra 5) 
 Id  x (regra 6) 
Id  y (regra 7) 
 
Considere-se a seguinte sequência de derivações, a partir do símbolo inicial 
Declaracao. 
Decalaracao  Tipo Lista ; (aplicação da regra 1) 
 real Lista ; (aplicação da regra 3) 
 real Id, Lista; (aplicação da regra 5) 
 real y, Lista ; (aplicação da regra 7) 
 real y, Id; (aplicação da regra 4) 
 real y, x; (aplicação da regra 6) 
Diz-se que a cadeia real y, x; é gerada pela gramática G2. 
Um segundo exemplo de aplicações sucessivas de produções é apresentado a 
seguir: 
Decalaracao  Tipo Lista ; (aplicação da regra 1) 
 int Lista ; (aplicação da regra 2) 
 int Id; (aplicação da regra 4) 
 int x; (aplicação da regra 6) 
Diz-se que a cadeia int x; é gerada pela gramática G2. 
Seja G = (V, , P, S) uma gramática. Uma derivação, denotada por “” é 
uma relação (confira a definição de relação no módulo 1), com domínio em (V 
 )+ e contra-domínio em (V  )*. 
A relação  pode ser definida como: 
 Para toda a produção da forma S  , tem-se que: S  . 
 Sejam , , ,  cadeias de símbolos (terminais ou não terminais da gramática) e  
  uma regra da gramática então: 
      . 
Derivações em que ocorre a aplicação de pelo menos uma produção são 
denotadas por +. 
Exemplo: Declaracao + real x, y; 
Exemplo: Expressao + int x; 
Uma sequência dezero ou mais derivações é denotada por *. 
Ao conjunto de todas as sentenças  geradas por uma gramática G dá-se o nome 
de linguagem definida pela gramática G, ou simplesmente, L(G). Tem-se que : 
L(G) = {w *| S + w } “ 
 Diz-se que duas gramáticas G1 e G2 são equivalentes se e somente se L(G1) = 
L(G2). 
Exemplo: Seja G1 = { V1, , P1, S1}, onde: 
 V1 = {S1} 
  = {a, b} 
 P1 = {S1  S1a| b } e S1 é o símbolo inicial da gramática. 
 Considere-se também a gramática G2 = { V2, , P2, S2}, onde: 
 V2 = {S2, X} 
  = {a, b} 
 P2 = { S2  bX; X  aX |  } 
 Tem-se que G1 é equivalente a G2, pois ambas geram a Linguagem: 
L = {  |  = ba*} 
 De fato, tem-se que: 
 S1  b 
 S1  S1 a  ba e portanto S1
2 ba 
 S1  S1 a  S1aa  baa e portanto S1
3 ba2 (lembre-se da operação de 
concatenação apresentada anteriormente). 
 S1  S1 a  S1aa  S1aaa baaa e portanto S1
4 ba3 (lembre-se da 
operação de concatenação apresentada anteriormente). 
 S1
n+1 ban, n ≥ 0 
 Por outro lado, tem-se que: 
 S2  bX b = x e portanto S2
2 b 
S2  bX baX  ba = ba e portanto S2
3 ba 
 S2  bX baX  baaX  baa e portanto S2
4 baa 
Assim, S2 
n+2 ban, n ≥ 0 
 
 
 
Exercício resolvido 1 (Fundamentado na questão: ENADE 2008 –39 a) 
Qualquer expressão aritmética binária pode ser convertida em uma expressão 
totalmente parentizada, bastando reescrever cada subexpressão binária a  b como 
(a  b), em que  denota um operador binário. Expressões nesse formato podem ser 
definidas por regras de uma gramática livre de contexto, conforme apresentado a 
seguir. Nessa gramática, os símbolos não-terminais E, S, O e L representam 
expressões, subexpressões, operadores e literais, respectivamente, e os demais 
símbolos das regras são terminais. 
E  ( S O S ) 
S  L | E 
O  + | - | * | / 
L  a | b | c | d | e 
Tendo como referência as informações acima, faça o que se pede a seguir. 
a) Mostre que a expressão (a * (b / c)) pode ser obtida por derivações das regras 
acima. 
 
Tem-se que: 
E (SOS)  (LOS)  (a O S)  (a * S)  (a * E)  (a * (SOS))  (a * (LOS))  
(a * (bOS))  (a * (b/S))  (a * (b/L))  (a * (b/c)) 
 
Exercício Resolvido 2: Considere a Linguagem L definida sobre o alfabeto A = {a, b}, 
cujas palavras são todas palíndromos. Mostre através desta Linguagem que a 
operação de concatenação não é fechada sobre L. 
Resp.: Tem-se que: w1 = bab  L e w2 = aa  L. A concatenação w1w2 = babaa não 
é uma palíndromo e portanto w1w2  L. 
 
Referências 
Gersting, J. L. Fudamentos Matemáticos para a Ciência da Computação, Rio de Janeiro: LTC, 
2001. 
Menezes, P. B. Linguagens Formais e Autômatos Porto Alegre: Bookman, 2010. 
Ramos, A. V. M.; José Neto, J.; Veja I. S. Linguagens Formais Teoria, Modelagem e 
Implementação, Porto Alegre: Bookman, 2009. 
Rosa, J. L. G. Linguagens Formais e Autômatos Rio de Janeiro: LTC, 2010.