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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
Parte 1
Para cada questa˜o, indique a resposta correta. Na˜o precisa justificar sua escolha.
1. Seja a grama´tica G definida por
S → AX | Y C
A → aA | ε
C → cC | ε
X → bXc | ε
Y → aY b | ε
Qual das seguintes cadeias pode ser derivada de S em zero ou mais passos?
(a) aaba
(b) aabbbc
(c) aaAbXc
Resposta: (c). A linguagem gerada pela grama´tica e´ {aibjck| i = j ou j = k}. As
respostas (a) e (b) violam esse formato, enquanto que S ⇒ AX ⇒ aAX ⇒ aaAX ⇒
aaAbXc.
2. Na grama´tica do item (1), o conjunto de cadeias que podem ser derivadas de C e´
(a) c∗
(b) Cadeias com uma quantidade par de cs.
(c) ∅ porque C na˜o e´ a varia´vel inicial.
Resposta: (a).
3. Qual das seguintes afirmac¸o˜es sobre a grama´tica do item (1) e´ verdadeira?
(a) G e´ amb´ıgua porque abc tem duas derivac¸o˜es diferentes a partir de S.
(b) G e´ amb´ıgua porque abc tem duas a´rvores sinta´ticas diferentes apartir de S.
(c) G na˜o e´ amb´ıgua porque pode ser convertida a` forma normal de Chomsky.
Resposta: (b). Uma grama´tica e´ amb´ıgua se alguma cadeia tem duas a´rvores sinta´ticas
diferentes
S
A
a A
ε
X
b X
ε
c
S
Y
a Y
ε
b
C
c C
ε
Duas derivac¸o˜es diferentes para a mesma cadeia na˜o necessariamente indicam ambigu¨i-
dade.
4. Considere o autoˆmato com pilha P definido por
q0 q1
ε,ε→ ε
a,#→ εb,ε→ #
Suponha que o autoˆmato esta´ no estado q1, que o conteu´do da pilha e´ ##### e que a porc¸a˜o na˜o
lida da cadeia de entrada e´ abba. Depois de executar um passo, o autoˆmato
(a) termina sua operac¸a˜o.
(b) continua no estado q1 e o conteu´do da pilha e´ ######.
(c) continua no estado q1 e o conteu´do da pilha e´ ####.
Resposta: (c). O autoˆmato desempilha um # e continua em q1.
5. A linguagem reconhecida pelo autoˆmato do item (4) e´
(a) {bnan| n ≥ 0}
(b) {bman| m ≥ n ≥ 0}
(c) {bman| n ≥ m ≥ 0}
Resposta: (b). Em q0, o autoˆmato empilha um # para cada b na cadeia de entrada. Em
q1, desempilha um # para cada a. Como q1 e´ um estado de aceitac¸a˜o, o autoˆmato aceita
sempre que puder desempilhar um #, i.e., sempre que a quantidade de as seja menor ou
igual que a quantidade de bs.
6. Seja a linguagem L = {ambnambn| m,n ≥ 0}, e considere a seguinte demonstrac¸a˜o de que L
sim satisfaz o lema do bombeamento para linguagens livre-do-contexto: Seja p o comprimento de
bombeamento. Escolha s = apbapb ∈ L. Divida s na forma s = uvxyz, com u = ap−1, v = a,
x = b, y = a, z = ap−1b. Claramente, uvixyiz ∈ L para todo i ≥ 0.
(a) A demonstrac¸a˜o esta´ incorreta porque na˜o foram consideradas todas as poss´ıveis diviso˜es de
s.
(b) A demostrac¸a˜o esta´ incorreta porque na˜o foram consideradas todas as poss´ıveis cadeias s ∈ L.
(c) A demonstrac¸a˜o esta´ correta.
Resposta: (b).
7. Seja a linguagem L = {anbncn| ≥ 0}, e considere a seguinte demonstrac¸a˜o de que L na˜o satisfaz
o lema do bombeamento para linguagens livre-do-contexto: Seja p ≥ 1 o comprimento de bombe-
amento. Escolha s = apbpcp ∈ L, e divida s na forma s = uvxyz, com u = ε, v = a, x = ε, y = ε,
z = ap−1bpcp. Claramente, uv0xy0z /∈ L.
(a) A demonstrac¸a˜o esta´ incorreta porque na˜o foram consideradas todas as poss´ıveis diviso˜es de
s.
(b) A demostrac¸a˜o esta´ incorreta porque na˜o foram consideradas todas as poss´ıveis cadeias s ∈ L.
(c) A demonstrac¸a˜o esta´ correta.
Resposta: (a).
8. Quantas ma´quinas de Turing e´ poss´ıvel construir com alfabeto de entrada Σ = {0,1}, alfabeto de
fita Γ = {0,1,⊔}, e os estados q0, qaceita e qrejeita?
(a) 3.
(b) 183.
(c) Infinitas.
Resposta: (b). No diagrama de estados de cada ma´quina de Turing ha´ 3 setas de
transic¸a˜o saindo de q0 (uma para cada s´ımbolo em Γ). Para cada transic¸a˜o, ha´ 3 estados
alvo poss´ıveis, 3 s´ımbolos que podem ser escritos na fita, e 2 sentidos poss´ıveis para mover
a cabec¸a leitora.
9. Suponha que M1 e M2 sa˜o ma´quinas de Turing que reconhecem as linguagens L1 e L2, respectiva-
mente, e L1 ⊆ L2. Enta˜o
(a) Para cada cadeia de entrada na qual M1 na˜o para, M2 tampouco para.
(b) Para cada cadeia de entrada na qual M1 para, M2 tambe´m para.
(c) Para cada cadeia de entrada que M1 aceita, M2 para.
Resposta: (c). M2 aceita todas as cadeias de L1.
10. Se L e´ uma linguagem Turing-decid´ıvel, enta˜o
(a) L e L¯ devem ser Turing-reconhec´ıvel.
(b) L deve ser Turing-reconhec´ıvel, mas L¯ pode na˜o seˆ-lo.
(c) L ou L¯ e´ Turing-reconhec´ıvel, mas na˜o ambas.
Resposta: (a). L e´ Turing-reconhec´ıvel, pois e´ decid´ıvel. L¯ tambe´m deve ser decid´ıvel,
pois podemos construir uma ma´quina de Turing que aceite as cadeias que na˜o esta˜o em
L e rejeite as que sim esta˜o. Se L¯ e´ decid´ıvel tambe´m e´ reconhec´ıvel.
Parte 2
1. Considere a seguinte ma´quina de Turing M sobre o alfabeto de entrada {0, 1}. Todas as transic¸o˜es
na˜o mostradas no diagrama conduzem ao estado de rejeic¸a˜o.
q0
q1
q2
qaceita
1→ 0,D
0→ 1,E
0→ 1,D
⊔ → ⊔,D
(a) Escreva a definic¸a˜o formal de M como uma 7-upla.
Resposta: M = (Q,Σ,Γ, δ, qo, qaceita, qrejeita), onde Q = {q0, q1, q2, qaceita, qrejeita},
Σ = {0, 1} , Γ = {0, 1,⊔} e δ e´ a func¸a˜o definida por
δ(q0, 1) = (q1, 0, D)
δ(q1, 0) = (q2, 1, E)
δ(q1,⊔) = (qaceita,⊔, D)
δ(q2, 0) = (q0, 1, D)
δ(q, a) = (qrejeita,⊔, D) para qualquer outro caso
(b) Descreva a operac¸a˜o de M sobre a entrada 1000, como uma sequeˆncia de configurac¸o˜es. Para
cada configurac¸a˜o, indique o conteu´do da fita, a posic¸a˜o da cabec¸a leitora, e o estado de M .
Por exemplo, a configurac¸a˜o inicial e´
q0
↓
1 0 0 0 ⊔ . . .
Tambe´m pode utilizar a notac¸a˜o do livro-texto: q01000⊔
Resposta:
q01000⊔ 11q010⊔
0q1000⊔ 110q10⊔
q20100⊔ 11q201⊔
1q0100⊔ 111q01⊔
10q100⊔ 1110q1⊔
1q2010⊔ 1110 ⊔ qaceita⊔
(c) Existe alguma cadeia para qual a M na˜o para?
Resposta: Na˜o, M aceita ou rejeita todas as cadeias de entrada.
(d) Qual a linguagem reconhecida por M?
Resposta: 10*.
2. Toda linguagem decid´ıvel por uma ma´quina de Turing com k > 1 fitas pode ser decidida tambe´m
por uma ma´quina de Turing com k − 1 fitas? Justifique brevemente sua resposta.
Resposta: Sim. Toda linguagem decidida por uma ma´quina de Turing com k > 1 fitas
tambe´m e´ decidida por uma ma´quina de Turing com uma u´nica fita. Uma ma´quina de
Turing com uma fita pode ser considerada como uma ma´quina de k− 1 fitas, que apenas
utiliza a primeira e ignora as restantes.
3. Suponha que A e B sa˜o linguagens Turing-reconhec´ıveis e que A∪B e A∩B sa˜o ambas decid´ıveis.
Prove que A e´ decid´ıvel.
Resposta: Sejam MA e MB as ma´quinas de Turing que reconhecem as linguagens A e
B, respectivamente, e MA∪B e MA∩B as que decidem A ∪ B e A ∩ B, respectivamente.
Construimos uma ma´quina de Turing M que decide A da seguinte forma:
Para uma cadeia de entrada w, M roda MA∪B .
Se MA∪B rejeita, w /∈ A, portanto, M rejeita (e para).
Se MA∪B aceita, M roda MA∩B.
Se MA∩B aceita, enta˜o w ∈ A e M aceita (e para).
Se MA∩B rejeita, enta˜o w ∈ A ou w ∈ B (mas na˜o pertence a ambos).
Agora, M roda MA e MB em paralelo, alternando entre ambas um passo por vez.
Uma das duas ma´quinas, MA ou MB , deve aceitar w.
Se MA aceita, M aceita (e para).
Se MB aceita, M rejeita (e para).