Gabarito Lista Exercícios 2

Prévia do material em texto

Instituto de Matema´tica
Gabarito da 2a Lista de Teoria da Computac¸a˜o
Professora: Maria Alice Silveira de Brito
Data: 22/11/2011
1. Mostre que:
(a) cada linguagem abaixo na˜o e´ regular,
(b) cada linguagem abaixo e´ livre de contexto,
(c) Apresente um autoˆmato de pilha determin´ıstico que as reconhec¸a, por estado final e pilha vazia.
L1 = {a
ibj : i = j, i ≥ 1, j ≥ 1} L2 = {a
ibj : 2i = j, i ≥ 1, j ≥ 1}
Se L1 e´ uma linguagem regular, enta˜o L1 satisfaz o teorema
do bombeamento para linguagens regulares.
Theorem 1 Seja L uma linguagem regular. Enta˜o, existe
um natural n0 tal que qualquer cadeia w de L com compri-
mento |w| ≥ n0, w pode ser decomposta em treˆs cadeias x, y
e z(w = xyz) de forma que |xy| ≤ n0, y 6= ε e para qualquer
t ≥ 1, xytz ∈ L.
Enta˜o suponha por contradic¸a˜o que L seja regular. Con-
sidere n0 como no teorema e a palavra temos uma palavra
w = an0 bn0 de L. Enta˜o pelo Teorema do bombeamento
w = an0 bn0 = xyz com |xy| ≤ n0.
Enta˜o como y 6= ε, y = at, t > 0, e assim xy2z = an0+tbn0 ,
e portanto xy2z /∈ L.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRb
R → aRb|ε)
Seja A = (K = {q0, q1, q2, q3}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, ε, X) = (q3, �).
Enta˜o temos uma palavra aibj de L2, e supomos por con-
tradic¸a˜o que L1 e´ regular e que |a
ibj | ≥ n. Enta˜o pelo Teo-
rema do bombeamento aibj = uvw como no teorema. Qual
seria a opc¸a˜o para v:
(a) Se v so´ tem a′s, enta˜o o nu´mero de a′s de uviw e´
diferente de
j
2
b′s, se t ≥ 2, e assim uvtw /∈ L2.
(b) Se v so´ tem b′s, enta˜o o nu´mero de b′s de uviw e´ difer-
ente de 2i a′s, se t ≥ 2 e assim uvtw /∈ L2.
(c) Se v tem a′s e b′s, enta˜o uviw tem um b antes de um
a com t ≥ 2, e assim uvtw /∈ L2.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRbb
R → aRbb|ε)
Seja A = (K = {q0, q1, q2, q3}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, a, X) = (q1, AAX),
(q1, a, A) = (q1, AAA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, ε, X) = (q3, �).
L3 = {a
ibj : i ≤ j, i ≥ 1, j ≥ 1} L4 = {a
ibj : i ≥ j, i ≥ 1, j ≥ 1}
Consideramos aibj = uvw com i ≥ n para o teorema do
bombeamento.
Assim, como |uv| ≤ n, a opc¸a˜o para v seria somente bombear
a′ e enta˜o para k ≥ j temos que uvkw tem mais a’s do que
b’s e uvkw /∈ L3.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRb
R → Rb|aRb|ε)
Seja A = (K = {q0, q1, q2, q3, q4}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q4}), onde
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, b, X) = (q3, X),
(q3, b, X) = (q3, X),
(q2, ε, X) = (q4, �),
(q3, ε, X) = (q4, �).
Observamos que o Teorema do bombeamento tem uma versa˜o
fa´cil de provar que:
Theorem 2 Seja L uma linguagem regular. Enta˜o, existe um
natural n tal que qualquer cadeia z de L com comprimento maior
ou igual a n pode ser decomposta em treˆs cadeias u, v e w(z =
uvw) de forma que |uv| ≤ n ou |vw| ≤ n, v 6= ε e para qualquer
i ≥ 1, uviw ∈ L.
Consideramos aibj = uvw com j ≥ n.
Assim, se |vw| ≤ n, a opc¸a˜o para v seria somente bombear b′
e enta˜o para k ≥ i temos que uvkw tem mais b’s do que a’s e
uvkw /∈ L3.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRb
R → aR|aRb|ε)
Seja A = (K = {q0, q1}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, ε, A) = (q3, �),
(q3, ε, A) = (q3, �),
(q3, ε, X) = (q3, �),
(q2, ε, X) = (q3, �).
1
L5 = {a
ibj : i = j, i ≥ 0, j ≥ 0} L6 = {a
ibj : 2i = j, i ≥ 0, j ≥ 0}
Consideramos aibj = uvw com i ≥ n.
Assim, como |uv| ≤ n, a opc¸a˜o para v seria somente bombear
a′s e enta˜o para k ≥ j temos que uvkw tem mais a’s do que
b’s e uvkw /∈ L5.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRb|ε
Seja A = (K = {q0, q1}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, ε, X) = (q3, �),
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, ε, X) = (q3, �).
Consideramos aibj = uvw com j ≥ n.
Assim, se |vw| ≤ n, a opc¸a˜o para v seria somente bombear b′s
e enta˜o para k ≥ 2 temos que uvkw tem i a′s e mais que 2i+k
b’s e assim uvkw /∈ L5.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aSbb|ε
Seja A = (K = {q0, q1, q2, q3}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, ε, X) = (q3, �),
(q0, a, X) = (q1, AAX),
(q1, a, A) = (q1, AAA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, ε, X) = (q3, �).
L7 = {a
ibj : i ≤ j, i ≥ 0, j ≥ 0} L8 = {a
ibj : i ≥ j, i ≥ 0, j ≥ 0}
Consideramos aibj = uvw com i ≥ n.
Assim, como |uv| ≤ n, a opc¸a˜o para v seria somente bombear
a′s e enta˜o para k ≥ j temos que uvkw tem mais a’s do que
b’s e uvkw /∈ L7.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aSb|Sb|ε
Seja A = (K = {q0, q1}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, ε, X) = (q3, �),
(q0, a, X) = (q1, AX),
(q0, b, X) = (q2, X),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, b, X) = (q2, X),
(q2, ε, X) = (q3, �).
Consideramos aibj = uvw com j ≥ n.
Assim, se |vw| ≥ n, a opc¸a˜o para v seria somente bombear b′s
e enta˜o para k ≥ j temos que uvkw tem i a′s e mais que i b’s
e assim uvkw /∈ L8.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aSb|aSε
Seja A = (K = {q0, q1}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, ε, X) = (q3, �),
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, ε, A) = (q3, �),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, ε, A) = (q3, �),
(q2, ε, X) = (q3, �),
(q3, ε, A) = (q3, �),
(q3, ε, X) = (q3, �).
L9 = {a
ibick : i ≥ 1, k ≥ 1} L10 = {a
ibjci : i ≥ 1, j ≥ 1}
Consideramos aibicj = uvw com i ≥ n.
Assim, como |uv| ≤ n, a opc¸a˜o para v seria somente bombear
a′s e enta˜o para k ≥ 2 temos que uvkw tem mais a’s do que
b’s e uvkw /∈ L9.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRbcC
C → cC|ε R → aRb|ε)
Seja A = (K = {q0, q1, q2, q3, q4}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q4}), onde
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, �),
(q2, b, A) = (q2, �),
(q2, c, X) = (q3, X),
(q3, c, X) = (q3, X),
(q3, ε, X) = (q4, �).
Consideramos aibjci = uvw com i ≥ n.
Assim, como |uv| ≤ n, a opc¸a˜o para v seria somente bombear
a′ e enta˜o para k ≥ 2 temos que uvkw tem mais a’s do que
c’s e uvkw /∈ L10.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRc
R → aRc|bB
B → bB|ε)
Seja A = (K = {q0, q1, q2, q3, q4}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q4}), onde
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, A),
(q2, b, A) = (q2, A),
(q2, c, A) = (q3, �),
(q3, c, A) = (q3, �),
(q3, ε, X) = (q4, �).
2
L11 = {a
ibjcj : i ≥ 1, j ≥ 1} L12 = {a
ibjck : i ≥ j ≥ 1, k ≥ 1}
Consideramos aibjcj = uvw com i ≥ n.
Assim, com |vw| ≤ n, a opc¸a˜o para v seria somente bombear
c′s e enta˜o para k ≥ 2 temos que uvkw tem mais c’s do que
b’s e uvkw /∈ L11.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → AbRc
A → aA|ε
R → bRc|ε)
Seja A = (K = {q0, q1, q2, q3, q4}, Σ = {a, b},
Γ = {X, B, �}, δ, q0, X, F = {q4}), onde
(q0, a, X) = (q1, X),
(q1, a, X) = (q1, X),
(q1, b, X) = (q2, BX),
(q2, b, B) = (q2, BB),
(q2, c, B) = (q3, �),
(q3, c, B) = (q3, �),
(q3, ε, X) = (q4, �).
Consideramos aibjck = uvw com i ≥ n.
Assim, se |vw| ≤ n, a opc¸a˜o para v seria somente bombear b′
e enta˜o para k ≥ i temos que uvkw tem mais b’s do que a’s e
uvkw /∈ L12.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aRb
R → aR|aRb|ε)
Seja A = (K = {q0, q1, q2, q3, q4}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q4}), onde
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A)= (q2, �),
(q2, b, A) = (q2, �),
(q2, c, X) = (q3, X),
(q2, c, A) = (q3, �),
(q3, c, A) = (q3, �),
(q3, c, X) = (q3, X),
(q3, ε, A) = (q3, �),
(q3, ε, X) = (q4, �).
L13 = {a
ibjck : i ≤ k, i ≥ 1, j ≥ 1} L14 = {a
ibjck : j ≤ k, i ≥ 1, j ≥ 1}
Consideramos aibjck = uvw com i ≥ n.
Assim, se |uv| ≤ n, a opc¸a˜o para v seria somente bombear a′
e enta˜o para t ≥ k temos que uvkw tem mais a’s do que c’s e
uvkw /∈ L13.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aCc
C → aCc|Cc|bB
B → bB|ε)
Seja A = (K = {q0, q1, q2, q3, q4}, Σ = {a, b},
Γ = {X, A, �}, δ, q0, X, F = {q3}), onde
(q0, a, X) = (q1, AX),
(q1, a, A) = (q1, AA),
(q1, b, A) = (q2, A),
(q2, b, A) = (q2, A),
(q2, c, A) = (q3, �),
(q3, c, A) = (q3, �),
(q3, c, X) = (q3, X),
(q3, ε, X) = (q4, �).
Consideramos aibjck = uvw com j ≥ n.
Assim, se |vw| ≤ n, a opc¸a˜o para v seria somente bombear c′
e enta˜o para k ≥ i temos que uvkw tem mais c’s do que a’s e
uvkw /∈ L14.
Considere a grama´tica livre de contexto G =
(K = {S, R}, Σ = {a, b}, S, P =
S → aAbCc
A → aA|ε
C → bCc|Cc|ε)
Seja A = (K = {q0, q1, q2, q3, q4}, Σ = {a, b},
Γ = {X, B, �}, δ, q0, X, F = {q3}), onde
(q0, a, X) = (q1, X),
(q1, a, X) = (q1, X),
(q1, b, X) = (q2, BX),
(q2, b, B) = (q2, BB),
(q2, c, B) = (q3, �),
(q3, c, B) = (q3, �),
(q3, c, X) = (q3, X),
(q3, ε, X) = (q4, �).
L15 = {a
ibjck : i ≥ j, i ≥ 1, j ≥ 1} L16 = {a
ibjck : i ≥ k, i ≥ 1, j ≥ 1}
L17 = {a
ibjck : j ≥ k, i ≥ 1, j ≥ 1} L18 = {a
ibjck : i = j + k, i ≥ 1, j ≥ 1}
L19 = {a
ibjck : k = i + j, i ≥ 1, j ≥ 1} L20 = {a
ibjck : i = j, i ≥ 1, j ≥ 1}
2. Mostre que sa˜o ou na˜o regulares, ou que sa˜o ou na˜o livres de contexto as seguintes linguagens, com o aux´ılio dos
lemas do bombeamento:
3
L3a = {a
ibj : i, j ≥ 0} L3b = {a
ibi : i ≥ 0} L3c = {a
ibj : i ≥ j ≥ 0}
Regular Livre de Contexto na˜o regular Livre de Contexto na˜o regular
S → aA|B|ε S → aAb|ε S → A|ε
A → aA|ε A → aAb|aA|ε
B → bB|ε
Se L e´ uma linguagem regular, enta˜o L sat-
isfaz o teorema do bombeamento.
Enta˜o temos uma palavra aibj de L, e supo-
mos por contradic¸a˜o que L e´ regular e que
ω = anbn, para o n do teorema. Enta˜o
pelo Teorema do bombeamento anbn = uvw
como no teorema com |uv| ≤ n. Enta˜o v so´
tem a′s, e enta˜o uviw tem mais a′s que b′s
com t ≥ 2, e assim uvtw /∈ L3b.
Consideramos aibj = uvw com i ≥ n.
Assim, como |uv| ≤ n, a opc¸a˜o para v se-
ria somente bombear a′s e enta˜o para k ≥ j
temos que uvkw tem mais a’s do que b’s e
uvkw /∈ L3c.
L3d = {a
ibj : i ≥ 1, j ≥ 1} L3e = {w.w : w ∈ {a, b}
∗} L3f = {w.w
R : w ∈ {a, b}∗
Regular Sens´ıvel ao Contexto Livre de Contexto
na˜o Livre de Contexto na˜o regular
S → aA, A → aA|bB, B → bB|ε
Considere a grama´tica sens´ıvel ao contexto:
S → aAS Aa → aA Ab → bA
S → bBS|DF Ba → aB Bb → bB
AD → DA BD → DB Da → D′a
Db → D′b D′a → aD′ D′b → bD′
D′A → aD′ D′B → bD′ D′F → ε
Observamos que o Teorema do bombeamento
para linguagens livres de contexto tem uma
versa˜o fa´cil de provar que:
Theorem 3 Seja L uma linguagem livre de
contexto. Enta˜o, existe um par de naturais
n, k tal que qualquer cadeia z de L com com-
primento maior ou igual a n pode ser de-
composta em cinco cadeias t, u, x, v, e y(z =
tuxvy) de forma que |uxv| ≤ k ou |uv| ≥ 1
e para qualquer i ≥ 1, tuixviy ∈ L.
Suponha por contradic¸ ao que a linguagem
L seja livre de contexto.
Considere n, k ∈ IN para o teorema
do bombeamento e a palavra ω =
a(n+k)b(n+k)a(n+k)b(n+k). Enta˜o ω e´
particionado como ω = uvxyz com |vxy| ≤
k. Assim se vxy e´ consistido somente de a′s
ou somente de b′s, teremos um dos blocos
com mais que n+k s´ımbolos do mesmo tipo,
que implicaria que uvixyiz na˜o pertenceria
a L. Dessa forma, vxy e´ consistido de a′s e
de b′s. Novamente, uv2xy2z tera´ um ´nico
bloco com mais que n+k s´ımbolos do mesmo
tipo, que implicaria que uvixyiz na˜o per-
tenceria a L.
Considere a seguir a grama´tica livre de con-
texto:
S → aSa|bSb|ε.
Suponha por contradic¸a˜o que a linguagem
L seja regular. Considere n ∈ IN como no
teorema do bombeamento e a palavra ω =
a2(n)b2(n)a2(n). Pelo teorema ω pode ser
expresso como ω = vxy assumindo |vx| ≤ n,
quando bombear´ıamos somente a’s e assim
vx2y na˜o pertenceria a linguagem L.
3. Utilizando a mT M4 = (K, Σ, G, d, i, F ), em que K = {q0, q1, q2, q3, q4}, Σ = {a, b}, Γ = {a, b, X, Y, ε}, i = q0, F =
{q4}) e
δ a b X Y ε
q0 q1XR q3Y R q4XR
q1 q1aR q2Y L q1Y R
q2 q2aL q0XR q2Y L
q3 q3Y R q4XR
q4
Verifique se as cadeias aab e abbaa sa˜o aceitas por esta mT M4, mostrando a sequ¨eˆncia de configurac¸o˜es assumidas
por M4 ao tentar reconhecer cada cadeia.
Resposta: q0aab - Xq1ab - Xaq1b - Xq2aY - q2XaY - Xq0aY - XXq1Y - XXY q1, enta˜o na˜o aceita por M4.
q0abbaa - Xq1bbaa - q2XY baa - Xq0Y baa - XY q3baa, enta˜o na˜o aceita por M4.
4
4. Construa uma mT M5 que reconhec¸a as cadeias da linguagem L5 = {a
nbncn : n ≥ 1}.
Considere M = (K, Σ, Γ, δ, q0, F ), onde K = {q0, q1, q2, q3, q4}, Σ = {a, b}, Γ = {a, b, c, X, Y, Z, �}, F = {q4}, e
δ(q0, a) = (q1, X, R) δ(q0, Y ) = (q0, Y, R) δ(q0, Z) = (q0, Z, R) δ(q0, �) = (q4, �, L) δ(q1, a) = (q1, a, R)
δ(q1, Y ) = (q1, Y, R) δ(q1, b) = (q2, Y, R) δ(q2, b) = (q2, b, R) δ(q2, Z) = (q2, Z, R) δ(q2, c) = (q3, Z, L)
δ(q3, b) = (q3, b, L) δ(q3, Y ) = (q3, Y, L) δ(q3, a) = (q3, a, L) δ(q3, X) = (q0, X, R)
Exemplo da derivac¸a˜o de aaabbbccc:
q0aaabbbccc → Xq1aabbbccc → Xaq1abbbccc → Xaaq1bbbccc → XaaY q2bbccc → XaaY bq2bccc → XaaY bbq2ccc → XaaY bq3bZcc →
XaaY q3bbZcc → Xaaq3Y bbZcc → Xaq3aY bbZcc → Xq3aaY bbZcc → Xq0aaY bbZcc → XXq1aY bbZcc → XXaq1Y bbZcc →
XXaY q1bbZcc → XXaY Y q2bZcc → XXaY Y bq2Zcc → XXaY Y bZq2cc → XXaY Y bq3ZZc → XXaY Y q3bZZc → XXaY q3Y bZZc →
XXaq3Y Y bZZc → XXq3aY Y bZZc → Xq3XaY Y bZZc → XXq0aY Y bZZc → XXXq1Y Y bZZc → XXXY q1Y bZZc →
XXXY Y q1bZZc → XXXY Y Y q2ZZc → XXXY Y Y Zq2Zc → XXXY Y Y ZZq2c → XXXY Y Y ZZq3Z → XXXY Y Y Zq3ZZ →
XXXY Y Y q3ZZZ → XXXY Y q3Y ZZZ → XXXY q3Y Y ZZZ → XXXq3Y Y Y ZZZ → XXq3XY Y Y ZZZ → XXXq0Y Y Y ZZZ →
XXXY q0Y Y ZZZ → XXXY Y q0Y ZZZ → XXXY Y Y q0ZZZ → XXXY Y Y Zq0ZZ → XXXY Y Y ZZq0Z → XXXY Y Y ZZZq0 →
XXXY Y Y ZZq4Z.
5. Tente definir a grama´tica G6 , para a linguagem L6 = {a
ibjck : i < j < k, i ≥ 1}, com base na grama´tica sens´ıvel
ao contexto G6 = (S, B, C, a, b, c, P, S), que gera a linguagem L6 = {a
nbncn : n ≥ 1}, cujas regras encontram-se, a
seguir:
S → aSBC S → aBC CB → BC,
aB → ab bB → bb bC → bc,
cC → cc.
Resposta:
Considere
S → aRBBCCC R → RC|RBC|aRBC|ε CB → BC
aB → ab bB → bb bC → bc
cC → cc
Exemplo: derivac¸a˜o de abbbcccc:
S → aRBBCCC → aRBCBBCCC → aBCBBCCC → aBBCBCCC → aBBBCCCC → abBBCCCC → abbBCCCC → abbbCCCC →
abbbcCCC → abbbccCC → abbbcccC → abbbcccc.
5