Gramaticas Livres de Contexto

Gram´ticas Livres de Contexto a 25 de novembro de 2011
Defini¸˜o 1 Uma Regra (ou produ¸ao) ´ um elemento do conjunto V × (V ∪ Σ)∗ . ca c˜ e
Sendo que V ´ um conjunto finito de elementos chamados de “vari´veis” e Σ e a um conjunto disjunto chamado de “Al fabeto”. Uma regra [A, w] normalmente
´ escrita como A → w. e Defini¸˜o 2 Uma Gram´tica Livre de Contexto ´ uma qu´drupla (V, Σ, P, S), ca a e a onde V ´ um conjunto finito de vari´veis, Σ (ou o Alfafeto) ´ um conjunto finito e a e de s´ ımbolos terminais, P ´ um conjunto finito de regras, e S ´ um elemento de e e
V chamado de s´ ımbolo inicial. Os conjuntos V e Σ s˜o disjuntos. a ´
Defini¸˜o 3 Uma Arvore de Deriva¸˜o de uma palavra pertencente ` uma ca ca a ling¨agem gerada por uma gram´tica livre de contexto, ´ uma ´rvore constru´ u a e a ıda iterativamente da seguinte forma:
1. Inicialize a ´rvore com a ra´ S. a ız
2. Se A → x1 x2 . . . xn com xi ∈ (V ∪ Σ) ´ a regra de deriva¸ao aplicada ` e c˜ a palavra uAv, ent˜o adicione x1 , x2 , . . . , xn como filhos de A na ´rvore. a a
3. Se A → λ ´ a unica regra de deriva¸ao aplicada ` palavra uAv, ent˜o e ´ c˜ a a adicione λ como o unico filho de A na ´rvore.
´
a
Defini¸˜o 4 Uma Gram´tica Regular ´ uma gram´tica livre de contexto ca a e a na qual toda regra de deriva¸ao tem uma das seguintes formas: c˜ 1. A → a
2. A → aB
3. A → λ

Exerc´ ıcios da Se¸˜o 0 ca Exerc´ ıcio 1 - Seja G a gram´tica a S → abSc | A
A → cAd | cd.
1

a) Dˆ uma deriva¸˜o de ababccddcc. e ca

→

abSc

→

ababScc

→

ababAcc

→

ababcAdcc

→

S

ababccddcc

b) Construa a ´rvore de deriva¸˜o da deriva¸˜o do exerc´ anterior. a ca ca ıcio

c) Use a nota¸˜o de conjuntos para definir L(G). ca L(G) = {(ab)m cn dn cm |m, n ≥ 0}

Exerc´ ıcio 2 - Seja G a gram´tica a →

ASB | λ

A →
B →

aAb | λ bBa | ba

S

a) Dˆ uma deriva¸˜o ` esquerda de aabbba. e ca a

→

ASB

→

aAbSB

→