Universidade Federal do Pará

Instituto de Ciências Exatas e Naturais

Programa de Pós-Graduação em Ciência da Computação
Disciplina: Teoria da Computação
Professor: Jefferson Morais
1. Construa gramática livres de contexto que gerem as seguintes linguagens.
a) L1 = {ai bj c* | i ≠ j}
S → AC | BC | aAbC | aBbC
A → aA | a | aAb
B → Bb | b | aBb
C → cC | ε
b) L2 = {ai bj ck | i = j + k}
S → aSc | B
B → aBb | ε
c) L3 = {ai bj ck | j = i + k}
S → AB
A → aAb | ε
B → bBc | ε

2. Linguagens livre de contexto são geradas por gramáticas dos tipos 2 ou 3. No entanto, existem
algumas linguagens livres de contexto que só podem ser geradas por gramáticas do tipo 2.
a) Qual é o aspecto linguístico que diferencia esta classe de linguagens das demais que
também podem ser geradas por gramáticas do tipo 3?
Citar construções aninhadas; citar a diferença entre os mecanismos reconhecedores;
b) De que forma este aspecto se manifesta nas gramáticas utilizadas para definir tais
linguagens?
Diferenciar as gramáticas do tipo 2 e 3 por meio do formalismo matemático; citar as propriedades das
gramáticas do tipo 2.
3. Considere cada uma das gramáticas abaixo:
◦ ({S, X, a}, {a}, {S → a, S → X, X → a, S → SS}, S)
◦ ({S, a}, {a}, {S → a, S → S, S → SS}, S)
Para cada uma das gramáticas acima, responda:
a) A gramática em questão é ambígua? Justifique sua resposta.
Em relação à ({S, a}, {a}, {S → a, S → X, X → a, S → SS}, S):
Sim, pois para a sentença aa existem, pelo menos, duas derivações mais à esquerda:
 Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Programa de Pós-Graduação em Ciência da Computação
Disciplina: Teoria da Computação
Professor: Jefferson Morais
S => SS => aS => aa
S => SS => aS => aX => aa

Em relação à ({S, a}, {a}, {S → a, S → S, S → SS}, S):

Sim, pois para a sentença aa existem, pelo menos, duas derivações mais à esquerda:
S => SS => aS => aa
S => SS => aS => aS => aa (a deriação “aS => aS” indica que S → S foi aplicada)

b) A linguagem definida pela gramática em questão é inerentemente ambígua? Justifique sua

resposta.
Pode-se dizer que não, para ambas as linguagens definidas pelas gramáticas acima, pois é possível
construir uma gramática não-ambígua que gere as respectivas linguagens. Segue as produções dessa
possível gramática não-ambígua:
P = {S → aS | a}

4. Considere a gramática livre de contexto G apresentada a seguir e construa uma gramática

equivalente, em que tenham sido eliminadas as produções em vazio, produções unitárias, os
símbolos inúteis e inacessíveis.
G = (V, Σ, P, S)
V = {S, A, B, C, D, E, F, a, b, c, d, e, f}
Σ = {a, b, c, d, e, f}
P = {S → aAa | A,
A → ε | B | cCDd,
B → bSbb | b | ε,
C → aaAaa | ε,
D → CDd | dD,
E → Ff,
F → f | eEe}
Eliminando as transições em vazio:
 Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Programa de Pós-Graduação em Ciência da Computação
Disciplina: Teoria da Computação
Professor: Jefferson Morais
E0 = {A, B, C}
E1 = {A, B, C, S}
E2 = {A, B, C, S}
P’ = {
S → aAa | A
A → B | cCDd
B → bSbb | b
C → aaAaa
D → CDd | dD
E → Ff
F → f | eEe
}
Fazendo as substituições de Bi e adicionando S’:
P’ = { S’ → S | ε
S → aAa | A | aa
A → B | cCDd | cDd
B → bSbb | b | bbb
C → aaAaa | aaaa
D → CDd | dD | Dd
E → Ff
F → f | eEe
}
Eliminando as produções unitárias:
Encontrando todos os conjuntos N:
NS’ = {S’, S, A, B}
NS = {S, A, B}
NA = {A, B}
NC = {C}
ND = {D}
NE = {E}
 Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Programa de Pós-Graduação em Ciência da Computação
Disciplina: Teoria da Computação
Professor: Jefferson Morais
NF = {F}
Então, as produções serão:
P’ = { S’ → ε | aAa | aa | cCDd | cDd | bSbb | b | bbb
S → aAa | aa | cCDd | cDd | bSbb | b | bbb
A → cCDd | cDd | bSbb | b | bbb
B → bSbb | b | bbb
C → aaAaa | aaaa
D → CDd | dD | Dd
E → Ff
F → f | eEe
}
Eliminando símbolos inúteis (não-terminais):
Encontrando o conjunto N:
N0 = {}
N1 = {S’, S, A, B, C, F}
N2 = {S’, S, A, B, C, F, E}
N3 = {S’, S, A, B, C, F, E}
Portanto, apenas o símbolo não-terminal D é inútil. Deve-se eliminá-lo juntamente
com as derivações onde ele apareça. As produções serão:
P’ = { S’ → ε | aAa | aa | bSbb | b | bbb
S → aAa | aa | bSbb | b | bbb
A → bSbb | b | bbb
B → bSbb | b | bbb
C → aaAaa | aaaa
E → Ff
F → f | eEe
}
Eliminando símbolos inacessíveis (não-terminais e terminais):
V0 = {S’}
V1 = {S’, ε, a, b, A, S}
 Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Programa de Pós-Graduação em Ciência da Computação
Disciplina: Teoria da Computação
Professor: Jefferson Morais
V2 = {S’, ε, a, b, A, S}
P’ = { S’ → ε | aAa | aa | bSbb | b | bbb
S → aAa | aa | bSbb | b | bbb
A → bSbb | b | bbb
}

5. Responda o que se pede em cada item abaixo.

a) Construa uma GLC na Forma Normal de Chomsky considerando as produções P = {S →
aSb | aSc | d}. Em seguida, considerando a GLCFNC, construa uma gramática na Forma
Normal de Greibach.
Forma Normal de Chomsky
Aplicando o passo (6) do algoritmo:
P={
S → ASB | ASC | d
A→ a
B→b
C→c
}

Aplicando o passo 7 do algoritmo:

P={
S → AD1 | AD2 | d
D1 → SB
D2 → SC
A→ a
B→b
C→c
}
 Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Programa de Pós-Graduação em Ciência da Computação
Disciplina: Teoria da Computação
Professor: Jefferson Morais
b) Construa uma gramática livre de contexto na Forma Normal Greibach para a gramática
com produções P = {S → AA | a, A → SS | b}.
A gramática já está isenta de produções em vazio, unitária, símbolos inúteis e inacessíveis. Deve-se
inicial aplicar o algoritmo de eliminação de recursão à esquerda. Assume-se a substituição de
símbolos não-terminais como: S = X1 e A = X2

Portanto, as produções ficam da forma: A1 → A2A2 | a, A2 → A1A1 | b

A produção A2 → A1A1 não satisfaz o passo (5) e (6) do algoritmo de eliminação de recursão à
esquerda.
Aplicando o passo (5), tem-se:
A2 → A2A2A1 | aA1 | b

Aplicando agora o passo (6), tem-se:

A2 → aA1 | b | aA1A2’ | bA2’
A2’ → A2A1 | A2A1A2’

As produções atuais após a eliminação de recursão à esquerda são da forma:

P={
A1 → A2A2 | a
A2 → aA1 | b | aA1A2’ | bA2’
A2’ → A2A1 | A2A1A2’
}

Agora, aplica-se o algoritmo da FNG considerando a ordenação A2’ < A1 < A2. Primeiramente,
substitui-se A2 em A1:
A1 → aA1A2 | bA2 | aA1A2’A2 | bA2’A2 | a

Agora, substitui-se A2 em A2’:

A2’ → aA1A1 | bA1 | aA1A2’A1 | bA2’A1 | aA1A1A2’ | bA1A2’ | aA1A2’A1A2’ | bA2’A1A2’
 Universidade Federal do Pará
Instituto de Ciências Exatas e Naturais
Programa de Pós-Graduação em Ciência da Computação
Disciplina: Teoria da Computação
Professor: Jefferson Morais

Como não há nenhuma segundo símbolo terminal após o primeiro símbolo terminal do lado direita
das produções, o algoritmo termina. Produções resultantes:
P={
A1 → aA1A2 | bA2 | aA1A2’A2 | bA2’A2 | a
A2 → aA1 | b | aA1A2’ | bA2’
A2’ → aA1A1 | bA1 | aA1A2’A1 | bA2’A1 | aA1A1A2’ | bA1A2’ | aA1A2’A1A2’ | bA2’A1A2’
}