prova3-2020-2-gabarito

Prévia do material em texto

Universidade Federal de Sergipe - Departamento de Computação
COMP0409 - Linguagens Formais e Computabilidade - T01 - 2020.2
Prof. Breno Piva
Prova 3 27 de julho de 2021
Nome:
Questão: 1 2 3 4 5 6 7 8 9 10 Total
Valor: 1 1 1 1 1 1 1 1 1 1 10
Pontuação:
1. (1 ponto) Sobre a enumerabilidade de conjuntos considere as afirmações:
I - Tanto o conjunto de todas as cadeias que descrevem Reconhecedores (no alfabeto binário) quanto o
conjunto das cadeias que descrevem linguagens (como sequências caracteŕısticas) são conjuntos infinitos
e, portanto, do mesmo tamanho.
II - O conjunto das codificações binárias de Decisores é um conjunto enumerável (contável).
III - O conjunto de todas as cadeias que descrevem linguagens (como sequências caracteŕısticas) é um
conjunto enumerável (contável).
a) Apenas I está correta.
b) Apenas II está correta. ←
c) Apenas III está correta.
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas.
h) Nenhuma está correta.
2. (1 ponto) Sobre a enumerabilidade de conjuntos considere as afirmações:
I - Se A é um conjunto contável e A está contido em B, então B é contável.
II - Se A está contido em B e B é incontável, então A é incontável.
III - Se A é uma linguagem decid́ıvel então A é um conjunto infinito.
a) Apenas I está correta.
b) Apenas II está correta.
c) Apenas III está correta.
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas.
h) Nenhuma está correta. ←
3. (1 ponto) Seja A um problema NÃO Turing-reconhećıvel, seja B um problema Turing-decid́ıvel e seja C
um problema sobre o qual não temos nenhuma informação. Considere as afirmações a seguir:
I - Se B ≤ C, então C é Turing-decid́ıvel.
II - Se A ≤ C, então C é NÃO Turing-reconhećıvel.
III - Se C ≤m B, então C é Turing-decid́ıvel.
a) Apenas I está correta.
b) Apenas II está correta.
c) Apenas III está correta. ←
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas.
h) Nenhuma está correta.
4. (1 ponto) Seja A um problema Turing-reconhećıvel, seja B um problema que é Turing-indecid́ıvel e seja C
um problema sobre o qual não temos nenhuma informação. Considere as afirmações a seguir:
I - Se A ≤m C, então C é Turing-reconhećıvel.
II - Se B ≤m C, então C é Turing-indecid́ıvel.
III - Se C ≤m A, então C é Turing-reconhećıvel.
a) Apenas I está correta.
b) Apenas II está correta.
c) Apenas III está correta.
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas. ←
g) Todas estão corretas.
h) Nenhuma está correta.
5. (1 ponto) Sejam F e M1 máquinas de Turing como descritas abaixo. Assinale a alternativa correta com
respeito às afirmações feitas em seguida.
F = ‘ ‘ Sobre a entrada < M,w > :
1 − Construa a MT M1 como d e s c r i t o .
2 − Dê < M1 > como sa ı́da . ’ ’
M1 = ‘ ‘ Sobre a entrada x :
1 − Se x 6= w , r e j e i t e .
2 − Senão , rode M com w .
3 − Se M a c e i t a r , a c e i t e . ’ ’
I - F é, claramente, parte de uma redução por mapeamento de PARAMT para VMT .
II - F é, claramente, parte de uma redução por mapeamento de AMT para VMT .
III - Sabendo que co−AMT não é reconhećıvel, F pode ser usada diretamente para provar que VMT não é
reconhećıvel.
a) Apenas I está correta.
b) Apenas II está correta.
c) Apenas III está correta. ←
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas.
h) Nenhuma está correta.
Page 2
6. (1 ponto) Seja M1 um reconhecedor para A e M2 um decisor para B. Então podemos afirmar:
I - B é Turing-reconhećıvel.
II - A ∩B é Turing-reconhećıvel.
III - A ∪B é Turing-reconhećıvel.
a) Apenas I está correta.
b) Apenas II está correta.
c) Apenas III está correta.
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas. ←
h) Nenhuma está correta.
7. (1 ponto) Considere a MT a seguir e as afirmações feitas sobre ela.
M = ‘ ‘ Sobre a entrada < M1, w > :
1 − Construa M2 como a s e g u i r :
M2 = ‘ ‘ Sobre a entrada x :
1 . Rode M1 com w
2 . Se M1 a c e i t a r , a c e i t e
3 . Se M1 r e j e i t a r , r e j e i t e ’ ’
2 − Devolva < M2 > . ’ ’
I - M é, claramente, parte de uma redução de AMT para co− VMT .
II - M é, claramente, parte de uma redução por mapeamento de PARAMT para co− VMT .
III - Sabendo que PARAMT é indecid́ıvel seria posśıvel provar que VMT também é indecid́ıvel usando
diretamente a MT M .
a) Apenas I está correta. ←
b) Apenas II está correta.
c) Apenas III está correta.
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas.
h) Nenhuma está correta.
8. (1 ponto) Considere a linguagem A, a MT M e as afirmações feitas sobre elas.
Seja A = {< M1,M2,M3,M4 > |L(M1) ∩ L(M2) = L(M3).L(M4)} e seja
D = ‘ ‘ Sobre a entrada < M,M ′ > :
1 − Construa M5 como a s e g u i r :
M5 = ‘ ‘ Sobre qualquer entrada :
1 . R e j e i t e . ’ ’
M6 = ‘ ‘ Sobre qualquer entrada :
1 . Ace i te . ’ ’
2 − Devolva < M,M6,M ′,M5 > . ’ ’
I - D provê uma redução de EQMT para A.
Page 3
II - D provê uma redução de A para EQMT .
III - D é, claramente, parte de uma redução por mapeamento de co− EQMT para A.
a) Apenas I está correta.
b) Apenas II está correta.
c) Apenas III está correta.
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas.
h) Nenhuma está correta. ←
9. (1 ponto) Considere as MTs abaixo e as afirmações feitas a respeito delas.
M1 = ({q0, q1, q2, q3, q4, q5, q6, qa, qr}, {a, b, c}, {a, b, c,t, a, c}, δ, q0, qa, qr), onde: δ(q0, a,t) = (q1, a,t, D, P ),
δ(q1, a,t) = (q1, a,t, D, P ), δ(q1, b,t) = (q2, b, c,D,D), δ(q2, b,t) = (q2, b, c,D,D), δ(q2, c,t) = (q3, c,t, E, P ),
δ(q3, a,t) = (q3, a,t, E, P ), δ(q3, b,t) = (q3, b,t, E, P ), δ(q3, c,t) = (q3, c,t, E, P ), δ(q3, a,t) = (q4, a,t, D, P ),
δ(q4, a,t) = (q1, a,t, D, P ), δ(q4, b,t) = (q5, b,t, D,E), δ(q5, b, c) = (q5, b, c,D, P ), δ(q5, c, c) = (q6, c, c, P, P ),
δ(q6, c, c) = (q6, c, c,D,E), δ(q6,t, c) = (qa,t, c, P, P )
M2 = ({q0, q1, q2, q3, q4, qa, qr}, {a, b, c}, {a, b, c,t, c}, δ, q0, qa, qr), onde: δ(q0, a,t) = (q1, a, c,D,D), δ(q1, a,t) =
(q1, a, c,D,D), δ(q1, b,t) = (q2, b, c,D,D), δ(q2, b,t) = (q2, b, c,D,D), δ(q2, c,t) = (q3, c,t, P, E), δ(q3, c, c) =
(q3, c, c,D,E), δ(q3, c, c) = (q4, c, c,D,E), δ(q4,t, c) = (qa,t, c, P, P )
I - M1 é um decisor para {aibjck|i× j = k e i, j, k > 0}
II - M1 é um reconhecedor para {aibjck|i× j = k e i, j, k > 0}
III - M2 é um decisor para {aibjck|i+ j = k e i, j, k > 0}
a) Apenas I está correta.
b) Apenas II está correta. ←
c) Apenas III está correta.
d) Apenas I e II estão corretas.
e) Apenas I e III estão corretas.
f) Apenas II e III estão corretas.
g) Todas estão corretas.
h) Nenhuma está correta.
10. (1 ponto) Considere a MT e as linguagens descritas a seguir:
Na descrição da MT M a seguir, o śımbolo ′?′ representa que qualquer śımbolo pode ter sido lido naquela
transição ou que o śımbolo original foi mantido na escrita. O śımbolo ′v′ indica um branco na fita.
M = ({q0, q1, q2, qa, qr}, {a, b}, {a, b, v, x}, δ, q0, qa, qr), onde: δ(q0, a, v) = (q1, a, b,D,D), δ(q0, b, ?) = (q0, b, ?, D, P ),
δ(q0, v, v) = (q2, x, x, E,E), δ(q1, a, ?) = (q0, a, ?, D, P ), δ(q1, v, ?) = (qr, v, ?, P, P ), δ(q2, a, ?) = (q2, x, ?, E, P ),
δ(q2, b, b) = (q2, x, x, E,E), δ(q2, x, x) = (qa, x, x, P, P ), δ(q2, x, b) = (qr, x, b, P, P ), δ(q2, b, x) = (qr, b, x, P, P ).
A = {anbn|n ≥ 0}
B = {a2nbn|n ≥ 0}
C = {w ∈ {a, b}∗|i = 2j, onde i é o número de as ej é o número de bs}
D = {w ∈ {a,b}∗| se o número de bs é n, então o número de as é m = 2n e n ≥ 1}
a) L(M) = A
b) L(M) = B
c) L(M) = C ←
d) L(M) = D
e) Nenhuma das outras alternativas é correta.
Page 4