Gramáticas Livres do Contexto
Revisão
Teoria da Computação
Pós-Graduação em Ciência da
Computação
Profa. Sandra de Amo
Gramática
• G = (V,T,P,S)
V = variáveis, S = variável inicial
T = terminais
P = conjunto de regras do tipo
w -> u onde
w = string de variáveis e terminais
u = string de variáveis e terminais
Diferença entre gramáticas e
autômatos
Autômato
Gramática
Gera strings
Mecanismo Enumerador
Reconhece strings
Mecanismo Reconhecedor
Quais são as palavras
A palavra “aba”
pertence a linguagem
L?
da Linguagem L
aaa
abab
abbb
….
SIM
NÃO
Diferença entre gramáticas e
autômatos
Autômato
Gramática
Sim
abab
Não
Aaaabb
Abababa
Sweklk
Slkdjfil
Slkdfjlskd
…..
abab pertence a L ?
Gramática Livre do Contexto
S
S -> AB
S->a
A-> AC
A -> a
B-> AC
C -> c
C-> SB
B
A
A
C
a
c
A
A
C
C
B
S
a
a
c
A
C
z=acaaacc
a
c
Derivação de uma palavra
S -> AB
S->a
A-> AC
A -> a
B-> AC
C -> c
C-> SB
z=acaaacc
S
B
A
A
C
a
c
A
A
C
C
B
S
a
a
c
A
a
C
c
S  AB  ACB  a C B ac B  acAC  ac AC C  acaCC  aca SBC 
acaaBC  acaaACC  acaaaCC  acaaacC  acaaacc
Tamanho da derivação = número de regras aplicadas = 13
Linguagem gerada por uma
Gramática Livre do Contexto
• G = gramática livre do contexto
• L(G) = {w  Σ* | existe uma derivação de
w usando as regras da gramática G}