Linguagens Formais e Autômatos linguagens e gramaticas

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), SSS})
Onde:
 {(,)} corresponde ao alfabeto terminal
 {S} é o alfabeto de variáveis
 S é o símbolo inicial da gramática
 { S( ), S (S), SSS} é 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 ab, onde 
a  (V S)+ e b  (V S)*.
Definem as condições de geração das palavras da 
linguagem.
Abreviação: ab, ac, ..., ax corresponde a 
ab|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 (VS)+ e contradomínio em (VT)*.
Um par (a,b) da relação é denotado da forma: 
ab.
 Seqüência de Derivação
 Seja G=(S,V,S,P)=( {a,b}, {S,X},S,{SaS|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,{SD|DS, D0|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, Aa|AS, Bb}) 
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, { SaSb, S ab})
 b) G2= ({a, b}, {S}, S, { S aSa | bSb | a | b })
 c) G3= ({0, 1}, {S, A, B}, S, { S 0B | 1A
A0 | 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): AwB | 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}