2ª Prova de Autômatos e Computabilidade - 2º/2014 - Lucero - UnB

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
1. (1 ponto) Prove que a classe das linguagens livres-do-contexto e´ fechada sobre a concatena-
c¸a˜o.
Resposta: Sejam L1 e L2 linguagens livres-do-contexto, geradas pelas grama´ticas G1 =
(V1,Σ, R1, S1) eG2 = (V2,Σ, R2, S2), respectivamente (por simplicidade, assumimos o mesmo
alfabeto Σ para ambas linguagens). A linguagem L = L1 ◦ L2 tambe´m e´ livre-do-contexto,
pois e´ gerada pela grama´tica G = (V,Σ, R, S) onde V = V1∪V2∪{S}, R = R1∪R2∪{S →
S1S2} e S e´ uma nova varia´vel que na˜o pertence a V1 nem a V2.
2. (1,5 pontos) O problema da pertineˆncia para grama´ticas livres-do-contexto pode ser enunci-
ado da seguinte forma: dada uma grama´tica livre-do-contexto G e uma cadeia w, w ∈ L(G)?.
A forma normal de Chomsky para grama´ticas livres-do-contexto permite resolver esse pro-
blema. Explique como.
Resposta: Uma grama´tica na forma normal de Chomsky gera uma cadeia de comprimento
n em exatamente 2n − 1 passos, se n ≥ 1, ou 1 passo, se n = 0. Logo, para determinar
se w ∈ L(G), convertemos G na forma normal de Chomsky. Se |w| ≥ 1, listamos todas as
cadeias geradas pela grama´tica em 2|w| − 1 passos; se |w| = 0, listamos todas as cadeias
geradas em um passo. Se w esta´ nessas listas, enta˜o w ∈ L(G); se na˜o, enta˜o w /∈ L(G).
3. (1,5 pontos) Prove que a linguagem L = {ambncp|m ≥ n ≥ p ≥ 0} na˜o e´ livre-do-contexto.
Utilize o lema do bombeamento .
Resposta: Suponha que L seja livre-do-contexto com comprimento de bombeamento p.
Escolhemos a cadeia de teste s = apbpcp. Note que s ∈ L, e |s| = 3p ≥ p. Fazemos
s = uvxyz, com |vxy| ≤ p e |vy| > 0.
(a) Suponha vy = ak, com 1 ≤ k ≤ p. Enta˜o, uv0xy0z = ap−kbpcp /∈ L, pois a quantidade
de as e´ menor que a quantidade de bs e que a quantidade de cs.
(b) Suponha que vxy conte´m k as e ℓ bs, com 1 ≤ k+ℓ ≤ p. Enta˜o, uv0xy0z = ap−kbp−ℓcp /∈
L, pois a quantidade de as ou a quantidade de bs (ou ambas) sa˜o menores que a
quantidade de cs.
(c) Suponha vy = bk, com 1 ≤ k ≤ p. Enta˜o, uv0xy0z = apbp−kcp /∈ L, pois a quantidade
de bs e´ menor que a quantidade de cs.
(d) Suponha que vxy conte´m k bs e ℓ cs, com 1 ≤ k+ℓ ≤ p. Enta˜o, uv2xy2z = apbp+kcp+ℓ /∈
L, pois a quantidade de bs ou a quantidade de cs (ou ambas) sa˜o maiores que a
quantidade de as.
(e) Suponha vy = ck, com 1 ≤ k ≤ p. Enta˜o, uv2xy2z = apbpcp+k /∈ L, pois a quantidade
de cs e´ maior que a quantidade de as e que a quantidade de bs.
Conclu´ımos que a cadeia s viola o lema do bombeamento, o que implica que L na˜o e´ livre-
do-contexto.
4. (1 ponto) Desenhe o diagrama de estados de um autoˆmato com pilha que reconhec¸a a
linguagem L = {vbw| v, w ∈ {a, b}∗ e |v| = |w|}.
Resposta:
q0 q1 q2 q3
ε, ε→ $
a, ε→ x
b, ε→ x
b, ε→ ε
a, x→ ε
b, x→ ε
ε, $→ ε
5. (1,5 pontos) Fornec¸a a definic¸a˜o formal de uma ma´quina de Turing que decida a linguagem
L = {ε} sobre o alfabeto Σ =. Na˜o esquec¸a da func¸a˜o de transic¸a˜o.
Resposta: M = ({q0, qa, qr}, {a, b}, {a, b⊔}, δ, q0, qa, qr), com δ(q0,⊔) = (qa,⊔, D), δ(q0, a) =
(qr,⊔, D) e δ(q0, b) = (qr,⊔, D).
6. (1 ponto) Seja L uma linguagem decid´ıvel. Descreva uma ma´quina de Turing que decida L,
usando o formato
M= “Sobre a entrada...:
1....
...
Resposta: Seja M a ma´quina de Turing que decide L. Enta˜o, uma ma´quina que decide L
e´
M= “Sobre a cadeia de entrada w:
1. Rode M sobre w. Se aceita, rejeite; se rejeita, aceite.
7. (2 pontos) Prove que uma linguagem e´ Turing-reconhec´ıvel se e somente se e´ enumera´vel.
Resposta: Seja L uma linguagem Turing-reconhec´ıvel sobre o alfabeto Σ e R a ma´quina
de Turing que reconhece L. Seja s1, s2, s3, . . . uma lista de todas as poss´ıveis cadeias sobre
Σ, em ordem lexicogra´fica. Podemos construir um enumerador para L, da seguinte forma:
E= “Ignore a entrada:
1. Repita os seguintes passos para i = 1, 2, 3, . . .
2. Gere uma nova cadeia si ∈ Σ
∗.
3. Rode R por i passos sobre cada cadeia s1, s2, . . . , si.
4. Imprima cada cadeia aceita por R.”
Seja L uma linguagem enumera´vel sobre o alfabeto Σ e E um enumerador para L. Podemos
construir uma ma´quina de uring que reconhece L, da seguinte forma:
R= “Sobre a cadeia de entrada:
1. Rode E para gerar cadeias si ∈ L. Para cada cadeia gerada:
3. Compare w com si. Se w = si, aceite.”
8. (0,5 ponto) Enuncie a Tese de Church-Turing.
Resposta: Qualquer processo computacional que, intuitivamente, possa ser considerado
um algoritmo pode ser convertido em uma ma´quina de Turing que sempre para.