Prova 2 - Autômatos e Computabilidade 1º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
1. Seja um autoˆmato com pilha na˜o-determin´ıstico A = (Q,Σ,Γ, δ, q0, F ).
(a) (1 ponto) Escreva o domı´nio e o contradomı´nio da func¸a˜o de transic¸a˜o δ.
Resposta: o domı´nio e´ Q× Σε × Γε e o contradomı´nio e´ P(Q× Γε).
(b) (1 ponto) Defina formalmente o que significa que o autoˆmato A aceite uma cadeia de
entrada w.
Resposta: A aceita a cadeia w se a cadeia pode ser escrita na forma w =
w1w2 · · ·wk, onde cada wi ∈ Σε, e existem uma sequeˆncia de estados r0, r1, . . . , rk ∈
Q e uma sequeˆncia de cadeias s0, s1, . . . , sk ∈ Γ
∗ tais que:
i. r0 = q0 e s0 = ε.
ii. (ri+1, b) ∈ δ(ri, wi+1, a) para i = 0, 1, . . . , k − 1, com si = at e si+1 = bt para
a, b ∈ Γε e t ∈ Γ
∗.
iii. rk ∈ F .
2. (1 ponto) Prove que toda linguagem finita e´ livre-do-contexto. Na sua resposta, mostre como
construir uma grama´tica livre-do-contexto que gere uma linguagem finita dada (escreva as
regras dessa grama´tica).
Resposta: Seja a linguagem finita L = {x1,, x2, . . . , xk}, onde cada xi e´ uma cadeia
sobre um alfabeto Σ. Provamos que L e´ livre-do-contexto mostrando que existe uma
grama´tica livre-do-contexto que a gera; por exemplo:
S → x1 | x2 | · · · | xk
3. Seja a grama´tica livre-do-contexto G1:
S → TX
T → aTa | bTb | X
X → aX | bX | ε
(a) (1 ponto) Construa uma grama´tica livre-do-contexto G2 equivalente, na qual somente
a varia´vel inicial S possa ser substitu´ıda pela cadeia vazia ε.
Resposta: Aplicando o primeiro passo para converter uma grama´tica livre-do-
contexto qualquer em uma equivalente na forma normal de Chomsky, obtemos
S → TX | T | X | ε
T → aTa | bTb | aa | bb | X
X → aX | bX | a | b
Por outro lado, e´ fa´cil ver que a grama´tica G1 dada gera qualquer cadeia w ∈ {a, b}
∗
(note que, em G1, S ⇒ TX ⇒ XX, e aplicando as substituic¸o˜es da u´ltima linha
de G1 podemos gerar qualquer cadeia). Por tanto, uma grama´tica equivalente da
forma solicitada pode ser tambe´m
S → aS | bS | ε
(b) (1 ponto) Desenhe o diagrama de estados de um autoˆmato com pilha AP equivalente.
Atenc¸a˜o: na˜o utilize notac¸o˜es abreviadas para as transic¸o˜es: em cada transic¸a˜o, o AP
empilha um u´nico s´ımbolo (que tambe´m pode ser ε).
Resposta: Podemos converter a grama´tica dada em um AP equivalente seguindo
o me´todo explicado no Lema 2.20, pp. 120–123 do livro-texto. Outro caminho e´
observar que a grama´tica gera cadeias da forma xyxRz, onde x, y, z ∈ {a, b}∗, o que
leva ao AP
q0 q1 q2 q3 q4 q5
ε, ε→ $
a, ε→ a
b, ε→ b
ε, ε→ ε
a, ε→ ε
b, ε→ ε
ε, ε→ ε
a, a→ ε
b, b→ ε
ε, ε→ ε
a, ε→ ε
b, ε→ ε
ε, $→ ε
Ainda, conforme explicado na resposta ao item (a) anterior, a grama´tica dada gera
qualquer cadeia w ∈ {a, b}∗ (note que qualquer cadeia w pode ser expressada na
forma xyxRz). Enta˜o, um AP equivalente tambe´m e´, simplesmente,
q0
a, ε→ ε
b, ε→ ε
4. Determine se cada uma das seguintes linguagens e´ livre-do-contexto ou na˜o. Justifique sua
resposta.
(a) (1 ponto) L1 = {x$y| x,y ∈ (ab)
∗}
Resposta: A linguagem e´ livre-do-contexto, pois L1 = L ◦ L
′ ◦ L, onde L = (ab)∗,
que e´ regular e portanto livre-do-contexto, e L′ = {$}, que e´ finita e portanto livre-
do-contexto (veja resposta a` questa˜o 2). Sabemos, tambe´m, que a concatenac¸a˜o de
linguagens livres-do-contexto produz outra linguagem livre-do-contexto.
(b) (1 ponto) L2 = {w$w| w ∈ {a, b}
∗}
Resposta: A linguagem na˜o e´ livre-do-contexto. Para provar esta afirmac¸a˜o, apli-
camos o lema do bombeamento. Suponha que L2 seja livre-do-contexto, e seja p seu
comprimento de bombeamento. Escolhemos a cadeia de teste s = apbp$apbp ∈ L2,
de comprimento |w| = 4p+1 ≥ p. Subdividimos esta cadeia em 5 partes s = uvxyz,
com |vxy| ≤ p.
i. Se vxy na˜o conte´m o s´ımbolo $, enta˜o vxy esta´ antes ou depois da ocorreˆncia
desse s´ımbolo, e vy conte´m pelo menos um a ou um b. Bombeando s para
baixo, obtemos uma cadeia da forma uxz = w1$w2, onde w1 6= w2 (se vxy esta´
antes da ocorreˆncia de $, enta˜o |w1| < |w2|, e se vxy esta´ depois da ocorreˆncia
de $, enta˜o |w1| > |w2|). Assim, uxz /∈ L2.
ii. Se vxy conte´m o s´ımbolo $, temos duas alternativas: (a) Se v = $ ou y = $,
enta˜o, bombeando s para baixo, obtemos uma cadeia uxz que na˜o conte´m $
e, portanto, uxz /∈ L2. Se x = $, enta˜o v = b
i e y = aj, onde 0 < i + j < p.
Bombeando s para baixo, obtemos uxz = apbp−i$ap−jbp. A quantidade de
as e/ou a quantidade de bs a` direita e esquerda do s´ımbolo $ sa˜o diferentes,
portanto, uxz /∈ L2.
Conclu´ımos que a cadeia s viola o lema do bombeamento, o que implica que L2 na˜o
e´ livre-do-contexto.
5. (1 ponto) Sejam L1 e L2 linguagens Turing-reconhec´ıveis. Descreva uma ma´quina de Turing
que reconhec¸a L1 ∪ L2, no formato
M= “Sobre a cadeia de entrada w:
1....
2....
...
n. Se... aceite.”
Resposta: Sejam M1 e M2 as ma´quinas de Turing que reconhecem L1 e L2, respectiva-
mente. A seguinte ma´quina de Turing reconhece L1 ∪ L2:
E= “Sobre a cadeia de entrada w:
1. Rode M1 e M2 sobre w de forma alternada, um passo cada vez. Em cada passo:
2. Se M1 ou M2 aceita w, aceite.”
6. (1 ponto) Verdadeiro ou falso? Responda e justifique brevemente.
(a) Existem ma´quinas de Turing que na˜o decidem nenhuma linguagem.
Resposta: Verdadeiro. Uma ma´quina de Turing que na˜o para sobre alguma cadeia
na˜o decide nenhuma linguagem.
(b) Existem ma´quinas de Turing que na˜o reconhecem nenhuma linguagem.
Resposta: Falso. Por definic¸a˜o, uma ma´quina de Turing reconhece a linguagem
formada pelo conjunto de cadeias que aceita. Se na˜o aceita nenhuma cadeia, ainda
assim reconhece uma linguagem: a linguagem vazia ∅.
7. (1 ponto) Considere uma ma´quina de Turing cuja cabec¸a de leitura/escritura possa se mo-
vimentar somente a` direita, chamada MTD. Podemos definir a MTD de maneira similar a`
ma´quina de Turing padra˜o, como uma 7-upla M = (Q,Σ,Γ, δ, q0, qaceita, qrejeita). A u´nica
diferenc¸a com a definic¸a˜o de a MT padra˜o e´ que no contradomı´nio da func¸a˜o de transic¸a˜o
na˜o precisamos incluir a direc¸a˜o de movimento da cabec¸a da ma´quina, pois e´ sempre a
mesma (a` direita). Assim, o contradomı´nio de δ e´ Q× Γ.
Mostre como converter um autoˆmato finito determin´ıstico (AFD) dado em uma MTD equi-
valente, o que prova que toda linguagem regular e´ reconhecida por uma MTD.
Resposta: Seja um AFD A = (Q,Σ, δ, q0, F ). Constru´ımos uma MTD equivalente M =
(Q′,Σ,Γ, δ′, q0, qaceita, qrejeita), com Γ = Σ ∪ {⊔}, Q
′ = Q ∪ {qaceita, qrejeita} e δ
′ definida
da seguinte forma: para cada estado q ∈ Q e cada s´ımbolo a ∈ Σ, se δ(q, a) = r,
adicionamos uma regra δ′(q, a) = (r, a). Assim, a MTD passa de um estado a outro
segundo cada s´ımbolo lido, da mesma maneira que o AFD. Tambe´m, para cada estado
q ∈ F , adicionamos uma regra δ′(q,⊔) = (qaceita,⊔). Desta forma, a MTD aceita a cadeia
de entrada se, ao finalizar a leitura da cadeia, se encontra em algum dos estados de
aceitac¸a˜o do AFD.