Linguagens Formais
Definições Prévias
Linguagens
Gramática
Fonte: http://www.icmc.sc.usp.br/~mdgvnune/download/sce5832/Teoria.html
Linguagens Formais
Definições Prévias
Alfabeto ou Vocabulário: Conjunto finito não vazio de
símbolos. Símbolo é um elemento qualquer de um
alfabeto.
Ex: {a,b}
{0,1,2,3,4,5,6,7,8,9}
Cadeia: Concatenação de símbolos de um alfabeto.
Define-se como cadeia vazia ou nula uma cadeia que
não contém nenhum símbolo.
Ex: aab
123094
l - cadeia nula
Linguagens Formais
Definições Prévias
Comprimento de cadeia: Número de símbolos de uma
cadeia.
Ex: |aab| = 3
|123094|=6
|l|=0
Concatenação de cadeias: Define-se a concatenação z
de uma cadeia x com uma cadeia y, como sendo a
concatenação dos símbolos de ambas as cadeias,
formando a cadeia xy. |z| = |x| + |y|
Ex: x = abaa; y = ba  z = abaaba
x = ba; y = l  z = ba
Linguagens Formais
Definições Prévias
Produto de alfabetos: É o produto cartesiano de
alfabetos.
Ex: V1 = {a,b} V2 = {1, 2, 3}  V1.V2 = V1xV2 =
{a1, a2, a3, b1, b2, b3}
Observe que V1.V2  V2.V1
Exponenciação de alfabetos: São todas as cadeias de
comprimento n sobre V (Vn). V0={l}, V1=V, Vn=Vn-1.V
Ex: V = {0, 1}
V3 = V2.V = (V.V).V = {00, 01, 10, 11}.{0, 1} = {000,
001, 010, 011, 100, 101, 110, 111}
Linguagens Formais
Definições Prévias
Fechamento (Clausura) de um Alfabeto: Seja A um
alfabeto, então o fechamento de A é definido como
A* = A0  A1  A2  ...  An  ...
Portanto A* = conjunto das cadeias de qualquer
comprimento sobre o alfabeto a.
Ex: A = {1}
A* = {l, 1, 11, 111, ...}
Fechamento Positivo de A: A+ = A* - {l}
Linguagens Formais
Linguagens
Linguagem é uma coleção de cadeias de símbolos, de
comprimento finito. Estas cadeias são denominadas
sentenças da linguagem, e são formadas pela
justaposição de elementos individuais, os símbolos ou
átomos da linguagem.
Linguagens Formais
Linguagens
Ex: {ab, bc} ( linguagem formada pelas cadeias ab e
bc)
{abn,anb; n=0} ( linguagem formada por todas as
cadeias que começam com "a" seguido de um número
qualquer de "b"'s ou começam com um número qualquer
de "a"'s seguidos de um "b", por exemplo ab, abb,
aab, aaab, ...)
Linguagens Formais
Linguagens
Métodos de Representação de Linguagens
Uma linguagem pode ser representada através de três
mecanismos básicos:
1) enumeração das cadeias de símbolos que formam as
suas sentenças (somente linguagens finitas podem ser
representadas por este método)
2) através de um conjunto de leis de formação das
cadeias (ao conjunto de leis de formação dá-se o
nome de Gramática)
3) através de regras de aceitação de cadeias (às
regras de aceitação dá-se o nome de Reconhecedor)
Linguagens Formais
Linguagens
Enumeração
Enumeração das cadeias de símbolos que formam as
suas sentenças: todas as sentenças da linguagem
aparecem explicitamente na enumeração, e a decisão
acerca da pertinência ou não de uma cadeia à
linguagem se faz por meio de uma busca da cadeia em
questão no conjunto de sentenças da linguagem;
Exemplo: L = {a, b, ab, ba} ( linguagem formada pelas
cadeias a, b, ab e ba)
Linguagens Formais
Linguagens
Leis de Formação
Através de um conjunto de leis de formação das
cadeias (ao conjunto de leis de formação dá-se o
nome de Gramática): dada uma cadeia de símbolos, só
é possível afirmar que tal cadeia pertence à linguagem
se for possível, aplicando-se as leis de formação que
compõem
a
gramática
da
linguagem,
derivar
(sintetizar) a cadeia em questão. Ao processo de
obtenção de uma sentença a partir da gramática dáse o nome de derivação da sentença.
Linguagens Formais
Linguagens
Exemplo:
G = ( {A, B}, {0, 1}, P, A)
P: A
A 
B 
B 
 0A
B
1B
l
Linguagens Formais
Linguagens
Exemplo:
G = ( {A, B}, {0, 1}, P, A)
P: A
A 
B 
B 
 0A
B
1B
l
Resp.: L(G) = {0n1m; n, m=0}
Linguagens Formais
Linguagens
Regras de aceitação de cadeias
Através de regras de aceitação ou reconhecimento de
cadeias (reconhecedor ou autômato): para decidir se
uma cadeia é uma sentença da linguagem, basta
aplicar a ela as regras de aceitação, as quais deverão
fornecer a decisão acerca da pertinência da cadeia à
linguagem.
Linguagens Formais
Linguagens
Exemplo:
M = ({A, B, {0, 1}, f, A, {B})
f : f(A,0)  A
f(A, 1)  B
f(B, 1)  B
f(B, 0)  A
A Linguagem reconhecida é a de cadeias de 0's e 1's,
terminando necessariamente com 1.
Linguagens Formais
Gramáticas
Formalmente as gramáticas, são caracterizadas como
quádruplas ordenadas
G = ( Vn, Vt, P, S)
onde:
Vn representa o vocabulário não terminal da
gramática. Este vocabulário corresponde ao conjunto
de todos os símbolos dos quais a gramática se vale
para definir as leis de formação das sentenças da
linguagem.
Linguagens Formais
Gramáticas
Vt é o vocabulário terminal, contendo os símbolos que
constituem as sentenças da linguagem. Dá-se o nome
de terminais aos elementos de Vt.
P representa o conjunto de todas as leis de formação
utilizadas pela gramática para definir a linguagem.
Para tanto, cada construção parcial, representada por
um não-terminal, é definida como um conjunto de
regras de formação relativas à definicão do nãoterminal a ela referente. A cada uma destas regras
de formação que compõem o conjunto P dá-se o nome
de produção da gramática.
Linguagens Formais
Gramáticas
Cada produção P tem a forma:

  (Vn U Vt)+;
  (Vn U Vt)*
S є Vn denota a principal categoria gramatica de G; é
dito o símbolo inicial ou o axioma da gramática. Indica
onde se inicia o processo de geração de sentenças.
Ex.1: G = ({S, A, B{, {a, b}, P, S)
P: S => AB
A => a
B => b
Linguagens Formais
Def1. Uma cadeia  g  gera diretamente () uma cadeia  d  se
(g  d)  P; ,  є (Vn U Vt)* ; g є (Vn U Vt)+
No Ex.1.: aB  ab; S  
Def2. Uma cadeia  gera ( ) uma cadeia  se
$ g1, g2,... gn, tal que  = g1 g2 ...  gn =  , n 0.
Se n = 0 :  =  portanto    para "
No Ex.1.: S  ab; S  a; AB  ab; ab  ab
Def3. Uma cadeia   (Vn  Vt)* é uma forma sentencial de G se S   ou
seja,  é um embrião para uma cadeia gerada pela gramática.
No Ex.1: aB, AB, Ba, S, ab são formas sentenciais.
Linguagens Formais
Uma forma sentencial, , é uma sentença de G se S   e   Vt*.
Ou seja, as cadeias geradas pela gramática são as sentenças de
G.
Def4. A Linguagem L gerada por uma gramática
G é definida como o conjunto de cadeias
geradas por G. Ou seja,
L(G) = {x є Vt*| S  x} ou {x|x é sentença de G}
Linguagens Formais
Gramáticas
Exemplo:
Gramática G1 = (V1, S1, P1, A)
onde:
V1 = {A, B}
S1 = {0, 1}
P1:
A  0A
A  B
B  1B
B  l
Exercício: Verifique que L(G) = {0n1m}
Faça a árvore de derivação para x=00111
Linguagens Formais
Gramáticas
Def5. Duas gramáticas G1 e G2 são equivalentes sse L(G1) =
L(G2)
Def6. Uma sentença é ambígua se $ duas ou mais seqüências de
derivação que a define.
Def7. Uma gramática é ambígua se possui alguma sentença
ambígua.
Ex2. G: S => A B
A => A A | B | a
B => B c d | A
Verifique se x= aaacd é ambígua.
Linguagens Formais
Gramáticas
Até este ponto não foi imposta qualquer restrição
sobre a gramática ou sobre as produções que denotam
as leis de formação da linguagem que está sendo
definida. As gramáticas gerais têm limitações em
relação à sua aplicabilidade no contexto do estudo dos
compiladores, devido às dificuldades que acarretam em
seu tratamento, sendo que as linguagens de
programação de interesse não exigem toda a
generalidade que as gramáticas gerais definidas acima
são capazes de oferecer.
Linguagens Formais
Gramáticas
Torna-se atraente o estudo de casos particulares, de
aplicação mais restrita, porém suficiente para resolver
os problemas levantados ao se projetar compiladores
para linguagens de interesse. Sendo assim, dividimos
as gramáticas em quatro classes, que serão vistas a
seguir.
Linguagens Formais
Gramáticas
Classes Gramaticais
Conforme as restrições impostas ao formato das
produções de uma gramática, a classe de linguagens
que tal gramática gera varia correspondentemente. A
teoria mostra que há quatro classes de gramáticas
capazes de gerar quatro classes correspondentes de
linguagens, de acordo com a denominada Hierarquia de
Chomsky.
Linguagens Formais
Gramáticas
•Gramáticas com Estrutura de Frase ou Tipo 0
•Gramáticas Sensíveis ao Contexto ou Tipo 1
•Gramáticas Livres de Contexto ou Tipo 2
•Gramáticas Regulares ou Tipo 3
Linguagens Formais
Gramáticas GEF
Gramáticas com Estrutura de Frase ou Tipo 0
São aquelas às quais nenhuma limitação é imposta.
Obviamente, todo o universo das linguagens que se
pode definir através dos mecanismos generativos
definidos pelas gramáticas corresponde exatamente ao
conjunto das linguagens que esta classe de gramáticas
é capaz de gerar. Esta classe de gramáticas a
hierarquia de Chomsky classifica como sendo a das
Gramáticas com Estrutura de Frase (GEF) ou Tipo 0.
Para essas gramáticas, as produções são todas da
forma:
  ,   (Vn U Vt)+,   (Vn U Vt)*.
Linguagens Formais
Gramáticas GEF
Exemplo:
G = ({A, B, C}, {a, b}, P, A)
P:
A  BC
BC  CB
B  b
C  a
Linguagens Formais
Gramáticas GEF
Exemplo:
G = ({A, B, C}, {a, b}, P, A)
P: A  BC
BC  CB
B  b
C  a
Resp.: L(G) = {ba, ab}
Linguagens Formais
Linguagens LEF
Definição 0: As linguagens geradas pelas
Gramáticas com Estrutura de Frase ou
do Tipo 0 são chamadas de Linguagens
com Estrutura de Frase (LEF) ou
Linguagens do Tipo 0.
Linguagens Formais
Gramáticas GSC
Gramáticas Sensíveis ao Contexto ou Tipo 1
Se às regras de substituição for imposta a restrição
de que nenhuma substituição possa reduzir o
comprimento da forma sentencial à qual a substituição
é aplicada, cria-se uma classe de gramáticas ditas
sensíveis ao contexto. As gramáticas que obedecem a
estas restrições pertencem, na hierarquia de
Chomsky, ao conjunto das Gramáticas Sensíveis ao
Contexto (GSC) ou do Tipo 1.
Linguagens Formais
Gramáticas GSC
Para as GSC, as produções são todas da forma
  , com ||  || onde ,   (Vn U Vt)+
(há uma exceção permitida: S  l, se S não ocorre do
lado de direto de nenhuma regra)
Linguagens Formais
Gramáticas GSC
Essas gramáticas são chamadas de sensíveis ao
contexto por tornarem possível a definição de regras
do tipo:
Ag  g,
onde A Vn,  (Vn U Vt)+, , g (Vn U Vt)*
Ou seja, A, no contexto de  e g, é substituído por .
Linguagens Formais
Gramáticas GSC
Exemplo:
G = ({S, B, C}, {a, b, c}, P, S)
P : S  aSBC
S  aBC
CB  BC
aB  ab
bB  bb
bC  bc
cC  cc
Resp.: L(G) = {anbncn | n>=1}
Linguagens Formais
Linguagens LSC
Definição 1: As linguagens geradas pelas
Gramáticas Sensíveis ao Contexto ou do Tipo 1
são chamadas de Linguagens Sensíveis ao
Contexto (LSC) ou Linguagens do Tipo 1.
Resultado 1:
Toda gramática do tipo 1 é também do tipo 0.
Corolário 1:
Toda LSC é também uma LEF (mas nem toda LEF
é LSC).
Linguagens Formais
Gramáticas GLC
Gramáticas Livres de Contexto ou Tipo 2
As Gramáticas Livres de Contexto (GLC) ou do Tipo 2
são aquelas cujas regras de produção são da forma:
A
onde A  Vn,   (Vn U Vt)*
Ou seja, quando do lado esquerdo da regra há apenas
um símbolo não-terminal.
Linguagens Formais
GLC e LLC
Definição 2: As linguagens geradas pelas Gramáticas Livres de
Contexto ou do Tipo 2 são chamadas de Linguagens Livres de
Contexto (LLC) ou Linguagens do Tipo 2.
Resultado 2:
Nem toda gramática do tipo 2 é também do tipo 1. Isso acontece
porque as regras da forma A  l não satisfazem a restrição de
comprimento, pois |A| > | l|, já que 1 > 0.
Resultado 2´:
Apesar do Resultado 2, é possível mostrar que toda LLC é também
uma LSC (mas nem toda LSC é uma LLC).
(qualquer GLC pode ser transformada em uma gramática equivalente
à original que satisfaz simultaneamente as definições de GLC e de
GSC)
Linguagens Formais
BNF
Outra maneira de se representar as Gramáticas Livres de Contexto
é através da Forma Normal de Backus.
BNF
Neste caso, => é substituído por ::= e os não terminais são ladeados por
<>
No caso de repetições de lado esquerdo:
<A> ::= a1
<A >::= a2
:
<A> ::= an
escreve-se: <A> ::= a1| a2| ...| an
Os símbolos <,> , :, =, | formam a metalinguagem, ou seja, são símbolos que
não fazem parte da linguagem mas ajudam a descrevê-la.
Linguagens Formais
GLC e LLC
Exemplo:
G = {Vn, Vt, P, S} onde:
Vn = {<sentença, <sn, <sv, sujeito, <predicado, <artigo, <substantivo, <verbo,
<complemento}
Vt = {o, a, peixe, comeu, isca}
S = <sentença
P=
1. <sentença> ::= <sn><sv>
2. <sn> ::= <artigo><substantivo>
3. <sv> ::= <verbo><complemento>
4. <complemento> ::= <artigo><substantivo>
5. <artigo> ::= o|a
6. <verbo> :: = mordeu
7. <substantivo> ::= peixe|isca
Exercícios:
a)
verifique se a cadeia “a isca mordeu o peixe” é uma sentença de L(G).
b)
Dê exemplos de sentenças de L(G), construindo árvores de derivação sintática.
Linguagens Formais
GLC e LLC
Exemplo 1:
G = ({S}, {a, +, *, (, )}, P, S)
P :
S  S * S
S  S + S
S  (S)
S  a
L(G) = conjunto das expressões aritméticas envolvendo
*, +, ( ) e a.
Um exemplo de cadeia formada por esta gramática é
a * (a + a).
Linguagens Formais
GLC e LLC
Exemplo 2:
G = ({S, A, B}, {a, b}, P, S)
P : S  aB | bA
A  a | aS | bAA
B  b | bS | aBB
L(G) = { x  Vt+ | x contém número de a's igual ao
número de b's }
Exercício: mostre que isso é verdade, por indução
sobre o comprimento de uma sentença.
Hipótese Indutiva: para todo w  Vt*,
1) S * w sse w consiste de = no. de a´s e b´s.
2) A * w sse w tem um a a mais que b´s.
3) B * w sse w tem um a b mais que a´s.
Linguagens Formais
GLC e LLC
Exemplo 3: Processo inverso: dada L(G), definir G.
L(G) = {0n12n0m | n ≥0, m ≥0 }
Linguagens Formais
GLC e LLC
Exemplo 3: Processo inverso: dada L(G), definir G.
L(G) = {0n12n0m | n ≥0, m ≥0 }
Resp.:
G= ({S, A, B}, {0, 1}, P, A)
P:
S  AB
A  0A11 | l
B  0B | l
Linguagens Formais
GLC e LLC
Exemplo 4:
L(G) = {ambn | m ≥ 0, n ≥ 0 }
Linguagens Formais
GLC e LLC
Exemplo 4:
L(G) = {ambn | m≥0, n≥0 } ou a*b*
Resp.:
G=({S, A, B}, {a, b}, P, S)
P: S  AB
A  aA | a
B  bB | b
Obs.: Caso geral:
Se S  S| então L(G) = 
Linguagens Formais
GLC e LLC
Exemplo 5:
L(G) = {anbn | n ≥ 1}
Linguagens Formais
GLC e LLC
Exemplo 5:
L(G) = {anbn | n ≥ 1}
S  aSb | ab
Linguagens Formais
GLC e LLC
Exemplo 6:
G = ({E, T, F}, { i, +, -, *, /, ^}, P, E)
P :
E  T | E + T | E - T
T  F | T * F | T / F
F  i | F ^ i
(recursiva à esquerda)
Verifique a ordem de precedência dos operadores via
árvore de derivação sintática:
i
i
i
i
+
*
+
i
i
i
i
*
*
+
+
i + i ^ i
i
i
i
Linguagens Formais
Precedência Operadores
Precedência de Operadores - Concluindo:
• Operadores que aparecem em regras mais
distantes do axioma S têm maior precedência
do que os que aparecem mais próximo.
^ precede * e /, que precedem + e –
* e / têm igual precedência
+ e – têm igual precedência
Linguagens Formais
Precedência Operadores
• Operadores que estão a uma mesma distância
do axioma (portanto de igual precedência) têm
prioridade definida pela recursividade do nãoterminal do lado esquerdo da regra: se à
esquerda, primeiro o da esquerda; se à direita,
primeiro o da direita.
i + i – i ≈ ((i + i) – i)
i + i * i / i ≈ (i + ((i * i) / i))
i ^ i ^ i - i ≈ (((i ^ i) ^ i) – i)
Linguagens Formais
Gramáticas GR
Gramáticas Regulares ou Tipo 3
Aplicando-se mais uma restrição sobre a forma das
produções, pode-se criar uma nova classe de
gramáticas, as Gramáticas Regulares (GR), de grande
importância no estudo dos compiladores por possuírem
propriedades
adequadas
para
a
obtenção
de
reconhecedores simples. Nas GRs, as produções são
restritas às formas seguintes:
A  aB
A  a
A  l
onde A,B  Vn e a  Vt
Linguagens Formais
Gramáticas GR
Definição3: As linguagens geradas pelas
Gramáticas Regulares ou do Tipo 3 são chamadas
de Linguagens Regulares (LR) ou Linguagens do
Tipo 3.
Resultado 3:
Toda gramática do tipo 3 é também do tipo 2.
Corolário 3:
Toda LR é também uma LLC (mas nem toda LLC é
LR).
Linguagens Formais
Gramáticas GR
Exemplo 1:
G = ({S}, {a, b}, P, S)
P =
S  aS
S b
Linguagens Formais
Gramáticas GR
Exemplo 1:
G = ({S}, {a, b}, P, S)
P =
S  aS
S b
Resp.: L(G) = {anb; n ≥0} ou a*b
Linguagens Formais
Gramáticas GR
Exemplo 2:
G = ({S, A}, {a, b, c}, P, S)
P =
S  aS | bA
A  c
Linguagens Formais
Gramáticas GR
Exemplo 2:
G = ({S, A}, {a, b, c}, P, S)
P =
S  aS | bA
A  c
Resp.: L(G) = {anbc | n ≥ 0}
Linguagens Formais
Gramáticas GR
Exemplo 3:
G = ( {<Dig>, <Int>}, {+, -, 0, ..., 9}, P, <Int>)
P = <Int> ::= +<Dig> | -<Dig>
<Dig> ::= 0<Dig> | 1<Dig>|...| 9<Dig> | 0 | 1 | 2
|...|9
Linguagens Formais
Gramáticas GR
Exemplo 3:
G = ( {<Dig>, <Int>}, {+, -, 0, ..., 9}, P, <Int>)
P = <Int> ::= +<Dig> | -<Dig>
<Dig> ::= 0<Dig> | 1<Dig>|...| 9<Dig> | 0 | 1 | 2
|...|9
Resp.:
L(G) = conj. números inteiros com sinal ±[0..9]+
Exercício: Modifique a gramática acima para que ela
também gere os números inteiros com sinal positivo
optativo. Qual o tipo da gramática resultante?
Linguagens Formais
Expressões Regulares
As Linguagens Regulares se caracterizam por serem
expressas por Expressões Regulares
Def. (Expressão Regular)
a) qualquer símbolo, inclusive l é uma Expressão
Regular (ER).
b) se x é ER, x* é ER (fechamento recursivo e
transitivo);
x+ é
ER
(fechamento
transitivo);
(x) é ER.
c) se x e y são ER, xy é ER (concatenação) e x|y é
ER (união de conjuntos).
Linguagens Formais
Expressões Regulares
Exemplo:
(ab)* = {l, ab, abab, ...abab...ab}
(a|b)* = {l, a...a, b...b, aba...ba, ...ba...bb...}
(ab|cd)f = {abf, cdf}
Linguagens Formais
Expressões Regulares
Notações Adicionais
+ "uma ou mais instâncias de"
r * = r+ | l
r+ = rr*
? "zero ou uma instância de"
r? = r | l
Linguagens Formais
Expressões Regulares
Exemplo:
numero  digitos fracao_opcional expon_opcional
digito  0 | 1 | .. |9
digitos  digito+
fracao_opcional  (.digitos)?
expon_opcional  (E (+ | -)? digitos)?
Exemplos de sentenças da linguagem gerada:
3
145.34E-2
10E2
Linguagens Formais
Expressões Regulares
Exercício: Reescreva a gramática anterior, eliminando
a meta-linguagem introduzida. Qual é o tipo da
gramática resultante?
Dica para descobrir se uma linguagem é regular: se
for possível descrevê-la como uma expressão regular,
então ela é regular. Ou, é claro, exibir uma GR que a
gere.
Quando se classifica uma linguagem, deseja-se saber
qual é a menor classe a que ela pertence. Ou seja,
uma LR é também LLC, LSC e LEF. No entanto, é
mais útil saber que ela é LR, pois isso indica que um
reconhecedor dessa linguagem pode ser o mais simples
possível.
Linguagens Formais
LR
Propriedades de Linguagens Regulares
O conjunto das LRs é fechado sob as operações de:
a) Concatenação: a concatenação de LRs resulta em
LR.
b) União: a união de LRs resulta em LR.
c) Clausura: o fechamento (*) de LR resulta em LR.
d) Intersecção: a intersecção de LRs resulta em LR.
e) Complemento: o complemento (S* - L) de LR resulta
em LR.
Vamos mostrar apenas os 3 primeiros casos.
Linguagens Formais
LR
Concatenação de Linguagens Regulares
Dadas duas Gramáticas Regulares G1 e G2, pode-se
construir uma Gramática Regular G3, tal que:
L(G3) = L(G1) . L(G2)
L1 . L2 = { xy | x  L1, y  L2}
Linguagens Formais
LR
Processo: Se S1 e S2 são os axiomas de G1 e G2,
simplesmente substituímos todas as produções A  a
(*) em G1 por A  aS2, e, então, colocamos todas as
produções juntas, formando G3. O símbolo inicial é
S1.
(*) se a = l então A  S2, deixando de ser uma
produção regular. Porém, como G2 é regular, basta
substituir A  S2, por A  ; para todo  tal que S2
 .
Linguagens Formais
LR
G1:
S1  0A
S1  1B
S1  l
A 1
B 2
Linguagens Formais
LR
G1:
S1  0A
S1  1B
S1  l
A 1
B 2
Resp.: L(G1) = {01, 12, l}
Linguagens Formais
LR
G2:
S2  0
S2  1C
S2  0S2
C 0
Linguagens Formais
LR
G2:
S2  0
S2  1C
S2  0S2
C 0
Resp.:
L(G2) = {0, 10, 00, 010, 00...0, 00...010} = 0*(10 | 0)
Linguagens Formais
LR
G3:
S1  0A S1  1B S1  0 S1  1C
S1  0S2
A  1S2
B  2S2
S2  0 S2  1C S2  0S2
C  0
Linguagens Formais
LR
G3:
S1  0A S1  1B S1  0 S1  1C
S1  0S2
A  1S2
B  2S2
S2  0 S2  1C S2  0S2
C  0
Resp.:
L(G3) = { 010, 0110, 0100, ..., 120, 1210, 1200, ...}
Linguagens Formais
LR
União de Linguagens Regulares
Podemos também construir G3 tal que
L(G3) = L(G1)  L(G2)
Processo: Para cada produção S1   ou S2  ,
adicionamos a produção S   ou S  . Colocamos
todas as produções juntas e o símbolo inicial de G3
será S.
Linguagens Formais
LR
Exemplo:
Sejam G1 e G2 vistas na seção anterior (concatenação)
\ G3 = S  0A S  1B S  l
A  1
B  2
S  0 S  1C S  0S2
S2  0 S2  1C S2  0S2
C  0
Obs.: S1  0A
S1  1B
S1  l
desnecessário pois
S1 não aparece do
lado direito das
regras
Linguagens Formais
LR
Exemplo:
Sejam G1 e G2 vistas na seção anterior (concatenação)
\ G3 = S  0A S  1B S  l
A  1
B  2
S  0 S  1C S  0S2
S2  0 S2  1C S2  0S2
C  0
Resp.:
L(G3) = {01, 12, 1, 0, 10, 00, 010, 0...0, 0...10} =
L(G1)  L(G2)
Linguagens Formais
LR
Conjunto Clausura
Dada uma Gramática Regular G1, podemos construir
uma Gramática Regular G2 tal que
L(G2) = L(G1)*
Processo: Substituímos A  a em G1 por A  aS1.
Adicionamos S1  l. O axioma é S1.
Linguagens Formais
LR
Exemplo 1:
G1 = S1  aS1
S1  bA
A  c
Linguagens Formais
LR
Exemplo:
G1:
S1  aS1
S1  bA
A  c
Resp.: L(G1) = {anbc | n ≥ 0} ou a*bc
Linguagens Formais
LR
G2:
S1  aS1
S1  bA | S1  l
A  cS1
Linguagens Formais
LR
G2:
S1  aS1
S1  bA | S1  l
A  cS1
Resp.:
L(G2) = {l, bc, abc, aa...bc, bcbc, abcabc, ...} =
(a*bc)* = L(G1)*
Linguagens Formais
LR
Resultado das Propriedades das Gramáticas Regulares
As Linguagens Regulares são fechadas sob todas as
operações
de
união,
concatenação,
clausura,
intersecção e complemento (S* - L).
Isto significa que qualquer Linguagem Regular não
vazia pode ser construída a partir de um número finito
de cadeias simples e um número finito de operações de
união,
concatenação,
clausura,
intersecção
e
complemento.
Linguagens Formais
Intersecção de Linguagens Regulares
Resultado:
Uma vez que as linguagens regulares são
fechadas sob as operações de complemento
e união, elas também são fechadas sob a
operação de intersecção.
Linguagens Formais
Intersecção de Linguagens Regulares
Resultado:
Uma vez que as linguagens regulares são
fechadas sob as operações de complemento e
união, elas também são fechadas sob a
operação de intersecção.
Prova: L1  L2 = ( L1'  L2')'
Linguagens Formais
Propriedades de Linguagens Livres de Contexto
O conjunto das LLCs é fechado sob as operações
de:
a)
b)
União: a união de LLCs resulta em LLC.
Clausura: o fechamento (*) de LLC resulta em
LLC.
c) Concatenação: a concatenação de LLCs resulta
em LLC.
Vamos mostrar :
Linguagens Formais
União de Linguagens Livres de Contexto
Dadas duas GLCs G1 e G2, pode-se construir uma
GLC G3, tal que:
L(G3) = L(G1) U L(G2)
Demonstração:
Se
G1 = {Vn1, Vt1, P1, S1} e G2 = {Vn2, Vt2, P2, S2}
Então definimos
G3 = {{Vn1 U Vn2}, {Vt1 U Vt2}, {P1 U P2 U {S3 =>
S1|S2}}, S3}
Linguagens Formais
Clausura de Linguagens Livres de Contexto
Dada uma GLC G1,pode-se construir uma GLC G2, tal
que:
L(G2) = L(G1)*
Demonstração:
Se
G1 = {Vn1, Vt1, P1, S1}
Então definimos
G2 = {Vn1, Vt1, {P1 U {S2 => S1 S2| l }}, S2}
Linguagens Formais
Concatenação de Linguagens Livres de Contexto
Dadas duas GLCs G1 e G2,pode-se construir uma GLC
G3, tal que:
L(G3) = L(G1).L(G2) = {xy | xL(G1), yL(G2)}
Demonstração:
Se
G1 = {Vn1, Vt1, P1, S1} e G2 = {Vn2, Vt2, P2, S2}
Então definimos
G3 = {{Vn1 U Vn2}, {Vt1 U Vt2}, {P1 U P2 U {S3 =>
l, para toda produção S1 => l de P1}}, S3}
Linguagens Formais
Conclusões
Hierarquia de Chomsky
Em termos gerais, para n
afirmar que uma linguagem
classificada também como
acordo com a Hierarquia de
 {0, 1, 2, 3} pode-se
de qualquer tipo pode ser
sendo de tipo menor, de
Chomsky.
Uma linguagem do tipo n é caracterizada pela
existência de alguma gramática do tipo n que a
descreva.
Linguagens Formais
Linguagens
Hierarquia de Chomsky
LR
LLC
LSC
LEF
LR = Linguagens
Regulares
LLC = Linguagens
Livres de Contexto
LSL =Linguagens
Sensíveis ao Contexto
LEF = Linguagens com
Estrutura de Frase
Linguagens Formais
Definições Prévias 
Gramáticas 
Linguagens 
