Universidade Estadual Vale do Acaraú - UVA

Curso: Ciências da Computação

Disciplina: Linguagens Formais e Autômatos
Professor: Cláudio Carvalho

Gramáticas Livres de Contexto - GLCs

1 Introdução

No estudo das linguagens naturais, gramáticas são conjuntos de regras que

indicam como sentenças são construídas. Nos exemplos a seguir, considere os termos

entre < e > como variáveis, e os demais como símbolos terminais.

<Sentenca> → <Sujeito> <Predicado> | <Sentenca>, e <Sentenca>

<Sujeito> → <Artigo> <Substantivo> | <Substantivo>
<Predicado> → <Verbo> | <Verbo> <Adverbio>
<Artigo> → O | A
<Substantivo> → Maria | João | menina | menino
<Verbo> → estuda | dorme | come
<Adverbio> → muito | pouco | cedo | tarde

Na gramática acima, temos uma representação simples de como formar uma

sentença em português. Algumas frases que podem ser derivadas são:

-  O menino come pouco .

-  João dorme cedo, e Maria estuda muito .

Assim como nas linguagens naturais, as gramáticas também têm muita apli-

cação nas linguagens de programação. Tomemos como exemplo a gramática a seguir, que

poderia ser utilizada para analisar a sintaxe de comandos For em Pascal. Ela deriva, por

exemplo: For I := J + 1 To J + 10 Do.

<Cmd> → For <Id> := <Exp> To <Exp> Do
<Id> → I | J
<Exp> → <Exp><Op><Exp> | (<Exp>) | <Id> | <Vlr>
<Op> → + | -
<Vlr> → <Dgt> | 1<Num> | . . . | 9<Num>
<Dgt> → 0 | ... | 9
<Num> → <Dgt> | <Dgt><Dgt>

Nas linguagens naturais, as gramáticas tratam tanto das regras de sintaxe

como das regras de semântica. As Gramáticas Livres de Contexto (GLC) tratam das

regras de sintaxe. São, portanto, usadas para análise sintática (ou parsing ). Raramente,

por não ser o seu propósito, este tipo de gramática lida com semântica.

1
2 Denição

GLC's são representadas por quádruplas G = (V, T, P, S), onde:

ˆ V: Conjunto nito e não vazio de símbolos variáveis;

ˆ T: Conjunto nito de símbolos terminais;

ˆ P: Conjunto nito de regras de produção;

ˆ S: Símbolo inicial da gramática (S ∈ V ).

A diferença deste tipo de gramática em relação às Gramáticas Regulares, vistas

anteriormente, está nas suas regras de produção. Nas GLC's, P : V → (V ∪ T )∗ . Com

isso, diz-se que essas compõem a classe mais geral de gramáticas cujo lado esquerdo das

regras de produção é apenas uma variável. O lado direito pode ser qualquer combinação

de símbolos variáveis e terminais.

Todas as observações feitas para Gramáticas Regulares, no que diz respeito

à simplicação na representação das regras de produção e à linguagem gerada, também

valem para as Gramáticas Livres de Contexto. A propósito, a linguagem gerada por esse

tipo de gramática é uma Linguagem Livre de Contexto (LLC).

Geralmente podemos especicar uma gramática apenas pelas suas regras de

produção. As variáveis são identicadas pelos símbolos que aparecem do lado esquerdo

das regras, e os demais símbolos são terminais ou ε. Convencionamos que a variável que

aparece do lado esquerdo da primeira regra de produção seja o símbolo inicial.

Ao nal do estudo das Linguagens Regulares, foi visto, pelo Lema do Bombea-

mento, que a linguagem L = an b n , n ∈ N não é regular. Como também foi visto no estudo

das gramáticas regulares, essa linguagem pode ser gerada por uma gramática linear que

não é regular. Essa é, portanto, uma Linguagem Linear - classe de linguagens que ca

entre as linguagens regulares e as livres de contexto. A seguir, temos gramáticas lineares

(e livres de contexto) G01 e G02 para a referida linguagem:

G01 = ({A, B}, {a, b}, P01 , A)

P01 = {A → aB | ε,
B → Ab}

G02 = ({S}, {a, b}, P02 , S)

P02 = {S → aSb | ε}

No nosso Curso, não será feito um estudo direcionado para as linguagens li-

neares. Essas serão vistas dentro das linguagens livres de contexto. Gramáticas Lineares
podem ser vistas como Gramáticas Livres de Contexto em que o lado direito de toda regra

de produção possui no máximo um símbolo variável.

2
3 Derivação e Parsing

Como foi visto nas gramáticas regulares, a derivação demonstra as aplicações

das regras de produção, uma a uma, para gerar uma cadeia a partir do símbolo inicial.

Denimos então dois tipos de derivação: devivação mais à direita, em que a substituição
será feita sempre na variável mais à direita, e a derivação mais à esquerda, em que a

substituição será feita sempre na variável que estiver mais à esquerda da cadeia.

Vale ressaltar que o processo de derivação não segue, necessariamente, uma

das formas anteriores. Qualquer variável pode ser substituída. Por exemplo, dada a

gramática G03 a seguir, temos algumas das possíveis derivações para a palavra a + a × a.
Em (a) temos uma derivação mais à esquerda; em (b) uma derivação mais à direita; e em

(c) uma derivação mista.

G03 = ({E}, {(, ), +, −, ×, /, a}, P03 , E)

P03 = {E → E + E | E − E | E × E | E/E | (E) | a}

(a) E ⇒ E + E ⇒ a + E ⇒ a + E × E ⇒ a + a × E ⇒ a + a × a.
(b) E ⇒ E + E ⇒ E + E × E ⇒ E + E × a ⇒ E + a × a ⇒ a + a × a.
(c) E ⇒ E × E ⇒ E + E × E ⇒ E + E × a ⇒ a + E × a ⇒ a + a × a.

Dada uma gramática G = (V, T, P, S) e uma palavra w, tal que S ⇒∗ w. A

árvore de derivação é uma estrutura utilizada para representar a derivação de w por G,

sem levar em consideração a ordem em que as regras de produção foram aplicadas, e é

construída da seguinte forma:

ˆ S deve ser a raiz;

ˆ Se uma regra de produção A → α1 . . . αk for aplicada (αi ∈ V ∪ T e 1 ≤ i ≤ k ),

então α1 , . . . , αk devem ser lhos de A, nessa ordem.

A árvore estará concluída quando todas as suas folhas forem elementos de

T ∪ {ε}. Tomemos como exemplo a derivação da cadeia (a + a) pela gramática G03 :

E ⇒ (E) ⇒ (E + E) ⇒ (a + E) ⇒ (a + a), ilustrada na Figura 1.

( E )

E + E

a a

Figura 1  Árvore de derivação para (a + a) em G03

3
4 Ambiguidade

Uma gramática pode gerar uma mesma cadeia de diferentes modos. Esta terá

diferentes árvores de derivação e, consequentemente, diferentes signicados. Isto pode

ser indesejado para algumas aplicações, tais como linguagens de programação, onde um

programa deve ter interpretação única.

Uma gramática é ambígua se, para alguma palavra, ela possui mais de uma

derivação mais à esquerda, ou mais à direita, e, portanto, possui mais de uma árvore de

derivação distinta. Por exemplo, a gramática G03 é ambígua, pois possui duas derivações

mais à esquerda para a + a × a.

(a) E ⇒ E + E ⇒ a + E ⇒ a + E × E ⇒ a + a × E ⇒ a + a × a.
(b) E ⇒ E × E ⇒ E + E × E ⇒ a + E × E ⇒ a + a × E ⇒ a + a × a.

A Figura 2 traz as duas árvores das derivações acima. Note que G03 não
2
obedece a ordem de precedência dos operadores. A expressão em (a) equivale a a+a ;

enquanto a expressão em (b) a 2a2 .

E E

E + E E × E

a E × E E + E a

a a a a

(a) (b)

Figura 2  Árvores de derivação para a+a×a em G03

A ambiguidade vem de substituições paralelas de variáveis. Por exemplo, em

G03 , E pode derivar E+E ou E × E, e ambas podem derivar E + E × E. Para evitar

isso, devem ser usadas variáveis diferentes para operações de prioridades diferentes. As

regras de prioridade para os operadores aritméticos podem ser reforçadas pela gramática

G04 a seguir.

G04 = ({E, F }, {(, ), +, −, ×, /, a}, P04 , E)

P04 = {E → E + E | E − E | F,
F → F × F | F/F | (E) | a}
Nem sempre é possível remover a ambiguidade de uma GLC. Algumas lin-

guagens livres de contexto são geradas necessariamente por gramáticas ambíguas. São

chamadas de linguagens inerentemente ambíguas. Por exemplo, L = {am bn cp | m, n, p ∈

N, com m = n ou n = p} é uma linguagem inerentemente ambígua.

4
5 Fecho das Linguagens Livres de Contexto

O conjunto das linguagens livres de contexto é fechado sobre as operações de

união, concatenação e concatenação sucessiva (ou Fecho de Kleene ).

Teorema 1. Para quaisquer LLC's L1 e L2 , L1 ∪ L2 é também uma LLC.

Demonstração. Como L1 e L2 são LLC's, elas podem ser geradas por GLC's. Sejam
G1 = (V1 , T1 , P1 , S1 ) e G2 = (V2 , T2 , P2 , S2 ) GLCs tais que L(G1 ) = L1 e L(G2 ) = L2 , com
V1 ∩ V2 = ∅ e S ∈ / V1 ∪ V2 . Construímos uma GLC G = (V1 ∪ V2 ∪ {S}, T1 ∪ T2 , P, S), com
P = P1 ∪ P2 ∪ {S → S1 | S2 }. Assim, L(G) = L(G1 ) ∪ L(G2 ) = L1 ∪ L2 .

Teorema 2. Para quaisquer LLC's L1 e L2 , L1 L2 é também uma LLC.

Demonstração. Como L1 e L2 são LLC's, elas podem ser geradas por GLC's. Sejam
G1 = (V1 , T1 , P1 , S1 ) e G2 = (V2 , T2 , P2 , S2 ) GLCs tais que L(G1 ) = L1 e L(G2 ) = L2 , com
V1 ∩ V2 = ∅ e S ∈ / V1 ∪ V2 . Construímos uma GLC G = (V1 ∪ V2 ∪ {S}, T1 ∪ T2 , P, S), com
P = P1 ∪ P2 ∪ {S → S1 S2 }. Assim, L(G) = L(G1 )L(G2 ) = L1 L2 .

Teorema 3. Para qualquer LLC L1 , L∗1 é também uma LLC.

Demonstração. L1 é uma LLC, ela pode ser gerada por uma GLC G1 = (V1 , T1 , P1 , S1 )
Como

tal que L(G1 ) = L1 . Construímos uma GLC G = (V1 , T1 , P, S1 ), com P = P1 ∪ {S1 →

S1 S1 | ε}. Assim, L(G) = L(G1 )∗ = L∗1 .

Para vericarmos uma aplicação desses resultados, considere as GLC's G05 e

G06 a seguir, com L(G05 ) = L05 = {a} e

n n
L(G06 ) = L06 = {b c | n ∈ N} .

G05 = ({X}, {a}, P05 , X)

P05 = {X → a}

G06 = ({Y }, {b, c}, P06 , Y )

P06 = {Y → bY c | ε}
Pelo Teorema 3, é possível construir uma GLC G07 cuja linguagem gerada seja
m
L07 = {a | m ∈ N} = (L05 ) ∗
.

G07 = ({X}, {a}, P07 , X)

P07 = {X → a | XX | ε}
Pelo Teorema 2, é possível construir uma GLC G08 cuja linguagem gerada seja
m n n
L08 = {a b c | m, n ∈ N} = L07 L06 .
G08 = ({S, X, Y }, {a, b, c}, P08 , S)
P08 = {S → XY,
X → a | XX | ε,
Y → bY c | ε}

5
 É um exercício fácil vericar que a linguagem N
L09 = {an bn cm | m, n ∈ }
também é livre de contexto. Pelo Teorema 1, podemos ver que a linguagem L10 =

{ai bj ck | i, j, k ∈ N, com i = j ou j = k} = L08 ∪ L09 também é livre de contexto.

Para apresentarmos os próximos resultados, tomemos como base a linguagem

n n n
L= {a b c | n ∈ N} , que não é livre de contexto (isso pode ser visto com o Lema do
Bombeamento para Linguagens Livres de Contexto ).

Teorema 4. O conjunto das LLC's não é fechado sobre a operação de intersecção.

Demonstração. Por contradição, assuma que o conjunto das LLCs é fechado para a ope-

ração de intersecção. Logo, para quaisquer LLC's L1 e L2 , temos que L1 ∩ L2 é também

uma LLC. Façamos L1 = {an bn cm | m, n ∈ N N
} e L2 = {am bn cn | m, n ∈ }. Assim,
N
L1 ∩ L2 = {an bn cn | n ∈ } é uma LLC. Isso é uma contradição.

Teorema 5. O conjunto das LLC's não é fechado sobre a operação de complemento.

Demonstração. Por contradição, assuma que o conjunto das LLCs é fechado para a ope-

ração de complemento. Logo, para quaisquer LLC L1 e L2 , L01 e L02 são também LLC's.
n n m
Façamos L1 = {a b c | m, n ∈ N N
} e L2 = {am bn cn | m, n ∈ }. Pelo Teorema 1, L01 ∪ L02
é uma LLC. Pela hipótese, (L1 ∪ L2 ) também é uma LLC. Observe que, por De Morgan,
0 0 0

N
(L01 ∪ L02 )0 = L1 ∩ L2 . Logo, L1 ∩ L2 = {an bn cn | n ∈ } é uma LLC, uma contradição.

6 Construção de Gramáticas Livres de Contexto

Como bem enfatizado por Sipser (2012), o projeto de gramáticas livres de

contexto, assim como o de autômatos nitos, requer criatividade. Na verdade, gramáticas

livres de contexto são ainda mais complicadas de construir do que os autômatos nitos,

pois estamos mais acostumados a programar uma máquina para tarefas especícas do que

descrever linguagens com gramáticas.

Muitas linguagens livres de contexto podem ser vistas como uma combinação

(união, concatenação ou concatenação sucessiva) de outras linguagens livres de contexto

mais simples. Portanto, os resultados apresentados nos Teoremas 1, 2 e 3, na seção 5

podem ser úteis para sistematizar a construção de gramáticas para essas linguagens.

Outro ponto importante a ser vericado é se a linguagem para a qual se deseja

projetar uma gramática é regular. Caso seja, é mais simples construir um autômato nito

para tal linguagem e, posteriormente, aplicar o algoritmo visto no estudo das gramáticas

regulares para obtenção de uma GLUD a partir de um AFN-ε. Toda gramática regular é

também livre de contexto.

6
7 Formas Normais

Quando se trabalha com gramáticas livres de contexto, é conveniente tê-las

em uma forma mais simplicada. As formas normais impõem restrições na denição das

regras de produção, sem reduzir o poder de geração das gramáticas. A seguir, serão

apresentadas as formas normais de Chomsky e de Greibach.

7.1 Forma Normal de Chomsky

Uma GLC G = (V, T, P, S) está na Forma Normal de Chomsky (FNC) se

todas as suas regras de produção, com exceção da regra S → ε (caso ε ∈ L(G)), estão

nas formas: A → BC ou A → a, onde a ∈ T, e A, B, C ∈ V , com B, C ∈ V \{S}.

O Teorema 6 a seguir e sua prova foram retirados de Sipser (2012, p.109-110).

Teorema 6. Qualquer linguagem livre de contexto é gerada por uma gramática livre de
contexto na Forma Normal de Chomsky.

A ideia é mostrar que é possível converter qualquer GLC para a FNC. A

conversão consiste em substituir as regras que violam as restrições por equivalentes que

sejam satisfatórias. Primeiro, adiciona-se um novo inicial. Em seguida, eliminam-se todas

as produções vazias (A → ε). Também são eliminadas as produções unitárias (A → B ).

Em ambos os casos, fazemos os ajustes na GLC para que a linguagem gerada seja mantida.

Por m, todas as regras remanescentes são convertidas para a forma correta.

Demonstração. Sejam L uma LLC qualquer, e G = (V, T, P, S) uma GLC que a gera.
0
Primeiro, obtemos uma GLC G = (V ∪ {S0 }, T, P ∪ {S0 → S}, S0 ). Essa modicação

garante que a variável inicial não aparece do lado direito de nenhuma regra de produção.

Segundo, cuidaremos das regras do tipo A → ε, para todo A 6= S0 . Assim,

para cada ocorrência de A no lado direito de uma regra de produção, será adicionada

uma nova regra sem esta. Em outras palavras, seR → uAv ∈ P e u, v ∈ (V ∪ T )∗ ,

adicionamos R → uv a P . Fazemos isso para cada ocorrência de A, uma de cada vez.

Então, se R → uAvAw ∈ P , devemos adicionar regras R → uvAw , R → uAvw e

R → uvw a P . Se R → A ∈ P , e R 6= A, adicionamos R → ε a P , a menos que

esta regra já tenha sido removida. Estes passos devem ser repetidos até que todas as

produções do tipo A → ε, para A 6= S0 , tenham sido removidas.

Terceiro, trataremos das regras unitárias. Ao removermos uma regra do tipo

A → B; para toda regra B→u em P, com u ∈ (V ∪ T )∗ , adicionamos a regra A → u, a

menos que esta seja uma regra unitária que já tenha sido removida. Este passo deve ser

repetido até que todas as regras unitárias tenham sido removidas.

7
 Por m, convertemos as demais regras para a forma correta. Substituímos

cada regra do tipo A → u1 u2 . . . uk , onde k ≥ 3 e ui ∈ V ∪ T , por A → u1 A1 , A1 → u2 A2 ,

A2 → u3 A3 , . . ., Ak−2 → uk−1 uk , e acrescentamos cada Ai a V . Substituímos cada
terminal ui nas regras anteriores por Ui , adicionamos Ui a V , e Ui → ui a P .

Como exemplo, vamos converter a GLC a seguir para a FNC. As regras subli-

nhadas são as que foram adicionadas, e as riscadas as que foram removidas.

1. Dada a gramática original, adicionar o novo símbolo inicial e a regra S0 → S :

a) Gramática original. b) Adição do novo estado inicial S0 .

S → ASA | aB, S0 → S
A → B | S, S → ASA | aB
B → b|ε A → B|S
B → b|ε

2. Remover regras de produção em que uma variável, que não é a inicial, gera ε.

a) Remoção de B → ε. b) Remoção de A → ε.
S0 → S S0 → S
S → ASA | aB | a S → ASA | aB | a | SA | AS | S
A → B|S|ε A → B | S | ///
ε
B → b | ///
ε B → b

3. Remover regras de produção unitárias.

a) Remoção de S → S . c) Remoção de A → B .
S0 → S S0 → ASA | aB | a | SA | AS
S → ASA | aB | a | SA | AS | ////
S S → ASA | aB | a | SA | AS
A → B|S A → ////
B |S|b
B → b B → b
b) Remoção de S0 → S . d) Remoção de A → S .
S0 → /// S | ASA | aB | a | SA | AS S0 → ASA | aB | a | SA | AS
S → ASA | aB | a | SA | AS S → ASA | aB | a | SA | AS
A → B|S A → ///
S | b | ASA | aB | a | SA | AS
B → b B → b

4. Por m, fazemos a correção nas demais regras restantes.

S0 → ASA ////// | aB
/// | AA1 | U1 B | a | SA | AS
S → ASA ////// | aB
/// | AA1 | U1 B | a | SA | AS
A → b | ASA ////// | ////
aB | AA1 | U1 B | a | SA | AS
B → b
A1 → SA
U1 → a

8
7.2 Forma Normal de Greibach

G = (V, T, P, S) está na Forma Normal de Greibach (FNG) se todas

Uma GLC
∗
as suas regras de produção são do tipo A → aα, com A ∈ V , a ∈ T e α ∈ V . Caso

 ∈ L(G), podemos acrescentar a regra S → ε.

O Teorema 7 a seguir e sua prova foram obtidos das transformações apresen-

tadas por Menezes (2012, p.100-101).

Teorema 7. Qualquer linguagem livre de contexto é gerada por uma gramática livre de
contexto na Forma Normal de Greibach.

Assim como na subseção 7.1, a ideia é mostrar que é possível converter qualquer

GLC para a FNG. A conversão consiste em substituir as regras que violam as restrições

por equivalentes que sejam satisfatórias. Primeiro, assim como no Teorema 6, fazemos a

simplicação da gramática, eliminando as produções dos tipos A→ε e A→B e fazendo

os ajustes de forma que a linguagem gerada seja mantida. E por m, convertemos todas

as demais regras para a forma correta.

Demonstração. Sejam L uma LLC qualquer, e G = (V, T, P, S) uma GLC que a gera.

Vamos mostrar que podemos modicar G de forma que ela que na FNG.

Primeiro, fazemos a eliminação das produções vazias e unitárias. Isso corres-

ponde à segunda e à terceira etapas mostradas no Teorema 6.

Segundo, renomeamos as variáveis em uma ordem crescente qualquer (por

exemplo, A1 , . . . , An , onde n = |V |). Diferentes critérios de renomeação podem levar a

diferentes GLC's na FNG, mas todas são equivalentes.

Terceiro, transformamos as produções para a forma Ar → As α, com r ≤ s.

Todas as regras do tipo Ar → As α, tais que r > s e As → β1 | . . . | βm , devem ser
substituídas por Ar → β1 α | . . . | βm α, e assim sucessivamente. Uma vez que o conjunto

de variáveis é nito, existe um limite para as transformações, que pode ser a geração de um

terminal no início do lado direito (Ar → aα) ou de uma recursão à esquerda (Ar → Ar α).
Quarto, devemos excluir as recursões à esquerda. Estas podem existir origi-

nalmente na GLC, ou podem ter sido geradas na etapa anterior. Para cada produção do

tipo Ar → Ar α que for excluída, devemos adicionar recursões à direita (Br → α | αBr )
a P, e a variável Br a V . Caso tenha sido excluída alguma regra de produção no passo

anterior; para cada Ar → φ, acrescentamos Ar → φBr .

Depois, precisamos garantir que o início do lado direito das produções seja

um terminal. Ao chegar neste ponto, para todas as produções da forma Ar → As α ,

temos que r < s. Consequentemente, as produções da variável An devem iniciar por um

9
terminal. Assim, se em An−1 → An α a variável An for substituída por suas produções
correspondentes (ex.: An → aβ ), o lado direito das produções de An−1 também será

iniciado por um terminal (ex.: An−1 → aβα). Estes passos devem ser repetidos para as

variáveis An−2 , . . . , A1 , o que resultará em produções exclusivamente da forma Ar → aα.

Agora devemos fazer o mesmo com as regras das variáveis Br , adicionadas na etapa

anterior, que não tenham o seu lado direito iniciado por terminal. Assim, toda regra do

tipoBr → As α, onde As → β1 | . . . | βk , deverá ser substituída por Br → β1 α | . . . | βk α.

Neste ponto, toda cadeia βi se inicia por um símbolo terminal.

Por m, precisamos garantir que em todas as regras de produção, agora na

forma A → aα, α ∈ V ∗ . Em toda regra de produção que tenha, no seu lado direito, um
símbolo ai ∈ T , a partir da segunda posição, criamos uma variável Ci , substituímos ai

por Ci e adicionamos a regra Ci → ai . Se já tiver sido criada uma variável Ci e uma regra

Ci → ai , nesta etapa, para algum ai , basta substituir ai por Ci . Por exemplo, a regra
A → abA1 bcA2 A5 será substituída por aC1 A1 C1 C2 A2 A5 , e devem ser adicionadas novas
variáveis C1 e C2 , e novas regras C1 → b e C2 → c. Não é criada uma variável diferente

para cada ocorrência de b, a partir da segunda posição. Isso completa a prova.

Como exemplo, vamos converter a GLC a seguir para a FNG. As regras subli-

nhadas são as que foram adicionadas, e as riscadas as que foram removidas.

S → AA | a
A → SS | b

1. A gramática não possui regras vazias ou unitárias. Portanto, já se encontra simplicada.

2. Renomeação de variáveis em ordem crescente. Façamos S = A1 e A = A2 .
A1 → A2 A2 | a
A2 → A1 A1 | b
3. Garantir que, em toda regra do tipo Ar → As α, r ≤ s.
A1 → A2 A2 | a
A2 → A //////
1 A1 | A2 A2 A1 | aA1 | b
4. Remoção de recursões à esquerda.
A1 → A2 A2 | a
A2 → //////////
A 2 A2 A1 | aA1 | b | aA1 B2 | bB2
B2 → A2 A1 | A2 A1 B2
5. Garantir que toda regra tenha o seu lado direito iniciado por um símbolo terminal.
A1 → A //////
2 A2 | aA1 A2 | bA2 | aA1 B2 A2 | bB2 A2 | a
A2 → aA1 | b | aA1 B2 | bB2
B2 → //////
A 2 A1 | aA1 A1 | bA1 | aA1 B2 A1 | bB2 A1 |
//////////
A 2 A1 B2 | aA1 A1 B2 | bA1 B2 | aA1 B2 A1 B2 | bB2 A1 B2
6. Nenhuma transformação adicional é necessária, pois todas as regras já estão na forma A → aα,
com a ∈ T e α ∈ V ∗ .

10
8 Exercícios

1. Com base na gramática livre de contexto G abaixo, responda:

G = ({A, B, C, D, E}, {a, b, c}, P, A)

P = {A → BC | DE,
B → aBb | ε,
C → cC | ε,
D → aD | ε,
E → bEc | ε}

a) caracterize L(G).
b) proponha uma GLC equivalente a G, sem produções nulas e unitárias.

c) mostre que G é ambígua.

d) modique G para que ela que na Forma Normal de Chomsky.

e) modique G para que ela que na Forma Normal de Greibach.

2. Na gramática a seguir, em que as variáveis estão delimitadas por < e >. Mostre

que a frase  a menina toca o menino com a or  possui mais de uma derivação mais

à esquerda, e apresente duas possíveis interpretações para ela.

<Sentence> → <Noun-Phrase> <Verb-Phrase>

<Noun-Phrase> → <Cmplx-Noun> | <Cmplx-Noun> <Prep-Phrase>
<Verb-Phrase> → <Cmplx-Verb> | <Cmplx-Verb> <Prep-Phrase>
<Prep-Phrase> → <Preposition> <Cmplx-Noun>
<Cmplx-Noun> → <Article> <Noun>
<Cmplx-Verb> → <Verb> | <Verb> <Noun-Phrase>
<Article> → o | a | um | uma
<Noun> → menino | menina | flor
<Verb> → toca | gosta | vê
<Preposition> → com

3. Proponha uma GLC para cada uma das linguagens a seguir:

a) L01 = {w ∈ {a, b}∗ | w = wR }

b) L02 = {w N
= am bn | m, n ∈ e m 6= n}
c) L03 = {w ∈ {a, b}∗ | n(a, w) = n(b, w)}
d) L04 = {w ∈ {a, b}∗ | 2 ≤ n(b, w) ≤ 4}
e) L05 = {w N
= an bbn/2c | n ∈ }
f) L06 = {w N
= an bdn/2e | n ∈ }
g) L07 = {w N
= an b2n−3 | n ≥ 2 e n ∈ }
h) L08 = {w N
= am bm+n cn | m, n ∈ }
i) L09 = {w N
= am bn cp | m, n, p ∈ , m = n ou m = p}
j) L10 = {w N
= am bn cp dq | m, n, p, q ∈ , e m + n = p + q}

11
 Referências

DING-ZHU, D.; KER-I, K. Problem Solving in Automata, Languages, and Complexity.

Newark, NJ: Wiley, 2004.

HOPCROFT, J. E.; ULLMAN, J. D.; MOTWANI, R. Introduction to Automata Theory,

Languages and Computation. 3. ed. Boston, MA, USA: Addison-Wesley Longman
Publishing Co., Inc., 2006.

MENEZES, P. F. B. Linguagens Formais e Autômatos. 6. ed. Porto Alegre: Bookman,

2012. v. 3. (Série livros didáticos informática UFRGS, v. 3).

SIPSER, M. Introduction to the Theory of Computation. 3. ed. Boston: Cengage

Learning, 2012.

12