Linguagens Formais
Jorge Muniz Barreto
UFSC-INE
2000
Por que estudar
Linguagens Formais?
• A resposta mais usual a esta pergunta é que o
estudo das linguagens formais, sob a forma de
gramáticas gerativas é a base da teoria da
interpretação e compilação. Juntamente com a
Teoria de Automata, como reconhecedores
das palavras válidas definidas nestas
linguagens tem-se um arcabouço teórico
perfeito para a compreensão e estudo de
compiladores.
Aplicações de Linguagens
Formais
• E será que estas gramáticas só serviriam
para isto? Claro que não, e serão
apresentados exemplos distintos do uso de
linguagens formais.
• Exemplos: Estudo de linguagens naturais,
modelos de crescimento em biologia,
modelos de evolução biológica, etc.
Linguística
• Um sistema formal de grande interesse em
teoria da Computação é o das Gramáticas
Gerativas. Estas Gramáticas apareceram
inicialmente no estudo de Linguística para
ajudar a melhor compreender as linguagens
naturais.
• Chama-se Linguagem Natural aquela que é
usada para comunicação entre seres vivos,
em particular, seres humanos.
Uso em Linguagem Natural
• Os linguistas se preocupam não somente
em definir precisamente o que é uma
sentença correta mas também dar uma
descrição da estrutura desta sentença.
Inicialmente, os estudos se concentraram na
Língua Inglesa a qual é atualmente talvez a
mais bem estudada e conhecida.
IA e Linguagem formal
• Para o pesquisador de Ciência da
Computação, essas gramáticas gerativas
tendo forma semelhante a um sistema
formal, fazem crer que, quando se conseguir
ter conhecimento completo da gramática
formal de uma língua falada, tal como o
português, um grande passo teria sido dado
para o computador “entender” português.
Modelos Formais (1/2)
• As gramáticas gerativas foram criadas por
Noam Chomsky. Existem ainda, para o estudo
das linguagens naturais outras abordagens:
• Teoria da estratificação de Sydney
• Lamb que considera a linguagem constituida
de mais de dois níveis (categorias gramaticais
e vocabulário), (palavras não-terminais e
terminais) e sim uma série de níveis ou
estratos.
Modelos Formais (2/2)
• A Teoria Tagmênica de Kenneth Pike para quem a
linguagem é uma variedade de comportamento
humano, como comer, jogar tenis ou nadar. A
principal colaboração desta teoria é a distinção entre
diferenças êmicas e éticas. As éticas podem ser
ignoradas pelo indivíduo que ouve ou produz o som
como o “l'' final de “Brasil'’ freqüentemente
pronunciado “u'', ou o ``th'' de ``tia'' do carioca. As
êmicas tem valor semântico como “carro'' e “caro''
que para um francofone são sons idênticos.
• As gramáticas sistêmicas de Halliday.
Alfabetos
• Um alfabeto é um conjunto finito de
símbolos.
• Algumas vêzes se fala de vocabulário, em
lugar de alfabeto. Neste caso os símbolos são
palavras. Par o objetivo seguido aqui, esta
diferença é irrelevante pois uma palavra pode
ser considerada representada por um símbolo,
como na escrita hieroglífica.
Exemplos de Alfabetos
• {a,e,i,o,u} é o alfabeto constituido pelas
vogais de nosso alfabeto.
• {I,V,X, L,C, M} é o alfabeto formado pelos
símbolos usados na numeração romana.
• {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} é o alfabeto
formado pelos símbolos usados na
numeração arábica.
Definição de Linguagem
• Ao conjunto de todos as seqüências de
elementos do alfabeto que se podem formar
denota-se por A*.
Uma linguagem L sobre um alfabeto
A, também escrita LA é todo
subconjunto de A*.
Exemplo de Linguagem dos
Números Romanos
• Seja o alfabeto R = {I,V,X,L,C,M} do exemplo 2. R* é um
conjunto de cardinalidade 0. Abaixo mostram-se alguns
elementos:
R* = {I,II,III,IIII,V,VV,VVV,VVVV,VXL,XL,...}
que em termos dos símbolos usados no alfabeto 3
significam: 1,2,3,?,5,?,?,?,?,40,...
• As sequencias às quais não corresponde valor, expresso pelo
correspondente número arábico, não são números romanos,
isto é, não pertencem à linguagem dos números romanos.
Modos de Definir uma
Linguagem (1/3)
• Essencialmente existem três modos de
definir uma linguagem:
• Por enumeração de seus elementos,
• Por um modo construtivo chamado
gramática gerativa, ou
• Por propriedades.
Modos de definir uma
Linguagem (2/3)
• Definir uma linguagem por enumeração de
seus elementos só é possível no caso de
linguagem com número finito de palavras.
• A definição por propriedades é uma
definição declarativa, em que certas formas
especiais são ditas pertencer à linguagem.
Modos de definir uma
Linguagem (2/3)
• As gramáticas gerativas consistem em um
algoritmo para gerar as palavras da
linguagem.
• Neste caso faz-se uma partição no alfabeto,
terminais e não terminais, da-se regras de
reescrita, e um elemento não terminal para
início da geração das palavras da
linguagem.
Gramática gerativa
• Uma gramática é a quadrupla:
<N,T,P,n0>
onde:
N: conjunto de símbolos ditos não terminais;
T: conjunto de símbolos terminais;
P: conjunto de regras de reescrita ou de
produção;
n0: raiz ou fonte da linguagem n0  N.
Representacões de regras
• Representação
funcional:
• A  ABa
• Representação como
em um sistema formal
A
ABa
Relação com Sistemas Formais
• A definição de uma linguagem por
gramáticas gerativas tem grande relação
com o estudo dos Sistemas Formais,
podendo mesmo ser considerado como
exemplo destes sistemas.
• Na realidade, a um dado sistema formal
correspondem tantas linguagens geradas por
gramáticas gerativas quantos são os
elementos do vocabulário.
Como ter várias Gramáticas
Gerativas de um Sistema Formal?
• Note que no sistema formal temse um
vocabulário. Não foi ainda especificado o
que é o elemento inicial gerador (algumas
vêzes se faz isto nas regras), nem os
terminais nem os não terminais. Escolhas
diferentes produzem linguagens distintas.
Exemplo de Gramática Gerativa
•
•
•
•
•
•
•
•
N={F,S,C,V,O}
T={Jó,Sô,casa,…}
P={
F  SC
F  SV
C  VO ...
}
N0 = F
• Se supõe o alfabeto não
terminal significando
categorias gramaticais,
tem-se:
• F: Frase
• S: Sujeito
• C: complemento, etc…
• E tem-se uma
representção do português.
Hierarquia de Chomsky
• A Hierarquia de Chomsky classifica as
linguagens segundo o grau de complexidade
das suas regras de reescrita.
• Assim as linguagens são classificadas como
de tipo 0, 1, 2 e 3. As tipo 0 não tem
restrições, as outras que são cada uma mais
restrita que a outra são: sensíveis ao
contexto, livres de contexto e regulares.
Linguagem Tipo 0
• Em uma linguagem tipo zero não há
restrições quanto às regras de reescrita, ou
de produção.
• São as mais difíceis de se tratar.
• Observação: serão usadas letras maiúsculas
para não terminais e minúsculas para
terminais.
Linguagem Tipo 1
• As Linguagens Tipo 1 são também chamadas
sensíveis ao contexto. Nelas se exige apenas que
em cada regra de produção, o comprimento da
palavra original seja igual ou menor que o da
palavra derivada.
• Assim: Aab  Ac não é válida;
• Mas: Ac  Aab o é.
Linguagem Tipo 1:Exemplo
• Seja a linguagem:
(N,T,P,S)
N={S,B,C},
T={a,b,c},
P{S  aSBC,
S  aBC,
CB  BC,
aB  ab, bB  bb
bC  bc, cC  cc}
Usando P1 n-1 vezes:
S  an-1 S(BC) n-1
Usando P2: a n (BC) n
P3 permite : an Bn Cn
P4: an b Bn-1 Cn
P5: an bn Cn
P6 1 vêz e P7 n-1 vêzes:
an bn cn
Prova-se que esta é forma geral
de palavras da linguagem.
Linguagem Tipo 2
• Linguagem Tipo 2 ou Livre de contexto são
as mais usadas. Nelas todos os antecedentes
de regras tem apenas 1 elemento, por
exemplo:
A  Ba
• Neste caso o resultado da transformação de
A independe do que tem antes ou depois ,
isto é, do contexto.
Linguagem Tipo 2: Árvores
• As linguagens de tipo
2 podem ser
representadas com
facilidade por árvores
de derivação:
• Existe 1 e apenas 1 nó
sem ramo chegando,
chamado raiz da
árvore.
• Para cada nó existe
uma seqüência de nós
ligando este nó à raiz
da árvore. O grafo é
conexo.
• Somente um arco
entra em cada nó.
Exemplo de árvore
Seja a gramática:
G=({S,A],{a,b}P,S)onde:
P={S  aAS
Sa
A  SbA
A  SS
A  ba}
Linguagem Tipo 3
• Linguagem Tipo 3 ou Linguagem Regular
ee aquela em que as Regras de produção, ou
tem apenas como consequencia um terminal
ou um terminal seguido de um não terminal.
Ex:
A  aB ou A  a
Nota: Estas linguagens são reconhecidas por
máquina de estados finita.
Árvores para Linguagem T3
• As árvores das linguagens tipo 3 são todas
mais simples que as do tipo 2.
• Árvores, servem para, partindo de suas
folhas reconstruir a árvore. A esta ação
chama-se parser, ou análise sintática,
E até curso mais aprofundado...
Será que sou
como o animal ao
lado?