LFA
- Ambiguidade
- Equivalência de gramáticas
- Hierarquia de Chomsky
Prof. Yandre Maldonado e Gomes da Costa
Hierarquia de Chomsky - Prof. Yandre Maldonado - 1
Ir p/ primeira página
Ambiguidade

Considerando a gramática com as
seguintes regras:
EE+E
EE*E
E  (E)
Ea
Tomando-se a cadeia a+a+a
Hierarquia de Chomsky - Prof. Yandre Maldonado - 2
Ir p/ primeira página
Ambiguidade
E
E
E
+
E +
E
a
a
E
E
a
a
+
E
E +
E
a
a
Duas árvores distintas para a sentença
a+a+a, logo a sentença é ambígua e a
gramática também.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 3
Ir p/ primeira página
Equivalência de
Gramáticas


Duas gramáticas G1 e G2 são
equivalentes se L(G1)=L(G2)
Equivalência não significa
gramáticas iguais
Hierarquia de Chomsky - Prof. Yandre Maldonado - 4
Ir p/ primeira página
Equivalência de
Gramáticas


G1
Exemplo:
Qual a linguagem gerada por cada
uma das seguintes gramáticas:
G2
G3
ET
T  TF
E  aaF
FE
E  ET
E  aa
TF
F  aa
F
T  aa
T
Hierarquia de Chomsky - Prof. Yandre Maldonado - 5
G4
E  aa
E  Eaa
Ir p/ primeira página
Equivalência de
Gramáticas



L(Gx)={a2n|n1}
Portanto as quatro gramáticas são
equivalentes
Observe que G3 é ambígua
(sentença aa)
Hierarquia de Chomsky - Prof. Yandre Maldonado - 6
Ir p/ primeira página
Hierarquia de Chomsky


Esta hierarquia define quatro tipos
de gramáticas
Os tipos são:
 Tipo
0 ou GEF - Gramática com
Estrutura de Frase
 Tipo 1 ou GSC - Gramática
Sensível ao Contexto
 Tipo 2 ou GLC - Gramática Livre
de Contexto
 Tipo 3 ou GR - Gramática Regular
Hierarquia de Chomsky - Prof. Yandre Maldonado - 7
Ir p/ primeira página
Hierarquia de Chomsky
GEF
LSC-GSC
LLC-GLC
LR-GR
Hierarquia de Chomsky - Prof. Yandre Maldonado - 8
Ir p/ primeira página
Hierarquia de Chomsky

GEF ou Tipo 0
 São
as gramáticas onde todas as
regras de produção pertencentes
ao conjunto P são do tipo:
   onde (VNVT)*
(VNVT)+
 As
próximas gramáticas são GEF’s
com restrições.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 9
Ir p/ primeira página
Hierarquia de Chomsky

GSC ou Tipo 1
 São
as gramáticas onde todas as regras
de produção pertencentes ao conjunto P
são do tipo:
   tal que ||  || exceto quando  = 
onde (VNVT)*
(VNVT)+
 As
próximas gramáticas são GSC’s com
restrições.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 10
Ir p/ primeira página
Hierarquia de Chomsky

Tipo 1 - exemplo:
S  aSBC
S  aBC
CB  BC
aB  ab
bB  bb
bC  bc
cC  cc
Hierarquia de Chomsky - Prof. Yandre Maldonado - 11


Qual é a linguagem
gerada por esta
gramática?
L(G) = {anbncn|n1}
Ir p/ primeira página
Hierarquia de Chomsky

GLC ou Tipo 2
 São
as gramáticas onde todas as regras
de produção pertencentes ao conjunto P
são do tipo:
A   onde (VNVT)*
AVN
 A próxima
gramática é GLC com
restrições.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 12
Ir p/ primeira página
Hierarquia de Chomsky

Tipo 2 - exemplo:
S  aB
S  bA
Aa
A  aS
A  bAA
Bb
B  bS
B  aBB
Hierarquia de Chomsky - Prof. Yandre Maldonado - 13


Qual é a linguagem
gerada por esta
gramática?
L(G) = {w{a,b}+| w
contém número de a’s
igual ao número de b’s}
Ir p/ primeira página
Hierarquia de Chomsky

Tipo 2 - exemplo 2:
S  AB
A  0A11
A
B  0B
B


Qual é a linguagem
gerada por esta
gramática?
L(G) = {0n12n0m|n0, m0}
Hierarquia de Chomsky - Prof. Yandre Maldonado - 14
Ir p/ primeira página
Hierarquia de Chomsky
Considere a seguinte linguagem:
L(G) = {ambn|n1, m1}


Descreva uma
GLC capaz de
gerar esta
linguagem.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 15

Tipo 2 - exemplo 3:
S  AB
A  aA
Aa
B  bB
Bb
Ir p/ primeira página
Hierarquia de Chomsky
GR ou Tipo 3
Gramáticas com produções do tipo:
A  aB ou
Ab
onde A, BVN
a VT
b VT  {}

Hierarquia de Chomsky - Prof. Yandre Maldonado - 16
Ir p/ primeira página
Hierarquia de Chomsky

Tipo 3 - exemplo:
S  aS
S  bA
Ac

Qual é a linguagem gerada pela GR?

L(G) = {anbc|n0}
Hierarquia de Chomsky - Prof. Yandre Maldonado - 17
Ir p/ primeira página
Hierarquia de Chomsky

Tipo 3 - exemplo 2:
N  +D|-D
D  0|1|2|3|4|5|6|7|8|9|0D|1D|2D|3D
|4D|5D|6D|7D|8D|9D

Qual é a linguagem gerada pela GR?

Números inteiros com sinal.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 18
Ir p/ primeira página
Hierarquia de Chomsky

Tipo 3 - exemplo 3:
N  +D|-D
D  0|1|2|3|4|5|6|7|8|9|1E|2E|3E|4E
|5E|6E|7E|8E|9E
E  0|1|2|3|4|5|6|7|8|9|0E|1E|2E|3E
|4E|5E|6E|7E|8E|9E

Números inteiros com sinal sem
ocorrência de zeros à esquerda.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 19
Ir p/ primeira página
Hierarquia de Chomsky

Tipo 2 - exemplo 2:
N  SD
S  +|D  ED|E
E  0|1|2|3|4|5|6|7|8|9

Gramática GLC equivalente ao
exemplo 2 do tipo 3.
Hierarquia de Chomsky - Prof. Yandre Maldonado - 20
Ir p/ primeira página