Baixe o app para aproveitar ainda mais
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 12 = 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; ZaZ | } é 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.
Compartilhar