SolucoesCompleta TC 1

Prévia do material em texto

Apeˆndice A
Soluc¸o˜es de Alguns dos Exerc´ıcios
Propostos
A.1 Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 1
2. Demonstre que para quaisquer cadeias w e u e para todo n ≥ 0 temos que
(2b) |wn| = n|w|,
Resposta: Provaremos por induc¸a˜o em n.
Base da Induc¸a˜o: |w0| = |λ| = 0 = 0|w|.
Hipo´teses indutiva: Suponha que |wk| = k|w|.
Passo indutivo: |wk+1| = |wwk| = |w|+ |wk| = |w|+ k|w| = (k + 1)|w|.
(2d) (wu)R = uRwR.
Resposta: Provaremos por induc¸a˜o em |u|.
Base da Induc¸a˜o: (wλ)R = wR = λRwR.
Hipo´teses indutiva: Suponha que (wu)R = uRwR para todo u tal que |u| = k.
Passo indutivo: Para todo s´ımbolo a do alfabeto de u, (w(ua))R = ((wu)a)R = a(wu)R =
auRwR = (ua)RwR.
5. Mostre que para qualquer n,m ≥ 0 e linguagem L temos que
(5a) (Ln)m = Lnm,
Resposta: Provaremos por induc¸a˜o em m.
Base da Induc¸a˜o: (Ln)0 = {λ} = L0 = Ln0.
Hipo´teses indutiva: Suponha que (Ln)k = Lnk.
Passo indutivo: (Ln)k+1 = (Ln)kLn = LnkLn = Lnk+n = Ln(k+1)
(5c) (LR)n = (Ln)R,
279
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
Resposta: Provaremos por induc¸a˜o em n.
Base da Induc¸a˜o: (LR)0 = {λ} = {λ}R = (L0)R.
Hipo´teses indutiva: Suponha que (LR)k = (Lk)R.
Passo indutivo: (LR)k+1 = (LR)kLR = (Lk)RLR = (LLk)R = (Lk+1)R
(5e) LP = ((L)R)S)R.
Resposta: Se L = ∅ enta˜o trivialmente LP = ((L)R)S)R. Provaremos por induc¸a˜o no
tamanho da cadeia w que w ∈ LP se e somente se w ∈ ((L)R)S)R quando L 6= ∅.
Base da Induc¸a˜o: λ ∈ LP pois λ e´ prefixo de qualquer cadeia. Por outro lado, λ ∈ L)R)S pois
λ e´ sufixo de qualquer cadeia, e portanto, λ ∈ ((L)R)S)R.
Hipo´teses indutiva: Suponha que para todo w tal que |w| = k, w ∈ LP se e somente se
w ∈ ((L)R)S)R.
Passo indutivo: wa ∈ LP se e somente se existe uma cadeia u ∈ Σ∗ tal que wau ∈ L, e isso
so ocorre se e somente existe uma cadeia u ∈ Σ∗ tal que (wau)R = uRawR ∈ LR (veja
exerc´ıcio (2d)), o qual e´ verdade se e somente se awR ∈ (LR)S . Portanto, wa ∈ LP se e
somente se (awR)R ∈ ((LR)S)R, isto e´, se e somente se, wa ∈ ((LR)S)R.
7. Sejam L1 e L2 duas linguagens tais que L1 ⊆ L2. Demonstre que
(7b) LR1 ⊆ LR2 ,
Resposta: Se w ∈ LR1 enta˜o wR ∈ L1. Como por hipo´tese L1 ⊆ L2, enta˜o wR ∈ L2.
Logo, w ∈ LR2 .
(7d) Para toda linguagem L, L1 ◦ L ⊆ L2 ◦ L.
Resposta: Se w ∈ L1 ◦ L enta˜o existe u ∈ L1 e v ∈ L tais que w = uv. Como por
hipo´tese, L1 ⊆ L2, enta˜o u ∈ L2. Logo, w = uv ∈ L2 ◦ L.
9. Descreva de maneira gene´rica em que situac¸o˜es LP = (LS)R.
Resposta: Pelo exerc´ıcio 5c isso so´ ocorrera´ quando L = LR isto e´ quando L for um
subconjunto dos pal´ındromos.
A.2 Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
1. Construir um autoˆmato para reconhecer somente a sequ¨eˆncia 10110.
Resposta: Um afd que reconhece somente a cadeia 10110 e´ ilustrada na figura A.24.
3. Construir um autoˆmato finito determin´ıstico que reconhec¸a qualquer cadeia contendo um
nu´mero qualquer de co´pias de 001, seguido por 1 e nenhuma outra cadeia. Isto e´ o afd
deve reconhecer a linguagem:
{w1 ∈ {0, 1}∗ / w = 001n para algum n ≥ 0}
As cadeias reconhecidas por este autoˆmato sa˜o do tipo: 1, 0011, 0010011, 0010010011, etc.
280
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
1 0 1 1 0
0 1 0 0 1 1,0
1,0
q q q q q
q
0 1 2 3 4 5
6
q
Figura A.1: afd para o exerc´ıcio 1.
00q q q0 1 2
1
0
3
11
0,1
qq
4
0,1
Figura A.2: afd para o exerc´ıcio 3.
Resposta: Um afd que reconhece esta linguagem e´ ilustrada na figura A.2.
4. Para cada um dos seguintes casos, construir um afd que com os s´ımbolos de entrada
a, b, c, d reconhec¸a a descric¸a˜o das cadeias dadas e na˜o outras.
(4b) Qualquer cadeia terminando com um a.
Resposta: Um afd que reconhece esta linguagem e´ ilustrado na figura A.3.
(4c) Qualquer cadeia consistindo de um nu´mero par de co´pias de abb.
Resposta: Um afd que reconhece esta linguagem e´ ilustrado na figura A.4.
(4d) Qualquer cadeia em {a, bcd}∗. Isto e´ a linguagem
{λ, a, bcd, aa, abcd, bcdbcd, bcda, aaa, aabcd, . . .}.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
281
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
0 qq 1
b,c,d
b,c,d
a
a
Figura A.3: afd para o exerc´ıcio (4b).
q q
30
q q
1 2
a b
c,d
b
b
b a
a
a
b,c,d b,c,d
c,d
a
c,dc,d
a
q
4
q
5
Figura A.4: afd para o exerc´ıcio (4c).
Resposta: O afd da figura A.5 reconhece a linguagem {a, bcd}∗.
(4e) Qualquer cadeia contendo exatamente uma u´nica co´pia da cadeia abbb.
Resposta: Um afd que reconhece esta linguagem e´ ilustrado na figura A.6.
5. Desenhe afd’s que reconhec¸am os subconjuntos de {a, b}∗ consistindo de
(5a) Todas as cadeias com exatamente um a.
Resposta: O afd na figura A.7 reconhece esta linguagem.
(5c) Todas as cadeias com mais do que treˆs a’s.
Resposta: O afd da figura A.8 reconhece esta linguagem.
6. Dar uma afd que aceite os nu´meros, no sistema bina´rio, que:
(6a) Sa˜o mu´ltiplos de 4.
282
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
q
3
0
q q
1 2
a
b c
d
c,d
a,b,d
a,b,c
a,b,c,d
Figura A.5: afd para o exerc´ıcio (4d).
Resposta: Antes de mostrar o afd que reconhece esta linguagens, devemos analisar
que linguagem e´ esta.
Valor em Decimal Valor em bina´rio
0 0
4 100
8 1000
12 1100
16 10000
20 10100
...
...
Claramente, um nu´mero diferente de zero em bina´rio e´ mu´ltiplo de 4 se seus dois
u´ltimos d´ıgitos sa˜o 00.
Nos consideraremos zeros a` esquerda como na˜o significativos, e portanto 0000100 e 100
devem ser aceitos, pois ambos representam o nu´mero 4. A cadeia vazia, por questa˜o
de simplicidade sera´ tambe´m considerada como zero. Assim, sobre este entendimento,
um afd que reconhece esta linguagem e´ o afd da figura A.9.
(6b) Sa˜o mu´ltiplos de 3.
Resposta: Para desenhar este afd primeiro necessitamos entender a linguagem
dos nu´meros bina´rios e dentre eles analisar quais sa˜o mu´ltiplos de 3. Um nu´mero e´
mu´ltiplo de 3 se o resto da divisa˜o dele por 3 e´ 0. Enta˜o a tabela a seguir mostra os
nu´meros em decimal, bina´rio e seu resto (em decimal) da divisa˜o dele por 3.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
283
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
q q 30 q
q
1 2
a b
c,d
b
b
a
ab,c,d b,c,d
c,d
a
c,d
c,d
b
a
a
q
4
q
5
a,b,c,d
q
6
Figura A.6: afd para o exerc´ıcio (4d).
Valor em Decimal Valor em Bina´rio Resto da Divisa˜o por 3
0 0 0
1 1 1
2 10 2
3 11 0
4 100 1
5 101 2
6 110 0
7 111 1
8 1000 2
9 1001 0
10 1010 1
11 1011 2
12 1100 0
13 1101 1
14 1110 2
15 1111 0
...
...
...
Novamente consideramos que zeros a` esquerda na˜o sa˜o significativos e que a cadeia
vazia e´ considerada como zero.
Assim seria natural termos treˆs estados. Um para quando o resto for 0 (q0), outro
para quando for 1 (q1) e um u´ltimo para quando o resto for 2 (q2). Como, resto zero
significa que o nu´mero e´ mu´ltiplo de 3, enta˜o ele seria estado final e como a cadeia
vazia (ou seja antes ler qualquer s´ımbolo) e´ considerada como 0, e 0 e´ mu´ltiplo de 3,
enta˜o esse estado tambe´m seria inicial.
284
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
q
0
q 1
a
b
2
a
b
a,b
Figura A.7: afd para o exerc´ıcio (5a).
q q0 q 1
a
b
2
a
b a,bb
qa
3
Figura A.8: afd para o exerc´ıcio (5c).
Observe que se o valor em decimal de um nu´mero bina´rio w (denotaremos isto por
#w), for n, enta˜o#w0 e´ 2n e de #w1 e´ 2n+1. Assim, se o resto da divisa˜o por 3 de
um nu´mero bina´rio w for 0, enta˜o isso significa que #w = 3k para algum k ∈ N. Logo,
#w0 = 2#w = 2(3k) = 3(2k) e portanto o resto da divisa˜o de #w0 por 3 continuaria
sendo 0, isto implica em que ter´ıamos uma transic¸a˜o rotulada por 0 do estado q0 a
ele mesmo. Analogamente, #w1 = 2#w + 1 = 2(3k) + 1 = 3(2k) + 1 e portanto o
resto da divisa˜o #w1 por 3 passa a ser 1 o qual implica numa transic¸a˜o rotulada por
1 do estado q0 ao estado q1. Agora se o resto da divisa˜o de #w por 3 for 1, enta˜o
#w = 3k + 1 para algum k ∈ N e portanto #w0 = 2#w = 2(3k + 1) = 3(2k) + 2.
Logo, o resto da divisa˜o de #w0 por 3 seria 2, o qual implica numa transic¸a˜o rotulada
por 0 do estado q1 ao estado q2. Analogamente, #w1 = 2#w + 1 = 2(3k + 1) + 1 =
3(2k) + 3 = 3(2k + 1). Logo, o resto da divisa˜o de #w0 por 3 seria 0, o qual implica
numa transic¸a˜o rotulada por 1 do estado q1 ao estado q0. Finalmente, se o resto
da divisa˜o de #w por 3 for 2, enta˜o #w = 3k + 2 para algum k ∈ N e portanto
#w0 = 2#w = 2(3k+2) = 3(2k)+ 3+1 = 3(2k+1)+1. Logo, o resto da divisa˜o de
#w0 por 3 seria 1, o qual implica numa transic¸a˜o rotulada por 0 do estado q2 ao estado
q1. Analogamente, #w1 = 2#w+ 1 = 2(3k + 2) + 1 = 3(2k) + 3+ 2 = 3(2k + 1) + 2.
Logo, o resto da divisa˜o de #w0 por 3 seria 2, o qual implica numa transic¸a˜o rotulada
por 1 do estado q2 nele mesmo.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
285
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
q
0
q q
1 2
00
1
1
0
1
Figura A.9: afd para o exerc´ıcio (6a).
O afd da figura A.10 ilustra este autoˆmato.
q
0
q q1 2
0
0
1
1
0
1
Figura A.10: afd para o exerc´ıcio (6b).
7. Encontre afd’s para as seguintes linguagens sobre Σ = {a, b}.
(7a) L = {w ∈ Σ∗/ |w| mod 3 = 0},
Resposta: O afd da figura A.11 reconhece esta linguagem.
q
0
q q
1 2
a,b a,b
a,b
Figura A.11: afd para o exerc´ıcio (7a).
(7c) L = {w ∈ Σ∗/ Na(w) mod 3 > 1},
Resposta: O afd da figura A.12 reconhece esta linguagem.
(7e) L = {w ∈ Σ∗/ 2 ≤ Na(w) ≤ 4},
Resposta: O afd da figura A.13 reconhece esta linguagem.
(7g) L = {w ∈ Σ∗/ Na(w) 6∈ {1, 2, 3}},
Resposta: O afd da figura A.14 reconhece esta linguagem.
(7i) L = {ambn/ mn e´ ı´mpar},
286
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
0
q q
1 2
a a
a
b b b
Figura A.12: afd para o exerc´ıcio (7c).
q
0
q q
1 2
a a
b b b b b a,b
a a aq q q
3 4 5
Figura A.13: afd para o exerc´ıcio (7e).
Resposta: O afd da figura A.15 reconhece esta linguagem.
(7k) L = {w ∈ Σ∗/ Na(w) e´ ı´mpar e |w| e´ par}, onde Na(w) e´ o nu´mero de a’s que
ocorrem em w e |w| e´ o tamanho da cadeia w.
Resposta: O afd da figura A.16 reconhece esta linguagem. Neste autoˆmato o
estado q0 reflete a situac¸a˜o que a cadeia lida ate´ esse momento tem uma quantidade
par de a’s e e´ de tamanho par, ou seja, Na(w) e |w| sa˜o pares. O estado q1 sintetiza
a situac¸a˜o em que Na(w) e |w| sa˜o ı´mpares. O estado q2 captura a situac¸a˜o em que
Na(w) e´ par enquanto |w| e´ ı´mpar. Finalmente, o estado q3 a situac¸a˜o desejada, ou
seja, Na(w) e´ ı´mpar e |w| e´ par, e portanto e´ o estado final.
9. Considere o conjunto das cadeias, sobre {0, 1}, definido pela condic¸a˜o abaixo. Exiba um
afd para cada um desses conjuntos.
(9a) O primeiro e u´ltimo s´ımbolo sejam iguais.
Resposta: O afd da figura A.17 reconhece esta linguagem.
(9c) Que reconhec¸a a linguagem L = {vwv/v,w ∈ {a, b}∗ e |v| = 2}.
q
0
 q
1
 q
2
 q
4
q
3
a
 a
 a
 a
b
 a,b
b
 b
 b
Figura A.14: afd para o exerc´ıcio (7g).
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
287
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
q
0
 q
1
 q
2
 q
3
a
a
a,b
a
b
b
b
q
4
b
Figura A.15: afd para o exerc´ıcio (7i).
Resposta: O afd da figura A.18 reconhece esta linguagem.
(9e) Todo 00 e´ seguido imediatamente por 1. Por exemplo, as cadeias λ, 101, 0010,
0010111001 esta˜o na linguagem, mas 0001 e 00100, na˜o esta˜o.
Resposta: O afd da figura A.19 reconhece esta linguagem.
(9g) Toda subcadeia de quatro s´ımbolos tem, quando muito, dois zeros. Por exemplo,
0011100, 001101 e 1010101 esta˜o na linguagem, mas 10100110 na˜o esta´, pois uma de
suas subcadeias de quatro s´ımbolos, 0100, conte´m treˆs zeros.
Resposta: O afd da figura A.20 reconhece esta linguagem. Neste afd cada estado,
amenos do estado de morte q3, “armazena” os treˆs u´ltimos d´ıgitos lidos. No inicio,
para evitar introduzir novos estados, o afd assume que leu 111 antes de comec¸ar.
O estado q0 enta˜o representa 111, o estado q1 representa 110, o estado q2 representa
100 o estado q3 representa a situac¸a˜o onde houve uma subcadeia de tamanho 4 com
treˆs 0’s, o estado q4 representa 101, o estado q5 representa 010, o estado q6 representa
001 e o estado q7 representa 011. Observe no afd da figura A.20 que o estado de
chegada das arestas que saem dos estado q7 e q0 com o mesmo ro´tulo coincidem, e
portanto esses dois estados poderiam ser fusionados em um u´nico estado.
(9i) Qualquer ocorreˆncia de dois zeros pro´ximos (isto e´ sem qualquer 0 no meio), esteja
separado por uma quantidade ı´mpar de uns. Por exemplo, λ, 111, 11011, 011101011 e
110101110101 fazem parte desta linguagem, mas as cadeias 0010 e 111010110 na˜o.
Resposta: O afd da figura A.21 reconhece esta linguagem.
11. Seja M = 〈Q,Σ, δ, q0, F 〉 um afd. Mostre que δ∗(q, vw) = δ∗(δ∗(q, v), w) para todo
v,w ∈ Σ∗.
Resposta: Provaremos por induc¸a˜o no tamanho de w.
Base da Induc¸a˜o: Se w = λ enta˜o δ∗(q, vw) = δ∗(q, vλ) = δ∗(q, v) e δ∗(δ∗(q, v), w) = δ∗(δ∗(q, v), λ) =
δ∗(q, v) e portanto ambos sa˜o iguais.
288
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
0
 q
1
q
2
 q
3
a
a
b
b
a
a
b
b
Figura A.16: afd para o exerc´ıcio (7k).
Hipo´teses indutiva: δ∗(q, vw) = δ∗(δ∗(q, v), w) para todo v,w ∈ Σ∗ tal que |w| = k
Passo indutivo: Seja a ∈ Σ e v,w ∈ Σ∗ tal que |w| = k. Enta˜o
δ∗(q, vwa) = δ(delta∗(q, vw), a) por definic¸a˜o de δ∗
= δ(delta∗(δ∗(q, v), w), a) por hipo´tese indutiva
= delta∗(δ∗(q, v), wa) por definic¸a˜o de δ∗
13. Para o afn na figura 2.9, ache δ∗(q1, 100) e δ∗(q0, 00101).
Resposta: Faremos isto passo a passo seguindo a definic¸a˜o de δ∗ para afn sem λ-
transic¸o˜es (equac¸o˜es 2.4 e 2.5).
δ∗(q1, 100) =
⋃
q∈δ∗(q1,10) δ(q, 0)
=
⋃
q∈⋃q′∈δ∗(q1,1) δ(q′,0)
δ(q, 0)
=
⋃
q∈⋃q′∈⋃
q′′∈δ∗(q1,λ) δ(q
′′,a) δ(q
′,0) δ(q, 0)
=
⋃
q∈⋃q′∈⋃
q′′∈{q1} δ(q
′′,a) δ(q
′,0) δ(q, 0)
=
⋃
q∈⋃q′∈δ(q1,a) δ(q′,0)
δ(q, 0)
=
⋃
q∈⋃q′∈{q2} δ(q′,0)
δ(q, 0)
=
⋃
q∈δ(q2,0) δ(q, 0)
=
⋃
q∈{q1} δ(q, 0)
= δ(q1, 0) = ∅
Para o outro caso, usaremos a ide´ia intuitiva para a func¸a˜o de transic¸a˜o estendida e que
foi expressa na definic¸a˜o 2.4.5.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
289
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
q
0
q
1
 q
2
q
3
0
0
1
1
0
0
1
1
q
4
1
 0
Figura A.17: afd para o exerc´ıcio (9a).
δ∗(q0, 00101) = δ∗(q0, 0101) ∪ δ∗(q1, 0101) pois δ(q0, 0) = {q0, q1}
= (δ∗(q0, 101) ∪ δ∗(q1, 101)) ∪ ∅ pois δ(q0, 0) = {q0, q1} e δ(q1, 1) = ∅
= ∅ ∪ δ∗(q2, 01) pois δ(q0, 1) = ∅ e δ(q1, 1) = {q2}
= δ∗(q1, 1) pois δ(q2, 0) = {q1}
= δ∗(q2, λ) pois δ(q1, 1) = {q2}
= {q2}
15. Seja L a linguagem aceita pelo autoˆmato da figura 2.2. Achar um afd que aceite L2.
Resposta: Antes de desenhar o afd que aceite a linguagem L2, onde L e´ a linguagem
reconhecida pelo autoˆmato dafigura 2.2 devemos analisar quem e´ L e quem e´ L2.
Claramente, L = {anb / n ≥ 0} e portanto L2 = {anbamb / n ≥ 0 e m ≥ 0}. Assim, o
autoˆmato da figura A.22 reconhece L2.
17. Projete um afn, com na˜o mais que cinco estados, para o conjunto
{ababn/ n ≥ 0} ∪ {aban/ n ≥ 0}
Resposta: Um afn com cinco estados que reconhece esta linguagem e´ mostrado na
figura A.23.
??. Construa um afn que aceite a linguagem de todas as cadeias sobre o alfabeto {0, 1} com
um nu´mero par de 1’s ou um nu´mero ı´mpar de 0’s.
Resposta: Um afn que reconhece esta linguagem e´ ilustrado na figura A.24.
22. Use a construc¸a˜o do teorema 2.5.3 para converter os afn’s das figuras 2.11, 2.15, 2.24,
2.25, 2.27 e 2.28, e do exerc´ıcio ?? para afd ´s equivalentes. E´ poss´ıvel respostas mais
simples se fizermos os afd ´s diretamente?
290
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
0
q
q
1
2
q
q
q
q
q
q
q
3
4
5
6
7
8
9
0
0
1
1
0
1
0,1
0,1
0,1
0,1
0
0
1
1
0
1
Figura A.18: afd para o exerc´ıcio (9c).
Resposta: Aqui so´ veremos dois casos.
1. A figura A.25 mostra a conversa˜o do afn do exerc´ıcio ?? (figura A.24), para um
afd.
E´ poss´ıvel diminuir a quantidade de estados no autoˆmato, eliminando o estado inicial
com suas λ-transic¸o˜es e levando um controle da paridade de 1’s e 0’s lidos, de modo
similar ao autoˆmato constru´ıdo no exemplo 2.2.6. Assim, o afd da figura A.26
e´ uma outra alternativa para reconhecer a linguagem do exerc´ıcio ?? com menos
estados que o da figura A.25.
2. A figura A.27 mostra a conversa˜o do afn da figura 2.24, para um afd.
23. E´ verdade que para qualquer afn M = 〈Q,Σ, δ, q0, F 〉 o complemento de L(M) e´ igual ao
conjunto {w ∈ Σ∗/ δ∗(q0, w) ∩ F = ∅}? Prove sua resposta.
Respostas: Sim, pois
L(M) = σ∗ − L(M)
= Σ∗ − {w ∈ Σ∗ / δ∗(q0, w) ∩ F 6= ∅}
= {w / w ∈ Σ∗ e w 6∈ {w ∈ Σ∗ / δ∗(q0, w) ∩ F 6= ∅}}
Como {w ∈ Σ∗ / δ∗(q0, w) ∩ F 6= ∅} ⊆ Σ∗, temos que
L(M) = {w ∈ Σ∗ / na˜o e´ o caso que δ∗(q0, w) ∩ F 6= ∅}
= {w ∈ Σ∗ / δ∗(q0, w) ∩ F = ∅}
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
291
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
q
0
 q
1
 q
2
0
0
1
1
0
0,1
1
q
3
Figura A.19: afd para o exerc´ıcio (9e).
q
0
 q
1
 q
2
0
 0
1
1
0
0,1
1
q
3
0
q
5
q
4
0
q
6
0
1
q
7
1
1
1
 0
Figura A.20: afd para o exerc´ıcio (9g).
24. Mostre que se L e´ reconhecida por um autoˆmato finito (determin´ıstico ou na˜o), enta˜o LR
e L tambe´m sa˜o reconhecidos por algum autoˆmato finito.
Resposta: Se L e´ uma linguagem regular, enta˜o existe um afd M = 〈Q,Σ, δ, q0, F 〉 tal
que L(M) = L, isto e´ que reconhece L. Seja o seguinte afn MR = 〈Q̂,Σ, δ̂, q̂0, F̂ 〉 onde
1. Q̂ = Q ∪ q̂0
2. q̂0 6∈ Q e
3. δ̂ : Q̂× Σ ∪ {λ} −→ 2Q̂ e´ definido como segue:
δ̂(q, a) =

{q′} , se q ∈ Q e a ∈ Σ e δ(q′, a) = q
∅ , se q = q̂0 e a ∈ Σ
∅ , se q ∈ Q e a = λ
F , se q = q̂0 e a = λ
4. F̂ = {q0}
292
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
0
 q
1
 q
2
0
 0
1
 0,1
1
 0,1
q
3
Figura A.21: afd para o exerc´ıcio (9i).
q
0
q q
1 2
a
a a,b
b b a,b q
3
Figura A.22: afd para o exerc´ıcio 15.
Observe que o u´nico que se fez foi inverter as setas no diagrama, tirar o status de estado
inicial a q0 e poˆr um novo estado como inicial (q̂0), tirar o status dos estados finais e deixar
como estado final somente a {q0} (o antigo estado inicial); e acrescentar uma λ-transic¸a˜o
do novo estado inicial aos antigos estados finais. Assim, se para um certo w ∈ Σ∗ existe
um caminho em M que leva do estado inicial q0 a um estado final qf , isto e´ δ
∗(q0, w) ∈ F ,
enta˜o aplicando a λ-transic¸a˜o de q̂0 a qf no afn M
R e (como as setas esta˜o invertidas)
lendo w de direita para esquerda (ou seja consumindo wR) chegaremos necessariamente
a q0 que agora e´ um estado final. Portanto w
R sera´ aceito no afn MR. Assim, MR
reconhece a linguagem LR, isto e´ L(MR) = LR e portanto esta linguagem e´ regular.
No caso da linguagem L podemos facilmente obter um afd a partir deM que a reconhec¸a.
Seja M = 〈Q,Σ, δ, q0, F 〉, onde F = Σ∗ − F . Claramente, se δ(q0, w) ∈ F (ou seja w e´
aceito porM e por tanto faz parte de L), enta˜o δ(q0, w) 6∈ F , isto e´, δ(q0, w) ∈ F e portanto
w e´ aceito por M . Assim, M reconhece a linguagem L, isto e´ L(M) = L e portanto esta
linguagem e´ regular.
25. Seja Σ = {a, b}. Construa um afn, que na˜o seja afd, e depois transforme ele num afd
usando o algoritmo do teorema 2.5.3, para as seguintes linguagens:
(25a) L = {w ∈ Σ∗/w = uaaav para alguma cadeia u e v tal que Nb(v) e´ mu´ltiplo de 3},
Resposta: O afn da figura A.28 reconhece esta linguagem.
(25c) L = {w ∈ Σ∗/ w = uaaav, para alguma cadeia u, v ∈ Σ∗, e Na(u) e´ ı´mpar},
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
293
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
q
0
q
q
1 2
q
q3 4
a b
a
b
a
b
Figura A.23: afn para o exerc´ıcio 17.
q
0
q
1
 q
2
q
3
0
0
1
1
0
1
λ
q
4
1
0
λ
Figura A.24: afn para o exerc´ıcio ??.
Resposta: O afn da figura A.29 reconhece esta linguagem.
(25e) L = {uv ∈ Σ∗/ Na(u) = 3 e Nb(v) e´ mu´ltiplo de 3},
Resposta: O afn da figura A.30 reconhece esta linguagem.
27. Seja o afd da figura A.31 e aplique o algoritmo da minimizac¸a˜o de estados para achar um
afd mı´nimo equivalente a ele.
Resposta: Aplicando o passo 1 do algoritmo obtemos a tabela A.1
Agora aplicando o passo 2 (uma primeira rodada):
• como δ(q0, b) = q3, δ(q2, b) = q4, e (q3, q4) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q0, q2).
294
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
0
1 0
0
{q0,q1,
q3}
{q1,q4}
{q2,q3}
{q1,q3}
{q2,q4}
0
0
1
11
1
Figura A.25: afd equivalente ao afn da figura A.24.
PP
PI
IP
II
1
1
0
0
0
0 1
1
Figura A.26: afd equivalente ao afd da figura A.25.
• como δ(q0, a) = q2, δ(q3, a) = q4, e (q2, q4) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q0, q3).
• como δ(q0, a) = q2, δ(q6, a) = q4, e (q2, q4) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q0, q6).
• como δ(q0, b) = q3, δ(q7, b) = q4, e (q3, q4) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q0, q7).
• como δ(q1, b) = q3, δ(q2, b) = q4, e (q3, q4) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q1, q2).
• como δ(q1, a) = q7, δ(q3, a) = q4, e (q4, q7) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q1, q3).
• como δ(q1, b) = q3, δ(q5, b) = q1, e (q1, q3) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q1, q5).
• como δ(q1, a) = q7, δ(q6, a) = q4, e (q4, q7) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q1, q6).
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
295
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
0
1
0
0,1
{q
0
}
φ
{q
0,
q
1
}
 {q
0,
q
2
}
1
{q
0,
q
1,
q
2
}
1
1
{q
2
}
0
0
0
1
Figura A.27: afd equivalente ao afn da figura 2.24.
• como δ(q1, b) = q3, δ(q7, b) = q4, e (q3, q4) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q1, q7).
• como δ(q2, b) = q4, δ(q3, b) = q5, e (q4, q5) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q2, q3).
• como δ(q2, b) = q4, δ(q5, b) = q1, e (q1, q4) esta´ marcado,enta˜o colocamos uma marca
na posic¸a˜o (q2, q5).
• como δ(q2, b) = q4, δ(q6, b) = q5, e (q4, q5) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q2, q6).
• como δ(q3, a) = q4, δ(q5, a) = q5, e (q4, q5) esta´ marcado, enta˜o colocamos uma marca
q1
q2
q3
q4 × × × ×
q5 ×
q6 ×
q7 ×
q0 q1 q2 q3 q4 q5 q6
Tabela A.1: Estados que na˜o sa˜o do mesmo tipo no afd da Figura A.31.
296
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
0
 q
1
 q
2
a
 b
a
a,b
q
3
a
a
 a
q
4
q
5
b
b
a
Figura A.28: afn para o exerc´ıcio (25a).
q
0
 q
1
 q
2
a
 a
a
b
q
3
a
a,b
a
b
q
4
Figura A.29: afn para o exerc´ıcio (25c).
na posic¸a˜o (q3, q5).
• como δ(q3, a) = q4, δ(q7, a) = q5, e (q4, q5) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q3, q7).
• como δ(q5, a) = q5, δ(q6, a) = q4, e (q4, q5) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q5, q6).
• como δ(q5, b) = q1, δ(q7, b) = q4, e (q1, q4) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q5, q7).
• como δ(q6, a) = q4, δ(q7, a) = q5, e (q4, q5) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q6, q7).
Agora aplicando o passo 2 (uma segunda rodada):
• como δ(q0, a) = q2, δ(q5, a) = q5, e (q2, q5) esta´ marcado, enta˜o colocamos uma marca
na posic¸a˜o (q0, q5).
A tabela A.2 apresenta o resultado de marcar as posic¸o˜es acima na tabela A.1.
Observe que as treˆs posic¸o˜es em branco na˜o podem ser marcadas pois:
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
297
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
q
0
 q
1
 q
2
a
a
a
b
q
3
a
 b,
λ
b
q
4
b
 b
q
5
b
a
q
6
b
b
a
Figura A.30: afn para o exerc´ıcio (25e).
q1
q2 × ×
q3 × × ×
q4 × × × ×
q5 × × × × ×
q6 × × × × ×
q7 × × × × × ×
q0 q1 q2 q3 q4 q5 q6
Tabela A.2: Estados que sa˜o equivalentes no afd da Figura A.31.
• δ(q0, a) = q2, δ(q1, a) = q7, e (q2, q7) na˜o esta marcado e δ(q0, b) = δ(q1, b).
• δ(q2, a) = δ(q7, a) e δ(q2, a) = δ(q7, a).
• δ(q3, a) = δ(q6, a) e δ(q3, a) = δ(q6, a).
Assim, a tabela A.2 apresenta os estados que sa˜o equivalentes no afd da Figura A.31 e
portanto podemos determinar as seguintes classes de equivaleˆncias:
• [q0] = {q0, q1}
• [q2] = {q2, q7}
• [q3] = {q3, q6}
• [q4] = {q4}
• [q5] = {q5}
Estas classes de equivaleˆncias sera˜o os estados do afd mı´nimo. O estado inicial e´ [q0] e o
estado final e´ [q4]. As transic¸o˜es sa˜o descritas a seguir:
• δ/≡([q0], a) = [δ(q0, a)] = [q2]
298
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
0
 q
2
q
1
 q
3
q
6
q
4
q
5
 q
7
a
a
a
a
a
a
a
a
b
b
b
b
b
b
b
b
Figura A.31: afd na˜o mı´nimo do exerc´ıcio 27
• δ/≡([q0], b) = [δ(q0, b)] = [q3]
• δ/≡([q2], a) = [δ(q2, a)] = [q5]
• δ/≡([q2], b) = [δ(q2, b)] = [q4]
• δ/≡([q3], a) = [δ(q3, a)] = [q4]
• δ/≡([q3], b) = [δ(q3, b)] = [q5]
• δ/≡([q4], a) = [δ(q4, a)] = [q0]
• δ/≡([q4], b) = [δ(q4, b)] = [q4]
• δ/≡([q5], a) = [δ(q5, a)] = [q5]
• δ/≡([q5], b) = [δ(q5, b)] = [q1] = [q0]
Assim a figura A.32 e´ o afd mı´nimo correspondente ao afd da figura A.31.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
299
A.2. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 2
[q
4
]
[q
2
]
[q
3
]
 [q
5
]
[q
0
]
a
b
a
b
a
b
a
b
a
b
Figura A.32: afd M/≡ obtido a partir do afd da Figura A.31.
300
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
A.3 Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 3
3. Escrever expresso˜es regulares para as seguintes linguagens no alfabeto {0, 1}:
(3a) Todas as cadeias terminando em 01.
Resposta: (0 + 1)∗01
(3c) Todas as cadeias com um nu´mero par de zeros.
Resposta: (01 ∗ 0 + 1)∗
(3d) Todas as cadeias com no ma´ximo duas ocorreˆncias da subcadeia 00.
Resposta: Entenderemos neste enunciado que a cadeia 0000 conte´m 3 ocorreˆncias
da subcadeia 00
3︷︸︸︷
00︸︷︷︸
1
00︸︷︷︸
2
Analogamente a cadeia 000 conte´m exatamente duas ocorreˆncias da subcadeia 00.
Nesta compreensa˜o, algumas expresso˜es regulares que descrevem esta linguagem sa˜o:
1. (01 + 1) ∗ (001(01 + 1)∗00 + 000 + 00 + λ)(10 + 1)∗
2. (01 + 1)∗((00 + λ)(1 + 10)∗(100 + λ) + 000)(10 + 1)∗
3. (01 + 1)∗(00((10 + 1)∗0(10 + 1)∗ + 1 + λ) + λ+ 0)
4. (01 + 1)∗00(10 + 1)∗0(10 + 1)∗ + (01 + 1)∗001∗ + (01 + 1)∗
(3e) de todas as cadeias que contenham as subcadeias 000 e 111.
Resposta: ((0 + 1)∗000(0 + 1)∗111(0 + 1)∗) + ((0 + 1)∗111(0 + 1)∗000(0 + 1)∗)
(3g) Todas as cadeias que para alguma ocorreˆncia de dois zeros eles estejam separados
por uma subcadeia de tamanho 3i, para algum i ≥ 0.
Resposta: Observe que uma cadeia com dois zeros consecutivos faz parte da lin-
guagem.
(0 + 1)∗0(101 + 111)∗0(0 + 1)∗
(3j) Todas as cadeias com uma quantidade ı´mpar de zeros.
Resposta: 1∗0(1∗01∗0)∗1∗
(3l) Todas as cadeias que na˜o contenham qualquer ocorreˆncia da subcadeia 000.
Resposta: (1 + 01 + 001)∗.
(3n) Todas as cadeias com exatamente uma ocorreˆncia da subcadeia 111.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
301
A.3. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 3
Resposta: (0 + 10 + 110)∗111(0 + 10 + 110)∗
(3p) Todas as cadeias com exatamente duas ocorreˆncias da subcadeia 000 e as quais
estejam separadas por uma quantidade ı´mpar de uns.
Resposta: (1 + 01 + 001)∗0001(11)∗000(1 + 01 + 001)∗.
5. Demonstre que:
(5a) (a+ b)∗ ≡ (a∗b∗)∗
Resposta:
L((a+ b)∗) = (L(a+ b))∗
= (L(a) ∪ L(b))∗
= ({a} ∪ {b})∗
= {a, b}∗
= {λ, a, b, aa, ab, ba, bb, aaa, aab, . . .}
L((a∗b∗)∗) = (L(a∗b∗))∗
= (L(a∗)L(b∗))∗
= (L(a)∗L(b)∗)∗
= ({a}∗{b}∗)∗
= ({λ, a, aa, aaa, . . .}{λ, b, bb, bbb, . . .})∗
= {λ, b, bb, . . . , a, ab, abb, . . . , aa, aab, . . .}∗
= {λ, a, b, aa, ab, ba, bb, aaa, aab, . . .}
Uma maneira mais formal de demonstrar a equivaleˆncia L((a + b)∗) = L((a∗b∗)∗) =
{a, b}∗ seria usando induc¸a˜o no tamanho da cadeia. A base da induc¸a˜o seria a cadeia
vazia (λ) a qual claramente pertence a ambas linguagens. A hipo´tese indutiva seria
uma cadeia arbitraria w ∈ L((a + b)∗) e w ∈ L((a∗b∗)∗). O passo indutivo seria
mostrar que wa,wb ∈ L((a+ b)∗) e wa,wb ∈ L((a∗b∗)∗).
(5c) a∗b∗ 6≡ (ab)∗
Resposta: Como por definic¸a˜o L(a∗b∗) = L(a∗)L(b∗) resulta fa´cil de ver que b ∈
L(a∗b∗), pois b = λb, λ ∈ L(a∗) e b ∈ L(b∗). Por outro lado, como L((ab)∗) = {ab}∗ =
{λ, ab, abab, ababab, . . .} enta˜o b 6∈ L((ab)∗) e portanto L(a∗b∗) 6= L((ab)∗).
(5e) aa∗ ≡ a∗a
302
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
Resposta:
L(aa∗) = L(a)L(a∗)
= {a}L(a)∗
= {a}{a}∗
= {a}{λ, a, aa, aaa, . . .}
= {a, aa, aaa, aaaa, . . .}
L(a∗a) = L(a∗)L(a)
= L(a)∗{a}
= {a}∗{a}
= {λ, a, aa, aaa, . . .}{a}
= {a, aa, aaa, aaaa, . . .}
7. Achar autoˆmatos finitos que aceitem as seguintes linguagens
Resposta: E´ claro que poder´ıamos usar o algoritmo do teorema 3.4.1, mas este e´ muito
tedioso e longo, pelo que optamos por construir diretamente o afn a partir da intuic¸a˜o da
linguagem.
(7a) L(aa∗(a+ b))
Resposta: Um afn que reconhece a linguagem L(aa∗(a+ b)) e´ ilustrado na figura
A.33. Observe que neste autoˆmato cada sub-expressa˜o regular de aa∗(a+ b) tem um
segmento do afn que “reconhece” essa expressa˜o.
q q0 q 1
a
2
a
a,b
Figura A.33: afn que reconhecea linguagem L(aa∗(a+ b))
(7c) L((ab+ b)∗(a+ λ))∗
Resposta: Um afn que reconhece a linguagem L((ab + b)∗(a + λ))∗ e´ ilustrado
na figura A.34 parte (A). No entanto, note que a ∈ L((ab + b)∗(a + λ)), pois λ ∈
L((ab + b)∗), a ∈ L(a + λ) e λa = a. Analogamente, b ∈ L((ab + b)∗(a + λ)), pois
b ∈ L((ab+ b)∗), λ ∈ L(a+ λ) e bλ = b. Logo,
L((ab+ b)∗(a+ λ)) = L((ab+ b)∗(a+ λ) + a+ b)
Portanto,
L(((ab+ b)∗(a+ λ))∗) = L(((ab+ b)∗(a+ λ) + a+ b)∗) = L((a+ b)∗)
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
303
A.3. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 3
Logo, um afn para a expressa˜o regular equivalente (a + b)∗ e´ ilustrado na figura
A.34 parte (B). Claramente, ambos autoˆmatos sa˜o equivalentes, isto e´, reconhecem a
mesma linguagem, mas o primeiro e´ inspirado na forma da expressa˜o regular ((ab +
b)∗(a + λ))∗ enquanto que o segundo e´ produto de uma ana´lises da linguagem em
questa˜o.
qq 0 q 1 2
ba, 
q
3
a, 
a,b
(B)
(A)
q
0
Figura A.34: afn que reconhece a linguagem L((ab+ b)∗(a+ λ))∗
(7e) L(aa∗bb∗aa∗)
Resposta: Um afn que reconhece a linguagem L(aa∗bb∗aa∗) e´ ilustrado na figura
A.35.
a b a
a bq q q a q
0 1 2 3
Figura A.35: afn que reconhece a linguagem L(aa∗bb∗aa∗)
(7g) L(a∗(b(bb)∗aa)∗)
Resposta: Um afn que reconhece a linguagem L(a∗(b(bb)∗aa)∗) e´ ilustrado na
figura A.36.
304
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
q
0
 q
1
 q
2
 q
3
a
a
a
b
b
b
q
4
λ
Figura A.36: afn que reconhece a linguagem L(a∗(b(bb)∗aa)∗)
8. Construir seguindo o algoritmo da sec¸a˜o 3.4.2 a expressa˜o regular que denota a linguagem
reconhecida pelo afd da figura 3.14.
Resposta: Segundo esse algoritmo devemos achar R21,1, mas para isso precisaremos achar
outros Rki,j intermedia´rios. Assim, a seguir acharei primeiro eles.
R01,1 = λ
R01,2 = 0 + 1
R02,1 = 1
R02,2 = λ+ 0
R11,1 = R
0
1,1(R
0
1,1)
∗R01,1 +R01,1
= λ(λ)∗λ+ λ
= λ
R11,2 = R
0
1,1(R
0
1,1)
∗R01,2 +R
0
1,2
= λ(λ)∗(0 + 1) + (0 + 1)
= 0 + 1
R12,1 = R
0
2,1(R
0
1,1)
∗R01,1 +R
0
2,1
= 1(λ)∗λ+ 1
= 1
R12,2 = R
0
2,1(R
0
1,1)
∗R01,2 +R
0
2,2
= 1(λ)∗(0 + 1) + (λ+ 0)
= 1(0 + 1) + λ+ 0
= λ+ 0 + 10 + 11
R21,1 = R
1
1,2(R
1
2,2)
∗R12,1 +R
1
1,1
= (0 + 1)(λ+ 0 + 10 + 11)∗1 + λ
Observe que, pelo fato de ser um afd simples, teria sido poss´ıvel obter a expressa˜o regular
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
305
A.3. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 3
((0 + 1)0∗1)∗
de forma direta se analisando o autoˆmato. Embora na˜o muito evidente, ambas expresso˜es
regulares sa˜o equivalentes.
9. Construir uma grama´tica linear a´ direita e uma linear a` esquerda para as linguagens
(9a) L((aab∗abab)∗)
Resposta: Uma grama´tica linear a` direita que gera esta linguagem e´ definida por
G = 〈{S,B}, {a, b}, S, P 〉, onde P e´ composto das seguintes produc¸o˜es
S −→ aaB | λ
B −→ bB | ababS
Uma grama´tica linear a` esquerda para esta mesma linguagem teria as seguintes
produc¸o˜es:
S −→ Babab | λ
B −→ Bb | Saa
(9c) L((a+ b)∗aaa)
Resposta: Uma grama´tica linear a` direita que gera esta linguagem e´ definida por
G = 〈{S}, {a, b}, S, P 〉, onde P e´ composto das seguintes produc¸o˜es
S −→ aS | bS | aaa
Uma grama´tica linear a` esquerda para esta mesma linguagem teria as seguintes
produc¸o˜es:
S −→ Aaaa
A −→ Aa | Ab | λ
(9e) L((a(aa)∗(bb)∗)∗aa∗)
Resposta: Uma grama´tica linear a` direita que gera esta linguagem e´ definida por
G = 〈{S,A,B,C}, {a, b}, S, P 〉, onde P e´ composto das seguintes produc¸o˜es
S −→ aA | aC
A −→ aaA | B
B −→ bbB | S
C −→ aC | a
Uma grama´tica linear a` esquerda para esta mesma linguagem teria as seguintes
produc¸o˜es:
S −→ Sa | Aa
A −→ B | λ
B −→ Bbb | C
C −→ Caa | Aa
11. Construir uma grama´tica regular que gere cada uma das seguintes linguagens sobre o
alfabeto {a, b}.
(11a) Todas as cadeias que terminem com treˆs a′s.
306
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
Resposta: Uma grama´tica regular (linear a` direita) que gera esta linguagem e´
definida por G = 〈{S}, {a, b}, S, P 〉, onde P e´ composto das seguintes produc¸o˜es
S −→ aS | bS | aaa
(11c) Todas as cadeias diferentes de (aaa)k, para qualquer k ≥ 0.
Resposta: Uma grama´tica regular (linear a` direita) que gera esta linguagem e´
definida por G = 〈{S,A}, {a, b}, S, P 〉, onde P e´ composto das seguintes produc¸o˜es
S −→ bA | aaaS | a | aa
A −→ aA | bA | λ
(11e) Todas as cadeias da forma aawaa, onde |w| e´ mu´ltiplo de treˆs.
Resposta: Uma grama´tica regular (linear a` direita) que gera esta linguagem e´
definida por G = 〈{S,A}, {a, b}, S, P 〉, onde P e´ composto das seguintes produc¸o˜es
S −→ aaA
A −→ aaaA | aabA | abaA | abbA | baaA | babA | bbaA | bbbA | aa
(11g) Todas as cadeias com uma quantidade par de a’s mas sem qualquer ocorreˆncia da
subcadeia aaa.
Resposta: Uma grama´tica linear a` direita que gera esta linguagem e´ definida por
G = 〈{S,A,B,C,D,E}, {a, b}, S, P 〉, onde P e´ composto das seguintes produc¸o˜es.
S −→ bS | aA | λ
A −→ bB | aE
B −→ bB | aC
C −→ bS | aD | λ
D −→ bB
E −→ bS | λ
Nesta grama´tica S representa a situac¸a˜o onde ate´ esse momento foi gerado uma
quantidade par de a’s e onde o u´ltimo s´ımbolo gerado na˜o foi a. A representa a
situac¸a˜o onde ate´ esse momento foi gerado uma quantidade ı´mpar de a’s, o u´ltimo
s´ımbolo foi a mas o antepenu´ltimo na˜o foi a. B representa a situac¸a˜o onde ate´ esse
momento foi gerado uma quantidade ı´mpar de a’s e onde o u´ltimo s´ımbolo na˜o foi a.
C representa a situac¸a˜o onde ate´ esse momento foi gerado uma quantidade par de a’s,
o u´ltimo s´ımbolo foi a mas o antepenu´ltimo na˜o foi a. D representa a situac¸a˜o onde
ate´ esse momento foi gerado uma quantidade ı´mpar de a’s, os dois u´ltimos s´ımbolos
foram a’s mas o anterior a eles (caso haja algum) na˜o foi a. E representa a situac¸a˜o
onde ate´ esse momento foi gerado uma quantidade par de a’s, os dois u´ltimos s´ımbolos
foram a’s mas o anterior a eles (caso haja algum) na˜o foi a.
12. Achar as grama´ticas regulares para as linguagens reconhecidas pelos autoˆmatos da figura
3.15 seguindo o algoritmo da subsec¸a˜o 3.6.2.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
307
A.3. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 3
Resposta: As grama´ticas regulares seguintes descrevem as linguagens reconhecidas pelos
afd’s da figura 3.15.
(12a) A grama´tica linear a` direita resultante de aplicar o algoritmo da subsec¸a˜o 3.6.2 ao afd
da figura 3.15.a, e´ definida por G = 〈{q0, . . . , q4}, {a, b}, q0, P 〉, onde P e´ composto das
seguintes produc¸o˜es.
q0 −→ bq0 | aq1
q1 −→ aq1 | bq2
q2 −→ bq2 | aq3
q3 −→ aq4 | bq1 | λ
q4 −→ aq4 | bq4
(12c) A grama´tica linear a` direita resultante de aplicar o algoritmo da subsec¸a˜o 3.6.2 ao afd
da figura 3.15.c, e´ definida por G = 〈{q0, . . . , q4}, {a, b}, q0, P 〉, onde P e´ composto das
seguintes produc¸o˜es.
q0 −→ aq1 | bq3
q1 −→ aq1 | bq2 | λ
q2 −→ aq1 | bq2
q3 −→ aq4 | bq3 | λ
q4 −→ aq4 | bq3
13. Construir um afn, seguindo o algoritmo da subsec¸a˜o 3.6.1, para cada uma das seguintes
grama´ticas
(13a) S −→ abA;
A −→ baB;
B −→ aA | bb
Resposta: O afn ilustrado na figura A.37 reconhece a mesma linguagem gerada
por esta grama´tica regular.
S
 a
 A
b
 b
a
B
a
b
b
Figura A.37: afn que reconhece a linguagem gerada pela grama´tica regular do exerc´ıcio (13a).
(13c) S −→ aA | bS | λ;
A −→ aB | bS | λ;
B −→ aaS | bS | λ
308
Introduc¸a˜o a` Teoria da Computac¸a˜o:
LinguagensFormais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
Resposta: O afn ilustrado na figura A.38 reconhece a mesma linguagem gerada
por esta grama´tica regular.
S
a
A
b
b
 a
B
a
a
b
Figura A.38: afn que reconhece a linguagem gerada pela grama´tica regular do exerc´ıcio (13c).
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
309
A.4. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 4
A.4 Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 4
1. Prove que toda linguagem finita e´ regular.
Resposta: Se L e´ uma linguagem finita sobre um alfabeto Σ, enta˜o L = {w1, . . . , wn}
para algum n ≥ 0. Cada wi tem a seguinte forma: wi = ai1 · · · aiki . Claramente o afn
M = 〈{q0, q11 , . . . , q1k1 , . . . , qn1 , . . . , qnkn},Σ, q0, δ, {q1k1 , q2k2 , . . . , qnkn}〉 onde para cada i =
1, . . . , n, j = 1, . . . , ki− 1 e a ∈ Σ, temos que
δ(q0, a) = {qi1 : ai1 = a}
δ(qij , a) =
{ ∅ se a 6= aij+1
{qij+1} se a = aij+1
δ(qiki , 0) = ∅
3. Quais das seguintes igualdades sa˜o verdadeiras para todas as linguagens regulares e todos
os homomorfismos? Justifique.
(3a) h(L1 ∪ L2) = h(L1) ∪ h(L2)
Resposta: Se w ∈ h(L1 ∪L2), enta˜o w = h(v) para algum v ∈ L1 ∪L2. Se v ∈ L1,
enta˜o h(v) ∈ h(L1) e portanto w ∈ h(L1) ∪ h(L2). Analogamente, se v ∈ L2, enta˜o
h(v) ∈ h(L2) e portanto w ∈ h(L1) ∪ h(L2).
Por outro lado, se w ∈ h(L1) ∪ h(L2), enta˜o w ∈ h(L1) ou w ∈ h(L2). Se w ∈ h(L1),
enta˜o existe v ∈ L1 tal que h(v) = w. Logo, v ∈ L1 ∪ L2 e h(v) = w ∈ h(L1 ∪ L2).
Analogamente, se w ∈ h(L2), enta˜o existe v ∈ L2 tal que h(v) = w. Logo, v ∈ L1∪L2
e h(v) = w ∈ h(L1 ∪ L2).
Portanto, esta igualdade e´ verdadeira.
(3b) h(L1 ∩ L2) = h(L1) ∩ h(L2)
Resposta: Se w ∈ h(L1 ∩ L2), enta˜o w = h(v) para algum v ∈ L1 ∩ L2 e portanto
v ∈ L1 e v ∈ L2. Assim, w ∈ h(L1) e w ∈ h(L2). Logo, w ∈ h(L1) ∩ h(L2).
No entanto a reversa de esta igualdade na˜o e´ correta, isto e´ se w ∈ h(L1)∩h(L2), na˜o
necessariamente e´ verdade que w ∈ h(L1 ∩ L2). Provaremos isto atrave´s do seguinte
contra-exemplo: Seja L1 = {ab}, L2 = {ba} e h(a) = h(b) = ab. Trivialmente,
h(L1) ∩ h(L2) = h({ab}) ∩ h({ba})
= {h(ab)} ∩ {h(ba)}
= {abab} ∩ {abab}
= {abab}
h(L1 ∩ L2) = h({ab} ∩ {ba})
= h(∅)
= ∅
Por outro lado, se w ∈ h(L1)∩h(L2), enta˜o w ∈ h(L1) e w ∈ h(L2). Logo, v ∈ L1∪L2
e h(v) = w ∈ h(L1 ∪ L2). Analogamente, Se w ∈ h(L2), enta˜o existe v ∈ L2 tal que
h(v) = w. Logo, v ∈ L1 ∪ L2 e h(v) = w ∈ h(L1 ∪ L2).
310
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
Assim esta igualdade na˜o e´ verdadeira.
(3c) h(Ln) = h(L)n
Resposta: Demonstraremos por induc¸a˜o em n que esta igualdade e´ correta.
Base da Induc¸a˜o: Se n = 0, enta˜o Ln = L0 = {λ}. Logo,
h(L0) = h({λ})
= {h(λ)}
= {λ}
= h({λ})0
Hipo´tese Indutiva: h(Li) = h(L)i.
Passo Indutivo:
h(Li+1) = h(LiL)
= h(Li)h(L)
= h(L)ih(L)
= h(L)i+1
Logo, podemos concluir que h(Ln) = h(L)n.
(3d) h(L∗) = h(L)∗
Resposta: w ∈ h(L∗) se, e somente se, existe v ∈ L∗ tal que w = h(v). Por definic¸a˜o
de fecho estrela, v ∈ L∗ se, e somente se, v ∈ Ln, para algum inteiro na˜o negativo
n. v ∈ Ln se, e somente se, w ∈ h(Ln). Pelo item anterior temos que w ∈ h(Ln) se,
e somente se, w ∈ h(L)n. Como, w ∈ h(L)n se, e somente se, w ∈ h(L)∗, podemos
concluir que h(L∗) = h(L)∗.
(3e) h(LR) = h(L)R
Resposta: Esta igualdade e´ incorreta, pois se L = {ab} e h(a) = aab e h(b) = bba,
enta˜o
h(LR) = h({ab}R)
= h({ba})
= bbaaab
h(L)R = h({ab})R
= (aabbba)R
= abbbaa
Logo, neste caso, h(LR) 6= h(L)R
(3f) h(L) = h(L)
Resposta: Esta igualdade e´ incorreta, pois se L = {ab} e h(a) = a e h(b) = a,
enta˜o
h(L) = h({a, b}∗ − {ab})
= {a}∗
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
311
A.4. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 4
h(L) = h({ab})
= {aa}
= {a, b}∗ − {aa}
Logo, neste caso h(L) 6= h(L)
4. Na prova do teorema 4.1.8, mostre que h(r) e´ uma expressa˜o regular. Enta˜o, mostre que
h(r) denota h(L).
Resposta: Provaremos por induc¸a˜o em r que h(r) e´ uma expressa˜o regular.
Base da Induc¸a˜o: Se r e´ uma expressa˜o regular primitiva, isto e´, r = λ, r = ∅ ou r = a
para algum a ∈ Σ1, enta˜o h(r) ou e´ λ, ou e´ ∅ ou e´ uma cadeia w ∈ Σ2, respectivamente,
em todos os casos h(r) e´ um expressa˜o regular.
Hipo´teses Indutiva: Assuma que r1 e r2 sa˜o expresso˜es regulares tais que h(r1) e h(r2)
tambe´m sa˜o expresso˜es regulares.
Passo Indutivo: Se r = r1 + r2, enta˜o
h(r) = h(r1 + r2)
= h(r1) + h(r2)
que e´ uma expressa˜o regular.
Se r = r1r2, enta˜o
h(r) = h(r1r2)
= h(r1)h(r2)
que e´ uma expressa˜o regular.
Se r = r∗1, enta˜o
h(r) = h(r∗1)
= h(r1)
∗
que e´ uma expressa˜o regular.
Assim podemos concluir que h(r) e´ uma expressa˜o regular sempre que r e´ uma expressa˜o
regular.
Por outro lado, devemos mostrar que h(r) denota h(L). Isto implica em mostrar que se
v ∈ L(h(r)), enta˜o v = h(w) para algum w ∈ L(r) e vice-versa, isto e´ que se w ∈ L(r)
enta˜o h(w) ∈ L(h(r)). Mas isto equivale a mostrar que L(h(r)) = h(L(r)). Faremos isto
por induc¸a˜o na complexidade da expressa˜o regular r.
Base da Induc¸a˜o: Seja r e´ uma expressa˜o regular primitiva.
Se r e´ λ enta˜o
312
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
L(h(λ)) = L(λ)
= {λ}
= {h(λ)}
= h({λ})
= h(L(λ)).
Se r e´ ∅ enta˜o
L(h(∅)) = L(∅)
= ∅
= h(∅)
= h(L(∅)).
Se r e´ um a ∈ Σ1 enta˜o L(r) = {a} e portanto
L(h(a)) = {h(a)}
= h({a})
= h(L(a)).
Logo, L(h(r)) = h(L(r)) quando r e´ uma expressa˜o regular primitiva.
Hipo´teses Indutiva: Assuma que r1 e r2 sa˜o expresso˜es regulares tais que L(h(r1)) =
h(L(r1)) e L(h(r2)) = h(L(r2)).
Passo Indutivo: Se r = r1 + r2, enta˜o
L(h(r)) = L(h(r1 + r2))
= L(h(r1) + h(r2))
= L(h(r1)) ∪ L(h(r2))
= h(L(r1)) ∪ h(L(r2))
= h(L(r1) ∪ L(r2))
= h(L(r1 + r2)).
Se r = r1r2, enta˜o
L(h(r)) = L(h(r1r2))
= L(h(r1)h(r2))
= L(h(r1))L(h(r2))
= h(L(r1))h(L(r2))
= h(L(r1)L(r2))
= h(L(r1r2)).
Se r = r∗1, enta˜o
L(h(r)) = L(h(r∗1))
= L(h(r1)
∗)
= L(h(r1))
∗
= h(L(r1))
∗
= h(L(r1)
∗).
Logo, podemos concluir que L(h(r)) = h(L(r)) para qualquer expressa˜o regular r.
5. Mostre que a famı´lia das linguagens regulares e´ fechada sobre unia˜o finita e intersecc¸a˜o
finita, isto e´, se L1, L2, . . . ,Ln sa˜o linguagens regulares enta˜o
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
313
A.4. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 4
n⋃
i=1
Li e
n⋂
i=1
Li
tambe´m sa˜o.
Resposta: Provaremos por induc¸a˜o em n o caso da unia˜o finita.
Base da Induc¸a˜o: Se n = 1, enta˜o
⋃n
i=1Li =
⋃1
i=1 Li = L1. Que claramente e´ regular.
Hipo´teses Indutiva: Assuma que
⋃n
i=1Li e´ regular.
Passo Indutivo: Provaremos que
⋃n+1
i=1 Li e´ regular. Como
n+1⋃
i=1
Li = (
n⋃
i=1
Li) ∪ Ln+1
enta˜o
⋃n+1
i=1 Li e´ uma unia˜o de duas linguagens regulares. Logo, pelo teorema 4.1.1,⋃n+1
i=1 Li e´ uma linguagem regular.
6. Sejam L1 e L2 duas linguagens sobre os alfabetos Σ1 e Σ2, respectivamente. O NEM de
duas linguagens e´
NEM(L1,L2) = {w ∈ (Σ1 ∪ Σ2)∗ / w 6∈ L1 e w 6∈ L2}.
Mostre que a famı´lia das linguagens regulares e´ fechada sobre NEM.
Resposta: Primeiro mostraremos passo a passo que NEM(L1,L2) = L1 ∪ L2.
NEM(L1,L2) = {w ∈ (Σ1 ∪ Σ2)∗ / w 6∈ L1 e w 6∈ L2}
= {w ∈ (Σ1 ∪ Σ2)∗ / ¬(w ∈ L1) e ¬(w ∈ L2)}
= {w ∈ (Σ1 ∪ Σ2)∗ / ¬(w ∈ L1 ou w ∈ L2)}
= {w ∈ (Σ1 ∪ Σ2)∗ / w ∈ L1 ou w ∈ L2}
= {w ∈ (Σ1 ∪ Σ2)∗ / w ∈ L1} ∪ {w ∈ (Σ1 ∪ Σ2)∗ / w ∈ L2}
= L1 ∪ L2
Como ja´ foi provado que as linguagem regulares sa˜o fechadas sobre complementoe unia˜o,
podemos concluir que se L1 e L2 sa˜o linguagens regulares enta˜o NEM(L1,L2) tambe´m e´
uma linguagem regular.
7 Mostre que as linguagens regulares sa˜o fechadas sobre a unia˜o disjunta, onde a unia˜o disjunta
de dois conjuntos (linguagens) L1 e L2 e´ definida por
L1 unionmulti L2 = {w0/ w ∈ L1} ∪ {w1/ w ∈ L2}
314
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
Resposta:
L1 unionmulti L2 = {w0/ w ∈ L1} ∪ {w1/ w ∈ L2}
= {w / w ∈ L1}{0} ∪ {w / w ∈ L2}{1}
= L1{0} unionmulti L2{1}
Como {0} e {1} sa˜o trivialmente linguagens regulares, e a classe das linguagens regulares
sa˜o fechadas sobre unia˜o e concatenac¸a˜o, temos que se L1 e L2 sa˜o linguagens regulares
enta˜o sua unia˜o disjunta, isto e´ L1 unionmulti L2, tambe´m e´ uma linguagem regular.
10. Seja L uma linguagem sobre um alfabeto Σ. Conforme visto no cap´ıtulo 1, a linguagem de
sufixos de L, denotada por LS , e´ definida como
LS = {w ∈ Σ∗ / vw ∈ L para algum v ∈ Σ∗}.
Demonstre que a classe das linguagens regulares e´ fechada sobre sufixos.
Resposta: Primeiro mostraremos que para qualquer linguagem L (regular ou na˜o), LS =
((LR)P )R, onde LR e´ linguagem reversa de L e LP e´ a linguagem de prefixos de L.
LS = {w ∈ Σ∗ / vw ∈ L para algum v ∈ Σ∗}
= {w ∈ Σ∗ / ((vw)R)R ∈ L para algum v ∈ Σ∗}
= {w ∈ Σ∗ / (wRvR)R ∈ L para algum v ∈ Σ∗}
= {w ∈ Σ∗ / wRvR ∈ LR para algum v ∈ Σ∗}
= {wR ∈ Σ∗ / wRvR ∈ LR para algum v ∈ Σ∗}R
= {w ∈ Σ∗ / wv ∈ LR para algum v ∈ Σ∗}R
= ((LR)P )R
Como a classe das linguagens regulares e´ fechada sobre prefixos e reversa, enta˜o podemos
concluir que se L e´ regular enta˜o LS tambe´m e´ regular.
13. Sejam L1 e L2 linguagens sobre alfabetos Σ1 e Σ2, respectivamente. Defina o operador ∧2
por
L1 ∧2 L2 = {uv/ u ∈ L1 ∪ L2 e v ∈ (Σ1 ∪ Σ2)∗}
Mostre que as linguagens regulares sa˜o fechadas sobre a operac¸a˜o ∧2 entre linguagens.
Resposta: Sejam G1 = 〈V1,Σ1, S1, P1〉 e G2 = 〈V2,Σ2, S2, P2〉 duas grama´ticas lineares
a` direita tais que L(G1) = L1 e L(G2) = L2. Seja X,S 6∈ V1 ∪ V2. Sem perca de
generalidade podemos considerar que V1 ∩ V2 = ∅. Claramente, a grama´tica G1 ∧2 G2 =
〈V1 ∪ V2 ∪ {S,X},Σ1 ∪ Σ2, S, P1 ∧X P2〉 onde
P1 ∧X P2 = {A −→ x ∈ P1 ∪ P2/ x 6∈ (Σ1 ∪ Σ2)∗} ∪ {A −→ xX/ A −→ x ∈ P1 ∪ P2 e
x ∈ (Σ1 ∪ Σ2)∗} ∪ {S −→ S1, S −→ S2} ∪ {X −→ aX/ a ∈ Σ1 ∪ Σ2} ∪ {X −→ λ}, e´ tal
que L(G1 ∧2 G2) = L(G1) ∧2 L(G2) = L1 ∧2 L2.
Por exemplo, se P1 consistir das seguintes produc¸o˜es:
S1 −→ aaS1 | bA
A −→ bbA | aaS1 | λ
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
315
A.4. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 4
e P2 consistir das seguintes produc¸o˜es:
S2 −→ aS2 | bS2 | abB
B −→ baB | C
C −→ ccC | cc
Enta˜o P1 ∧X P2 consistiria das seguintes produc¸o˜es:
S −→ S1 | S2
S1 −→ aaS1 | bA
A −→ bbA | aaS1 | X
S2 −→ aS2 | bS2 | abB
B −→ baB | C
C −→ ccC | ccX
X −→ aX | bX | cX | λ
17. Mostre que existe um algoritmo para determinar se L1 ⊆ L2, para qualquer linguagem
regular L1 e L2.
Resposta: Observe que em conjuntos A ⊆ B se e somente se B ∩ A = ∅. Como as
linguagens regulares sa˜o fechadas sobre complemento e intersecc¸a˜o, enta˜o L2 ∩ L1 e´ uma
linguagem regular. De fato seria poss´ıvel construir algoritmicamente um afd que reco-
nhec¸a essa linguagem baseada em afd’s que reconhecem L1 e L2. Agora aplicamos o
algoritmo para detectar se um afd reconhece uma linguagem vazia ou na˜o‘ao afd que
reconhece L2 ∩ L1. Se tivermos como resposta“sim” enta˜o L1 ⊆ L2 e caso contra´rio
L1 6⊆ L2.
19. Seja a tabela 4.1. A primeira coluna representa os ro´tulos de cada fila na tabela enquanto a
primeira fila representa os ro´tulos de cada coluna na tabela. Para cada x, y ∈ Σ = {a, b, c}
denote por T (x, y) o conteu´do da tabela para a posic¸a˜o (x, y). Seja a seguinte func¸a˜o
A : Σ+ → Σ definida por
• A(a) = a, para cada a ∈ Σ e
• A(wa) = T (A(w), a), para cada w ∈ Σ+ e a ∈ Σ.
Demonstre que a seguinte linguagem e´ regular:
L = {w ∈ Σ+/A(w) = A(wR)}
Resposta: Primeiro devemos entender bem o problema. A notac¸a˜o T (b, a) e´ o conteu´do
da tabela 4.1 na posic¸a˜o da linha b com a coluna a e portanto T (b, a) = c, ja´ T (a, b) = a.
Assim,
316
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
A(aababcc) = T (A(aababc), c)
= T (T (A(aabab), c), c)
...
= T (T (T (T (T (T (a, a), b), a), b), c), c)
= T (T (T (T (T (a, b), a), b), c), c)
= T (T (T (T (a, a), b), c), c)
= T (T (T (a, b), c), c)
= T (T (a, c), c)
= T (c, c)
= a
Por outro lado,
A((aababcc)R) = A(ccbabaa)
= T (A(ccbaba), a)
= T (T (A(ccbab), a), a)
...
= T (T (T (T (T (T (c, c), b), a), b), a), a)
= T (T (T (T (T (a, b), a), b), a), a)
= T (T (T (T (a, a), b), a), a)
= T (T (T (a, b), a), a)
= T (T (a, a), a)
= T (a, a)
= a
Portanto, A(aababcc) = A(ccbabaa) o que implica que aababcc ∈ L.
Como, trivialmente, para todo pal´ındromo w temos que A(w) = A(WR), enta˜o esta lin-
guagem contem propriamente os pal´ındromos e portanto e´ infinita. Observe que o lema
do bombeamento na˜o pode ser usado para provar que L e´ regular, pois ele so garante que
L for regular enta˜o satisfaz as condic¸o˜es, ma so fato de satisfazer as condic¸o˜es na˜o implica
em que seja regular.
Certamente esta linguagem na˜o e´ fa´cil de descrever sem ter que recorrer a` tabela associativa
por tanto a missa˜o de achar um autoˆmato finito para esta linguagem de forma direta e´
na˜o trivial. Pore´m, aqui so´ faremos uma prova de que existe tal autoˆmato finito. Sejam
os afd da figura A.39. Claramente, eles reconhecem as seguintes linguagens
• La = {w ∈ {a, b, c}/A(w) = A(wR) = a}
• Lb = {w ∈ {a, b, c}/A(w) = A(wR) = b}
• Lc = {w ∈ {a, b, c}/A(w) = A(wR) = b}
Por outro lado, e´ fa´cil ver que
L = (La ∩ LRa ) ∪ (Lb ∩ LRb ) ∪ (Lc ∩ LRc ).
Logo, como as linguagens regulares sa˜o fechadas sobre intersecc¸a˜o, unia˜o e reversa, enta˜o
L e´ uma linguagem regular.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
317
A.4. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 4
Esta prova so´ mostra a existeˆncia, mas a partir dela com algo de esforc¸o seria poss´ıvel
construir um afd que reconhec¸a L.
20. Seja Σ = {0, 1}. Mostre que e´ poss´ıvel aplicar o lema do bombeamento para as seguintes
linguagens regulares.
(20a) L = {w ∈ Σ∗ / 0110 e´ um prefixo de w}
Resposta: Seja m = 5, w ∈ L tal que |w| ≥ m, x = 0110, e y com z cadeias tais
que w = xyz e |y| = 1. Claramente |xy| = m. Claramente, para cada i = 0, 1, . . .,
temos que xyiz = 0110yiz ∈ L.
(20c) L = {w ∈ Σ∗ / w = u111v para algum u, v ∈ Σ∗}
Resposta: Seja m = 5, w ∈ L tal que |w| ≥ m. Como, w = u111v, se u = λ
enta˜o considere x = 111, e y com z cadeias tais que w = xyz e |y| = 1. Claramente
|xy| < m. Claramente, para cada i = 0, 1, . . ., temos que xyiz = 111yiz ∈ L. Se
u 6= λ, enta˜o considere x = λ, e y com z cadeias tais que w = xyz e |y| = 1. Assim,
a subcadeia 111 ocorre em z e portanto z = u111v para algum u, v ∈ Σ∗. Logo,
xyiz = yiz = yiu111v ∈ L.
21. Mostre que as linguagens sobre Σ = {a, b}, definidas a seguir, na˜o sa˜o regulares.
(21a) L = {w ∈ Σ∗/ Na(w) = Nb(w)}
Resposta: Para demonstrar que esta linguagens na˜o e´ regular, devemos mostrar
que ela na˜o satisfaz o lema do bombeamento, ou analogamente que ela satisfaz o
corola´rio do lema do bombeamento (corola´rio 4.3.6). Claramente L e´ infinita.
Seja m um inteiro positivo qualquer e w = ambm. Claramente w ∈ L. Seja, x, y e
z cadeias tais que w = xyz, |xy| ≤ m e |y| ≥ 1. Enta˜o, x = ai e y = aj (portanto
z = am−(i+j)bm), para algum i e j satisfazendo i+ j ≤ m e j ≥ 1. A cadeia xy2z 6∈ L,
pois xy2z = aiajajam−(i+j)bm = am+jbm. Como j ≥ 1, enta˜o m+ j > m e portanto
xy2z = am+jbm 6∈ L.(21b) L = {w ∈ Σ∗/ Na(w) 6= Nb(w)}
Resposta: Note que esta linguagem e´ o complemento da linguagem do exerc´ıcio
anterior (Exerc´ıcio 21a). Como linguagens regulares sa˜o fechadas sobre complemento
enta˜o se L = {w ∈ Σ∗/ Na(w) 6= Nb(w)} for regular a linguagem do Exerc´ıcio 21a
tambe´m seria regular, mas ja´ foi provado que ela na˜o e´ regular, chegando a uma
contradic¸a˜o. Logo, podemos concluir que L = {w ∈ Σ∗/ Na(w) 6= Nb(w)} na˜o e´
regular.
Para demonstrar que esta linguagens na˜o e´ regular usando diretamente o corola´rio
do lema do bombeamento (corola´rio 4.3.6) considere um inteiro positivo m qualquer
e w = amb2m!. Claramente w ∈ L. Seja, x, y e z cadeias tais que w = xyz, |xy| ≤ m
e |y| ≥ 1. Enta˜o, x = ai e y = aj (portanto z = am−(i+j)bm!+m), para algum i e j
318
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
satisfazendo i+ j ≤ m e j ≥ 1. Note que m!j +1 = 1+
∏j−1
k=1 k×
∏m
k′=j+1 k
′ e portanto
e´ um inteiro positivo. Mas,
xy
m!
j z = ai(aj)
m!
j
+1am−(i+j)bm!+m
= aiaj×(
m!
j
+1)am−(i+j)bm!+m
= aiam!+jam−(i+j)bm!+m
= ai+m!+j+m−(i+j)bm!+m
= am!+mbm!+m 6∈ L.
Portanto, L na˜o e´ uma linguagem regular.
(21d) L = {ambn/ m > n}
Resposta: Para demonstrar que esta linguagens na˜o e´ regular, devemos mostrar
que ela na˜o satisfaz o lema do bombeamento, ou analogamente que ela satisfaz o
corola´rio do lema do bombeamento (corola´rio 4.3.6). Claramente L e´ infinita.
Seja m um inteiro positivo qualquer e w = ambm−1. Claramente w ∈ L. Seja,
x, y e z cadeias tais que w = xyz, |xy| ≤ m e |y| ≥ 1. Enta˜o, x = ai e y = aj
(portanto z = am−(i+j)bm−1), para algum i e j satisfazendo i + j ≤ m e j ≥ 1. A
cadeia xy0z 6∈ L, pois xy0z = aiam−(i+j)bm−1 = am−jbm−1. Como j ≥ 1, enta˜o
m− j ≤ m− 1 e portanto xy0z = am−jbm−1 6∈ L.
(21e) L = {ambn/ m 6= n}
Resposta: Para demonstrar que esta linguagens na˜o e´ regular, devemos mostrar
que ela na˜o satisfaz o lema do bombeamento, ou analogamente que ela satisfaz o
corola´rio do lema do bombeamento (corola´rio 4.3.6). Claramente L e´ infinita.
Seja m um inteiro positivo qualquer e w = ambm!+m. Claramente w ∈ L. Seja, x, y
e z cadeias tais que w = xyz, |xy| ≤ m e |y| ≥ 1. Enta˜o, x = ai e y = aj (portanto
z = am−(i+j)bm!+m), para algum i e j satisfazendo i + j ≤ m e j ≥ 1. A cadeia
xy
m!
j
+1z 6∈ L, pois
xy
m!
j
+1z = aiaj
m!
j
+1
am−(i+j)bm!+m
= aiaj(
m!
j
+1)am−(i+j)bm!+m
= am−jam!+jbm!+m
= amam!bm!+m
= am!+mbm!+m.
23. Seja Σ = {a, b} e .̂ : Σ∗ → Σ∗ a operac¸a˜o definida recursivamente a seguir:
• λ̂ = λ
• ŵa = ŵaa
• ŵb = ŵbb
Mostre usando o lema do bombeamento que a linguagem L = {wŵ/ w ∈ Σ∗} na˜o e´ regular.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
319
A.4. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 4
Resposta: Para demonstrar que esta linguagens na˜o e´ regular, devemos mostrar que ela
na˜o satisfaz o lema do bombeamento, ou analogamente que ela satisfaz o corola´rio do lema
do bombeamento (corola´rio 4.3.6). Claramente L e´ infinita.
Seja m um inteiro positivo qualquer e w = amb. Claramente a cadeia wŵ = ambbma ∈ L.
Seja, x, y e z cadeias tais que wŵ = xyz, |xy| ≤ m e |y| ≥ 1. Enta˜o, x = ai e y = aj
(portanto z = am−(i+j)bbma), para algum i e j satisfazendo i + j ≤ m e j ≥ 1. A cadeia
xy2z 6∈ L, pois xy2z = aiajajam−(i+j)bbma = am+jbbma. Como j ≥ 1, enta˜o m+ j > m e
portanto âm+jb 6= bma. Logo, am+jbbma 6∈ L.
320
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
A.5 Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 5
3. Achar as grama´ticas livres do contexto para as seguintes linguagens (com m ≥ 0, n ≥ 0 e
k ≥ 0).
(3a) L = {anbm / n 6= m− 1},
Resposta: Observe que
L = {anbm / n 6= m− 1}
= {anbm / n > m− 1} ∪ {anbm / n < m− 1}
= {anbm / n ≥ m} ∪ {anbm / n+ 2 ≤ m}
= {anbm / n ≥ m} ∪ {anbkbb / n ≤ k}
Assim, L = L1 ∪ L2, onde L1 = {anbm / n ≥ m} e L2 = {anbkbb / n ≤ k}
Uma grama´tica livre do contexto que gera a linguagem L1 e´ a seguinte
S1 −→ aS1b | A
A −→ aA | λ
Por outro lado, uma grama´tica livre do contexto que gera a linguagem L2 e´ a seguinte
S2 −→ aS2b | B
B −→ bB | bb
A unia˜o destas duas linguagens se faz simplesmente (pois na˜o tem varia´veis em co-
mum) juntando ambas grama´ticas e adicionando uma nova varia´vel inicial e duas
produc¸o˜es comec¸ando dela, uma para S1 e a outra para S2. Assim, o resultado desta
junc¸a˜o e´ a grama´tica livre do contexto:
S −→ S1 | S2
S1 −→ aS1b | A
A −→ aA | λ
S2 −→ aS2b | B
Blra bB | bb
(3c) L = {anbm / n ≤ m+ 3},
Resposta:
S −→ aSb | A
A −→ Ab | aaa
(3e) L = {anbmck / n = m ou m ≤ k},
Resposta: Esta linguagem e´ a unia˜o das linguagem L1 e L2, onde L1 = {anbmck / n =
m} e L2 = {anbmck / m ≤ k}. Assim, uma grama´tica livre do contexto para esta
linguagem resulta da unia˜o das respectivas grama´ticas livres do contexto para L1 e
L2.
Uma grama´tica livre do contexto que gera L1 e´ a seguinte:
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
321
regivan
Realce
regivan
Realce
regivan
Texto digitado
| lambda
regivan
Texto digitado
regivan
Riscado
regivan
Texto digitado
| C
regivan
Texto digitado
C -> a | aa | aaa | lambda 
A.5. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 5
S1 −→ BC
B −→ aBb | λ
C −→ cC | λ
Uma grama´tica livre do contexto que gera L2 e´ a seguinte:
S2 −→ AD
A −→ aA | λ
D −→ bDc | E
E −→ cE | λ
Portanto, como ambas grama´ticas na˜o teˆm varia´veis em comum, uma grama´tica livre
do contexto que gera L1 ∪ L2, isto e´ L, e´ a seguinte:
S −→ S1 | S2
S1 −→ BC
B −→ aBb | λ
C −→ cC | λ
S2 −→ AD
A −→ aA | λ
D −→ bDc | E
E −→ cE | λ
(3g ) L = {anbmck / n = m ou m 6= k},
Resposta: Esta linguagem e´ a unia˜o das linguagens: L1 = {anbmck / n = m},
L2 = {anbmck / m < k} e L3 = {anbmck / m > k}. Uma grama´tica livre do contexto
para L1 foi dada no exerc´ıcio anterior, ja´ as grama´ticas livres do contexto de L2 e L3
sa˜o as seguintes:
S2 −→ AD
A −→ aA | λ
D −→ bDc | E
E −→ cE | c
S3 −→ AF
A −→ aA | λ
F −→ bFc | G
G −→ bG | b
Assim, juntando as treˆs grama´ticas resulta na seguinte grama´tica livre de contexto:
322
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
S −→ S1 | S2 | S3
S1 −→ BC
B −→ aBb | λ
C −→ cC | λ
S2 −→ AD
A −→ aA | λ
D −→ bDc | E
E −→ cE | c
S3 −→ AF
F −→ bFc | G
G −→ bG | b
(3i) L = {w ∈ {a, b}∗ / Na(w) e´ ı´mpar }
Resposta:
S −→ bS | aA
A −→ aS | bA | λ
(3k) L = {akbman / 2k = n+m},
Resposta:
S −→ aSaa | aAba | A
A −→ aAbb | λ
(3m) L = {akbman / m = 2(n+ k) + 1},
Resposta:
S −→ AbB
A −→ aAbb | λ
B −→ bbBa | λ
(3o) L = {akbmanbp / m = k ou n = p}
Resposta:
S −→ AB | BA
A −→ aAb | ab
B −→ aB | bC
C −→ bC | λ
4. Desenhe uma grama´tica livre de contexto que gere todas as expresso˜es regulares va´lidas sobre
o alfabeto {a, b}. Por exemplo deve permitir gerar as cadeias (a+ aa∗b)∗ + (λ+ aa)(bb)∗b
e (ab+ ba)∗(aa+ bb)∗.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
323
A.5. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 5
Resposta: A grama´tica deve gerar todas as expresso˜es regulares sobre o alfabeto {a, b}.
Assim, por exemplo, deve gerar as expresso˜es regulares a, ∅, a+b, (a+b)∗b e (aab+b)∗(a+λ).
Portanto o conjunto de s´ımbolos terminais da grama´tica deve conter todos os poss´ıveis
s´ımbolos usados numa expressa˜o regular sobre este alfabeto. Logo, o conjunto de s´ımbolos
terminais deveria ser: {a, b, λ, ∅, (, ),+, ·,∗ }, pore´m para na˜o confundir a cadeia vazia λnuma grama´tica livre do contexto com o s´ımbolo terminal λ, usaremos o s´ımbolo λ para
representar este u´ltimo. Por uma questa˜o de simplicidade a grama´tica se baseara´ na
definic¸a˜o original de expresso˜es regulares (definic¸a˜o 3.1.1) com uma u´nica abreviac¸a˜o: a
supressa˜o do s´ımbolo de concatenac¸a˜o “·”.
S −→ a | b | λ | ∅ | (S + S) | (S)∗ | SS
Observe que esta grama´tica permitiria expresso˜es regulares do tipo (aλ∅+ bb(∅)∗a)∗. Mas
observe que isto tambe´m e´ permitido pela definic¸a˜o 3.1.1. Caso nos quisermos coibir
expresso˜es regulares que possuam uma sub-expressa˜o regular da forma r1r2 com r1 sendo
λ ou ∅ e r2 na˜o, ou vice-versa, ter´ıamos que modificar a grama´tica livre do contexto para:
S −→ λ | ∅ | S1
S1 −→ a | b | (S + S) | (S)∗ | S1S1
Observe que isto na˜o diminui o poder de expressa˜o das expresso˜es regulares, pois L(rλ) =
L(r) e L(r∅) = L(∅).
5. Achar uma grama´tica livre do contexto para a linguagem
L = {anwwRbn / w ∈ {a, b}∗, n ≥ 1}
Resposta:
S −→ aSb | aAb
A −→ aAa | bAb | λ
6. Defina uma grama´tica livre do contexto para a linguagem de todas cadeias no alfabeto {a, b}
que na˜o sa˜o pal´ındromos. Isto e´, para a linguagem
L = {w ∈ {a, b}∗ / w 6= wR}
Resposta:
S −→ aSa | bSb | A
A −→ aBb | bBa
B −→ aB | bB | λ
7. Seja L = {anbn / n ≥ 0}
(7a) Mostre que L2 e´ livre do contexto.
324
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
Resposta: Antes devemos analisar quem e´ L2. L2 sa˜o todas as cadeias w tal que
w = uv e u ∈ L e v ∈ L, mas u e v na˜o precisam ser as mesmas cadeias, por tanto
u = anbn para algum n ≥ 0 e v = ambm para algum m ≥ 0. Assim,
L2 = {anbnambm / n ≥ 0 e m ≥ 0}
Uma grama´tica livre do contexto para esta linguagem e´ a seguinte:
S −→ AA
A −→ aAb | λ
8. Mostre uma a´rvore de derivac¸a˜o para a cadeia aabbbb, com a grama´tica
S −→ AB | λ,
A −→ aB,
B −→ Sb.
Deˆ uma descric¸a˜o da linguagem gerada por essa grama´tica.
Resposta: Uma a´rvore de derivac¸a˜o para a cadeia aabbbb e´ ilustrada na figura A.40.
A linguagem gerada por esta grama´tica livre do contexto consiste de todas as cadeias da
forma anb2n com n ≥ 0.
11. Mostre que a grama´tica seguinte e´ amb´ıgua
S −→ AB | aaB,
A −→ a | Aa,
B −→ b.
Resposta: Uma grama´tica e´ amb´ıgua se existem duas derivac¸o˜es mais a` esquerda para
uma mesma cadeia. Neste caso a cadeia aab a qual tem as seguintes derivac¸o˜es mais a`
esquerda:
1) S ⇒ AB ⇒ AaB ⇒ aaB ⇒ aab
2) S ⇒ aaB ⇒ aab
12. Construa uma grama´tica na˜o amb´ıgua, equivalente a` grama´tica do exerc´ıcio anterior.
Resposta: A Ambigu¨idade na grama´tica anterior so´ ocorre por causa da produc¸a˜o S −→
aaB, que so´ e´ usada para gerar a cadeia aab. Logo retirando esta produc¸a˜o da grama´tica,
como abaixo, obtemos uma grama´tica equivalente a` anterior mas na˜o amb´ıgua.
S −→ AB
A −→ a | Aa,
B −→ b.
14. Mostre que toda S-grama´tica e´ na˜o-amb´ıgua.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
325
A.5. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 5
Resposta: Seja G = 〈V, T, S, P 〉 uma S-grama´tica. Lembre que em S-grama´ticas todas
as produc¸o˜es teˆm a forma A −→ ax com a ∈ T e x ∈ V ∗. Se A −→ ax e A −→ ay sa˜o
produc¸o˜es em P , enta˜o necessariamente x = y.
Suponha que ela e´ amb´ıgua. Enta˜o existe uma cadeia, digamos a1 . . . an ∈ T ∗ com pelo
menos duas derivac¸o˜es mais a` esquerda. Observe que neste caso a varia´vel mais a` esquerda
e´ trocada, e portanto a cada etapa um u´nico s´ımbolo e´ gerado. Logo, duas derivac¸o˜es mais
a` esquerda realizam as seguintes etapas:
S ⇒ a1x1 ⇒ a1a2x2 ⇒ · · · ⇒ a1 . . . an−1xn ⇒ a1 . . . an (A.1)
e
S ⇒ a1y1 ⇒ a1a2y2 ⇒ · · · ⇒ a1 . . . an−1yn ⇒ a1 . . . an (A.2)
com xi, yi ∈ V +.
Mostraremos por induc¸a˜o que cada forma sentencial a1 . . . akxk = a1 . . . akyk.
Base da Induc¸a˜o: k = 1. Se S ⇒ a1x1 e S ⇒ a1y1 enta˜o S −→ a1x1 e S −→ a1y1
esta˜o ambas em P . Mas, pela S-condic¸a˜o x1 = y1.
Hipo´teses Indutiva: Suponha que para algum k < n, xk = yk.
Passo Indutivo: Seja A a varia´vel mais a` esquerda de xk (e pela hipo´tese indutiva
tambe´m de yk). Como a1 . . . akxk ⇒ a1 . . . akak+1xk+1 e a1 . . . akyk ⇒ a1 . . . akak+1yk+1,
enta˜o A −→ ak+1xk+1 e A −→ ak+1yk+1. Logo pela S-condic¸a˜o, xk+1 = yk+1
Assim, para qualquer k < n temos que xk = yk e por conseguinte a derivac¸a˜o (A.1) e´ igual
a` derivac¸a˜o (A.2).
16. Use o teorema 5.5.3, para remover produc¸o˜es esquerda-recursivas nas grama´ticas
(16a) S −→ abS | SS | λ
Resposta: A u´nica produc¸a˜o esquerda-recursiva e´ S −→ SS, portanto, pelo teo-
rema 5.5.3, na grama´tica acima eliminamos essa produc¸a˜o e em seu lugar colocamos
as produc¸o˜es S −→ abSZ, S −→ Z, Z −→ S e Z −→ SZ, ou seja obtemos a seguinte
grama´tica:
S −→ abS | abSZ | λ | Z
Z −→ S | SZ
(16c) S −→ aZ | SbS,
Z −→ aZb | λ.
326
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
Resposta: So´ temos uma produc¸a˜o esquerda-recursiva. Realizando as substituic¸o˜es
apontadas pelo teorema 5.5.3 a` grama´tica, obtemos a seguinte grama´tica livre do
contexto:
S −→ aZ | aZY
Z −→ aZb | λ
Y −→ Sb | SbY
19. Elimine as λ-produc¸o˜es de
S −→ AaB | aCaB,
A −→ aBa | λ | B,
B −→ bbA | λ,
C −→ bbbC | AB.
Resposta: Claramente A e B sa˜o anula´veis. Como ha´ uma produc¸a˜o C −→ AB, enta˜o
C tambe´m e´ anula´vel. Logo o conjunto VN de todas as varia´veis anula´veis na grama´tica
e´ {A,B,C}. Agora colocamos todas produc¸o˜es que na˜o sa˜o λ-produc¸o˜es e adicionamos
aquelas substituindo em todas as combinac¸o˜es poss´ıveis as varia´veis A e B por λ, isto
resulta na seguinte grama´tica:
S −→ AaB | aCaB | Aa | aB | a | aCa | aaB | aa,
A −→ aBa | B | aa,
B −→ bbA | bb,
C −→ bbbC | bbb | AB | A | B.
21. Elimine produc¸o˜es unita´rias, λ-produc¸o˜es, produc¸o˜es inu´teis e produc¸o˜es esquerda-recursivas
nas seguintes grama´ticas livres do contexto:
(21d) S −→ AbAaBa | ABSa | aAAbC,
A −→ aAa | λ,
B −→ bbB | BCa | aD | λ,
C −→ cAE | aCCa,
D −→ E | F ,
E −→ aCb,
F −→ FaF | FSaA,
G −→ SaH,
H −→ aA | λ.
Resposta: Primeiro eliminaremos produc¸o˜es inu´teis usando o algoritmo na prova
do teorema 5.5.7. Este e´ constitu´ıdo de duas partes. Da primeira parte obtemos as
seguintes produc¸o˜es:
S −→ AbAaBa | ABSa,
A −→ aAa | λ,
B −→ bbB | λ,
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
327
A.5. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 5
G −→ SaH,
H −→ aA | λ.
Agora aplicando a segunda parte obtemos:
S −→ AbAaBa | ABSa,
A −→ aAa | λ,
B −→ bbB | λ,
Agora eliminaremos λ-produc¸o˜es e aplicamos o algoritmo do teorema 5.5.10, resul-
tando na grama´tica:
S −→ AbAaBa | ABSa | bAaBa | AbaBa | AbAaa | baBa | bAaa | Abaa |
baa | ASa | BSa | Sa,
A −→ aAa | aa,
B −→ bbB | bb,
Como na˜o ha´ produc¸o˜es unita´rias passamos a remover produc¸o˜es esquerda recursivas
usando o algoritmo do teorema 5.5.3. Note que so´ existe uma produc¸a˜o esquerda
recursiva: S −→ Sa. A remoc¸a˜o resulta na seguinte grama´tica:
S −→ AbAaBa | ABSa | bAaBa | AbaBa | AbAaa | baBa | bAaa | Abaa |
baa | ASa | BSa | AbAaBaZ | ABSaZ | bAaBaZ | AbaBaZ |
AbAaaZ | baBaZ | bAaaZ | AbaaZ | baaZ | ASaZ | BSaZ,
Z −→ a | aZ,
A −→ aAa | aa,
B −→ bbB | bb,
23. Converter as seguintes grama´ticas a` forma normal de Chomsky
(23a) S −→ aSb | ab
Resposta: Para transformar esta grama´tica livre do contexto numa grama´tica
tambe´m livre do contexto equivalente na forma normal de Chomsky, a demonstrac¸a˜o
do teorema 5.6.2, sugere que primeiro se devem eliminar as produc¸o˜es unita´rias e
λ-produc¸o˜es, que neste caso na˜o ha´, para depois seguir as seguintes duas etapas.
Etapa 1: Devemos substituircada s´ımbolo terminal, por exemplo a, nas produc¸o˜es
por novas varia´veis, Ba, e depois introduzir as produc¸o˜es Ba −→ a. Assim, aplicando
esta etapa, a grama´tica acima se transforma na grama´tica:
S −→ BaSBb | BaBb
Ba −→ a
Bb −→ b
Etapa 2: Devemos substituir as produc¸o˜es que tenham mais de duas varia´veis (su-
ponha A −→ X1 . . . Xn) por duas produc¸o˜es, uma com duas varia´veis (A −→ Y1Xn)
e a outra com n−1 varia´veis (Y −→ X1 . . . Xn), onde a varia´vel Y e´ nova. Repetimos
este processo ate´ so´ ficarem produc¸o˜es com duas varia´veis. Como neste caso temos
uma u´nica produc¸a˜o com mais de duas varia´veis a` direita (S −→ BaSBb), esta etapa
so´ tem um passo. Assim, a grama´tica resultante dessa etapa e´:
328
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
regivan
Realce
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
S −→ Y Bb | BaBb
Y −→ BaS
Ba −→ a
Bb −→ b
a qual esta´ na forma normal de Chomsky.
(23c) S −→ abAB,
A −→ bAB | λ,
B −→ BAa | A | λ.
Resposta: Novamente seguiremos o algoritmo da demonstrac¸a˜o do teorema 5.6.2
para transformar a grama´tica acima numa equivalente na forma normal de Chomsky.
Neste caso primeiro temos que eliminar produc¸o˜es unita´rias e λ-produc¸o˜es. Elimi-
nando λ-produc¸o˜es obtemos a seguinte grama´tica:
S −→ abAB | abB | abA | ab
A −→ bAB | bB | b
B −→ BAa | A | Aa | Ba | a
Eliminando agora produc¸o˜es unita´rias obtemos a seguinte grama´tica:
S −→ abAB | abB | abA | ab
A −→ bAB | bB | b
B −→ BAa | bAB | bB | b | Aa | Ba | a
Seguindo a etapa 1, obtemos a seguinte grama´tica:
S −→ BaBbAB | BaBbB | BaBbA | BaBb
A −→ BbAB | BbB | b
B −→ BABa | BbAB | BbB | b | ABa | BBa | a
Ba −→ a
Bb −→ b
Seguindo a etapa 2 obtemos a seguinte grama´tica, faremos isto introduzindo a menor
quantidade de varia´veis poss´ıveis, ou seja usaremos o bom senso em vez do “algoritmo”
da demonstrac¸a˜o do teorema 5.6.2:
S −→ Y1Y2 | Y1B | Y1A | BaBb
Y1 −→ BaBb
Y2 −→ AB
A −→ BbY2 | BbB | b
B −→ Y3Ba | BbY2 | BbB | b | ABa | BBa | a
Y3 −→ BA
Ba −→ a
Bb −→ b
25. Converter as seguintes grama´ticas na forma normal de Greibach.
(25a) S −→ aaS | SS | aa.
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
329
A.5. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 5
Resposta: A demonstrac¸a˜o do teorema 5.6.6 define 4 etapas para transformar
uma grama´tica livre do contexto numa equivalente na forma normal de Greibach.
Seguiremos cada uma dessas etapas.
Etapa 1: Transformaremos primeiro a` forma normal de Chomsky. Na primeira
etapa obtemos a seguinte grama´tica:
S −→ BaBaS | SS | BaBa
Ba −→ a
Na segunda etapa obtemos a forma normal de Chomsky:
S −→ Y S | SS | BaBa
Y −→ BaBa
Ba −→ a
Etapa 2: Rotulando as varia´veis obtemos a seguinte grama´tica:
A1 −→ A2A1 | A1A1 | A3A3
A2 −→ A3A3
A3 −→ a
Etapa 3: Usamos os teoremas 5.5.1 e 5.5.3 para deixar todas as produc¸o˜es na
forma prevista nesta etapa. Como resultado obtemos a seguinte grama´tica:
A1 −→ A2A1 | A2A1Z1 | A3A3 | A3A3Z1
Z1 −→ A1A1 | A1A1Z1
A2 −→ A3A3
A3 −→ a
Etapa 4: Usamos o teorema 5.5.1 para transformar a grama´tica resultante da etapa
anterior numa na forma normal de Greibach. Faremos isto passo a passo. Primeiro
substituiremos a ocorreˆncia mais a` esquerda de A3 no lado direito da produc¸a˜o A2 −→
A3A3 (Observe que a u´nica produc¸a˜o tendo A3 no lado esquerdo satisfaz as condic¸o˜es
de Greibach), isto resulta na seguinte grama´tica:
A1 −→ A2A1 | A2A1Z1 | A3A3 | A3A3Z1
Z1 −→ A1A1 | A1A1Z1
A2 −→ aA3
A3 −→ a
Agora todas as produc¸o˜es com A2 ou A3 no lado esquerdo esta˜o na forma normal de
Greibach. Agora substituiremos a varia´vel mais a` esquerda de cada produc¸a˜o tendo
A1 no lado esquerdo (observe que por se encontrar nesta etapa, essa varia´vel so´ pode
ser A2 ou A3). Como resultado obtemos a seguinte grama´tica:
330
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
A1 −→ aA3A1 | aA3A1Z1 | aA3 | aA3Z1
Z1 −→ A1A1 | A1A1Z1
A2 −→ aA3
A3 −→ a
Finalmente fazemos o mesmo com as produc¸o˜es cujo lado esquerdo seja Z1. Observe
que neste caso, a varia´vel mais a` esquerda do lado direito da produc¸a˜o sempre sera´
da forma Ai, como todos os Ai’s esta˜o na forma normal de Greibach esta substituic¸a˜o
acarretara´ em que as produc¸o˜es com Z1 no lado esquerdo tambe´m estejam na forma
normal de Greibach. Isto resulta na seguinte grama´tica:
A1 −→ aA3A1 | aA3A1Z1 | aA3 | aA3Z1
Z1 −→ aA3A1A1 | aA3A1Z1A1 | aA3A1 | aA3Z1A1
aA3A1A1Z1 | aA3A1Z1A1Z1 | aA3A1Z1 | aA3Z1A1Z1
A2 −→ aA3
A3 −→ a
(25c) S −→ aA | Bbb,
A −→ aBa | aa,
B −→ Abb | Cab,
C −→ Aba | Bab | aba
Resposta: A demonstrac¸a˜o do teorema 5.6.6 define 4 etapas para transformar
uma grama´tica livre do contexto numa equivalente na forma normal de Greibach.
Seguiremos cada uma dessas etapas.
Etapa 1: Transformaremos primeiro a` forma normal de Chomsky. Na primeira
etapa obtemos a seguinte grama´tica:
Forma normal Pre-Chomsky: Por simplicidade usaremos nomes de varia´veis X e Y
em vez de Ba e Bb respectivamente.
S −→ XA | BY Y ,
A −→ XBX | XX,
B −→ AY Y | CXY ,
C −→ AYX | BXY | XYX
X −→ a,
Y −→ b.
Forma normal de Chomsky:
S −→ XA | BD,
A −→ XE | XX,
B −→ AD | CF ,
C −→ AG | BF | FX
D −→ Y Y ,
E −→ BX,
F −→ XY ,
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
331
A.5. Soluc¸o˜es de Exerc´ıcios do Cap´ıtulo 5
G −→ Y X,
X −→ a,
Y −→ b.
Etapa 2: Antes de rotular as varia´veis, para diminuir passos nas etapas posteri-
ores, e´ aconselha´vel analisar qual a melhor rotulac¸a˜o. Neste caso, e´ bom olhar o
grafo de dependeˆncia entre as varia´veis (considerando so´ as do lado esquerdo de uma
produc¸a˜o e a mais a` esquerda do lado direito da mesma produc¸a˜o). A figura A.41
mostra tal grafo de dependeˆncia. A ordem entre B e C na˜o e´ fundamental, pois eles
esta˜o entrelac¸ados. Porem como B tem menor produc¸o˜es que C consideraremos B
precedendo C. Assim, a ordem considerada e´: S,E,B,C,A,D,F,G,X, Y e rotulando
essas varia´veis nessa ordem obtemos a seguinte grama´tica:
V1 −→ V9V5 | V3V6,
V5 −→ V9V2 | V9V9,
V3 −→ V5V6 | V4V7,
V4 −→ V5V8 | V3V7 | V7V9
V6 −→ V10V10,
V2 −→ V3V9,
V7 −→ V9V10,
V8 −→ V10V9,
V9 −→ a,
V10 −→ b.
Etapa 3: Usamos os teoremas 5.5.1 e 5.5.3 para deixar todas as produc¸o˜es na
forma prevista nesta etapa. Primeiro observe que a u´nica produc¸a˜o que na˜o satisfaz
as condic¸o˜es desta etapaV4 −→ V3V7. Assim, aplicando o teorema 5.5.1 obtemos a
seguinte grama´tica:
V1 −→ V9V5 | V3V6,
V5 −→ V9V2 | V9V9,
V3 −→ V5V6 | V4V7,
V4 −→ V5V8 | V5V6V7 | V4V7V7 | V7V9
V6 −→ V10V10,
V2 −→ V3V9,
V7 −→ V9V10,
V8 −→ V10V9,
V9 −→ a,
V10 −→ b.
Agora temos uma produc¸a˜o esquerda recursiva (V4 −→ V4V7V7). Eliminamos esta
usando o teorema 5.5.3. Isto resulta na seguinte grama´tica:
V1 −→ V9V5 | V3V6,
V5 −→ V9V2 | V9V9,
V3 −→ V5V6 | V4V7,
332
Introduc¸a˜o a` Teoria da Computac¸a˜o:
Linguagens Formais, autoˆmatos e Computabilidade
Cap´ıtulo A. Soluc¸o˜es de Alguns dos Exerc´ıcios Propostos
V4 −→ V5V8 | V5V6V7 | V7V9 | V5V8Z1 | V5V6V7Z1 | V7V9Z1
Z1 −→ V7V7 | V7V7Z1
V6 −→ V10V10,
V2 −→ V3V9,
V7 −→ V9V10,
V8 −→ V10V9,
V9 −→ a,
V10 −→ b.
Etapa 4: Usamos o teorema 5.5.1 para transformar a grama´tica resultante da
etapa anterior numa na forma normal de Greibach. Observe que V9 e V10 esta˜o na
forma normal de Greibach e que as produc¸o˜es de V5 a V8 comec¸am com uma delas.
Por tanto faremos todas estas substituic¸o˜es de uma u´nica vez:
V1 −→ V9V5 | V3V6,
V5 −→ aV2 | aV9,
V3 −→ V5V6 | V4V7,
V4 −→ V5V8 | V5V6V7 | V7V9 | V5V8Z1 | V5V6V7Z1 | V7V9Z1
Z1 −→ V7V7 | V7V7Z1
V6 −→ bV10,
V2 −→ V3V9,
V7 −→ aV10,
V8 −→ bV9,
V9 −→ a,
V10 −→ b.
Agora substituiremos todas