Baixe o app para aproveitar ainda mais
Prévia do material em texto
Linguagens Formais Prof. Marcio Klein Linguagens Formais Prof. Marcio Klein Linguagens Linguagens Linguagens - Exemplos Linguagens - Especificação Linguagens - Especificação Exemplo: L = {w | w mod 2 = 0} Linguagens - Especificação Linguagens – Operações sobre União Exemplo Interseção Exemplo Linguagens – Operações sobre Diferença Exemplo Complemento Exemplo Linguagens – Operações sobre Linguagens – Operações sobre De Morgan Linguagens – Operações sobre Concatenação Exemplo Exemplo Linguagens – Operações sobre Estrela de Kleene Expressões Regulares Prof. Marcio Klein 2012/1 Linguagens – Exercícios 1. Uma mensagem interceptada por uma empresa, era composta de cadeias que continham somente os caracteres {a,b,c,d} e havia a indicação: L = {(ad)mbp(cb)mdp | m>=1, p>=0} Descreva quais palavras abaixo fazem parte da linguagem definida para esta mensagem. a) bcbddd b) adbddd c) adadbcbcbcb d) adadadbbbcbcbcbdd e) adadbbbcbcbddd Linguagens – Exercícios Prof. Marcio Klein 2012/1 De três exemplos de palavras para cada uma das linguagens Linguagens – Exercícios 4) Uma mensagem composta apenas por cadeias de caracteres com as letras {a,b,c,d} e tem a seguinte indicação: L = {a,c,d}*ba{b,c}dc{a,b}* Indique quais das seguintes palavras pertencem à linguagem definida pela mensagem: a. ( ) bbacdca b. ( ) acabcdca c. ( ) cbaddc d. ( ) dbadca e. ( ) bacdcbbb Gramática Prof. Marcio Klein Gramática Conjunto de princípios que regem o funcionamento de uma língua. A gramática orienta como as palavras podem ser combinadas ou modificadas para que as pessoas possam comunicar-se com facilidade e precisão. Não é preciso que uma língua possua escrita para ser dotada de gramática. As línguas indígenas, por exemplo, embora sejam apenas faladas, têm seus próprios princípios de funcionamento. (Dicionário Online Português) Gramática Anteriormente foi visto que uma linguagem é definida formalmente por um subconjunto da combinação de símbolos de um determinado alfabeto expressões regulares. Uma gramática é, basicamente, um conjunto finito de regras cuja aplicação sucessiva gera as palavras de uma determinada linguagem. O conjunto de todas as palavras geradas por uma linguagem define a linguagem. Gramática Uma gramática é uma quádrupla ordenada: G = (S,V, S, P) onde: Sé o alfabeto terminal para a gramática V é o alfabeto não terminal ou alfabeto de variável para a gramática S é o símbolo inicial para a gramática P é o conjunto de produções da gramática. Gramática - Exemplo Prof. Marcio Klein 2012/1 Como primeiro exemplo, consideremos a “linguagem” de parênteses casados. Parênteses casados incluem todas as cadeias balanceadas de parênteses esquerdo e direito. Exemplos: (( )), ( )( ), (( )(( ))) Contra exemplo: ( )), (( )( ), ((( ( ))) Gramática - Exemplo A gramática que cria a linguagem de parênteses casados tem a forma: GPC= ({(, )}, {S}, S, { S( ), S (S), SSS}) Onde: {(,)} corresponde ao alfabeto terminal {S} é o alfabeto de variáveis S é o símbolo inicial da gramática { S( ), S (S), SSS} é o conjunto de produção da gramática Exemplo: obtenção ou derivação de (( )( )): S (S)(SS) (( )S) (( )( )) Gramática – Regras de Produção São pares do tipo (a, b), representados por ab, onde a (V S)+ e b (V S)*. Definem as condições de geração das palavras da linguagem. Abreviação: ab, ac, ..., ax corresponde a ab|c|...|x . A aplicação de uma regra de produção chama-se uma derivação. Exemplo: P= {S aX | bX, X a | b | aX | bX | λ } Gramática – Derivação Seja G=(S,V,S,P) uma gramática. Uma derivação é um par da relação denotada por , com domínio em (VS)+ e contradomínio em (VT)*. Um par (a,b) da relação é denotado da forma: ab. Seqüência de Derivação Seja G=(S,V,S,P)=( {a,b}, {S,X},S,{SaS|X, X ba|X}) Uma seqüência de derivação para produzir a palavra “aaba” nesta gramática é: S aS aaS aaX aaba Gramática - Exercício 1. Dado o alfabeto {a, b}, o conjunto de variáveis {S}, o símbolo inicial S, e as regras de produção: {S aSb, S ba}: a) Apresente a gramática desta linguagem na forma: G=(S,V,S,P) b) Apresente 4 palavras que pertençam a esta linguagem c) Determine a Expressão Regular que define esta linguagem Gramática - Exercício 2. Dado o alfabeto {a, b,c}, o conjunto de variáveis {S, A,B, C}, o símbolo inicial S, e as regras de produção: {S A, A BaC, B bB | b, C cC | c}: a) Apresente a gramática desta linguagem na forma: G=(S,V,S,P) b) Apresente 4 palavras que pertençam a esta linguagem c) Determine a Expressão Regular que define esta linguagem Gramática - Exercício • 3. Seja a gramática geradora dos conjunto dos números naturais: • G=(S,V,S,P)=({0,1,...,9}, {S, D},S,{SD|DS, D0|1|...|9}) Apresente a derivação para que ela gere o número 475 4. Qual a linguagem definida por G = ({a,b}, {S,A,B}, S, { S AB, Aa|AS, Bb}) Gramática - Exercício 5. Apresente exemplos de palavras criadas a partir das gramáticas abaixo e procure identificar a linguagem criada por elas: a) G1= ({a, b}, {S}, S, { SaSb, S ab}) b) G2= ({a, b}, {S}, S, { S aSa | bSb | a | b }) c) G3= ({0, 1}, {S, A, B}, S, { S 0B | 1A A0 | 0S | 1AA B 1 | 1S | 0BB } Gramática – Hierarquia de Chomsky Chomsky classifica as gramáticas nos seguintes tipos: J.L.Rangel - Ling. Formais – Apostila PUC / Wikipedia Tipo 0 - gramática com estrutura de frase, ou gramática sem restrição, ou irrestrita (às quais nenhuma limitação é imposta) Tipo 1: gramáticas sensíveis ao contexto, ou gsc Tipo 2: gramáticas livres de contexto, ou glc Tipo 3: gramáticas regulares Se uma linguagem tem uma gramática tipo 0, ela é uma linguagem tipo 0; se do tipo 1, ela é uma linguagem tipo 1, e assim por diante. Gramática – Hierarquia de Chomsky J.L.Rangel - Ling. Formais – Apostila PUC / Wikipedia Os dois últimos níveis ( 2 e 3) são muito utilizados na descrição de linguagens de programação e na implementação de interpretadores e compiladores. Gramática Linear Uma gramática linear é uma gramática livre de contexto¹ que tem no máximo um símbolo não- terminal no lado direito de suas produções (flecha). a) Gramática Linear à Direita (GLD): AwB | w | l b) Gramática Linear à Esquerda (GLE): A Bw| w | l c) Gramática Linear à esquerda e à direita Exemplo: G = ({a, b}, {S}, S, {S → aSb | S → l}) Linguagem gerada: Uma linguagem linear é uma linguagem gerada por alguma gramática linear Gramática Livre de Contexto A gramática livre de contexto (tipo 2) contém do lado esquerdo das produções (flecha) somente uma variável Uma Linguagem L sobre um alfabeto Sé livre de contexto (ou tipo 2) se pode ser gerada por uma gramática livre de contexto Exemplos: a gramática do parênteses casado, a geradora dos números naturais e as apresentadas no exercício 2 anteriormente apresentado são gramáticas livres de contexto. Gramática Sensível a Contexto A seguinte linguagem é sensível a contexto: G = ({a, b, c}, {S, B, C}, S, {S aSBC | aBC; CB BC; aB ab; bB bb; bC bc; cC cc } Exemplo de palavra da linguagem definida por esta gramática: S aBC abC abc Gramática Recursivamente Enumerável Qual quergramática é do tipo 0, isto é, não existem restrições quanto a forma de suas produções, sendo a gramática e a linguagem que geram denominadas de Linguagens Recursivamente Enumeráveis. Quanto menor é a hierarquia de Chomsky maior é complexidade da gramática e linguagem gerada. Relação entre a Hierarquia de Chomsky, o modelo da gramática e reconhecedor Gramática Livre de Contexto - Exercícios 1. De exemplos de palavras e procure identificar qual linguagem a seguinte gramática livre de contexto gera: Garcia Rosa,J.L.;P39 G = ({0, 1}, {S, A, B}, S, {S 0A | 1A | 0B | 1B A 0 | 0S | 1AA B 1 | 1S | 0BB } Gramática Livre de Contexto - Exercícios 2. Considere a gramática G definida pelo alfabeto S= {a, b, c, d} e pelas produções: S abSc | A A cAd | cd (a) Dar uma derivação da palavra ababccddcc. (b) Use a notação de conjuntos para definir L(G). (a) S abSc ababScc ababAcc ababcAdcc ababcaccddcc (b) L(G) = {(ab)ncndncn}
Compartilhar