Exercícios sobre decidibilidade do 2º/2012

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 6
No Problema da Correspondeˆncia de Post Bobo (PCPB), em cada domino´, a cadeia superior tem
o mesmo comprimento que a cadeia inferior. Mostre que PCPB e´ decid´ıvel.
Resposta: Seja P =
{[
t1
b1
]
,
[
t2
b2
]
, . . .
[
tk
bk
]}
um conjunto de domino´s, com |ti| = |bi| para
i = 1, 2, . . . , k. Para formar um emparelhamento, o domino´ inicial devera´ ter a mesma cadeia
na parte superior e na parte inferior. Ao mesmo tempo, se P possui um domino´ com a mesma
cadeia na parte superior e na inferior, esse domino´ constitui um emparelhamento trivial (com
uma u´nica pec¸a). Podemos construir, enta˜o, o seguinte decisor para PCBP:
U= “Sobre a entrada 〈P 〉, onde P e´ um conjunto de domino´s [ ti
bi
], com i = 1, 2, . . . , k,
e |ti| = |bi|:
1. Se ti = bi para algum i, aceite; se na˜o, rejeite.
Prove que a linguagem EQGLC = {〈G1, G2〉| G1 e G2 sa˜o grama´ticas livre-do-contexto e L(G1) =
L(G2)} e´ indecid´ıvel. Dica: fac¸a uma reduc¸a˜o a partir da linguagem indecid´ıvel TODASGLC =
{〈G〉| G e´ uma grama´tica livre-do-contexto e L(G) = Σ∗}
Resposta: Suponha que EQGLC e´ decid´ıvel, e que R e´ um decisor para EQGLC. Podemos
construir, enta˜o, o seguinte decisor para TODASGLC:
U= “Sobre a entrada 〈G〉, onde G e´ uma grama´tica livre-do-contexto:
1. Construa uma grama´tica livre-do-contexto G′ tal que L(G′) = Σ∗.
2. Rode R sobre 〈G,G′〉.
3. Se R aceita, aceite; se R rejeita, rejeite.
Como sabemos que TODASGLC e indecid´ıvel, a ma´quina de Turing U na˜o pode ser constru´ıda.
Conclu´ımos, enta˜o, que R na˜o existe e EQGLC e´ indecid´ıvel.
Fornec¸a uma ma´quina de Turing que decida a linguagem AALL = {〈M,w〉| M e´ um autoˆmato
linearmente limitado que aceita a cadeia w}.
Resposta:
U= “Sobre a entrada 〈M,w〉, onde M e´ um autoˆmato linearmente limitado e w e´ uma
cadeia:
1. Simule M sobre w por um ma´ximo de qngn passos, onde q e´ a quantidade de
estados de M , n e´ o comprimento da fita e g e´ a quantidade de s´ımbolos no
alfabeto de fita.
2. Se M aceita, aceite; se R rejeita, rejeite. Se M na˜o parou, rejeite.
Prove que EQGLC e´ co-Turing-reconhec´ıvel. Pode usar o fato de que AGLC e´ decid´ıvel.
Resposta: A seguinte ma´quina de Turing reconhece EQGLC:
U= “Sobre a entrada 〈G1, G2〉, onde G1 e G2 sa˜o grama´ticas livre-do-contexto:
1. Gere cadeias wi ∈ Σ
∗, onde i = 1, 2, . . ., em ordem lexicogra´fica. Para cada wi:
1. Teste se wi ∈ L(G1) e se wi ∈ L(G2), usando o decisor para AGLC.
2. Se o decisor aceita um dos testes e rejeita o outro, aceite.
Seja a ma´quina de Turing M :
q0 qaceita
⊔ → 0,D
com Σ = {0, 1} e Γ = {0, 1,⊔}, e a cadeia w = ε. A partir M e w, e usando o algoritmo visto em
aula, construa um conjunto de domino´s para o problema da correspondeˆncia de Post modificado
(PCPM) e mostre que existe um emparelhamento. Atenc¸a˜o: no conjunto de domino´s, inclua
todas as pec¸as que o algoritmo gera, mesmo aquelas que na˜o sera˜o utilizadas no emparelhamento.
Resposta:
P =
{[
#
#q0 ⊔#
]
,
[
q0⊔
0qaceita
]
,
[
0
0
]
,
[
1
1
]
,
[⊔
⊔
]
,
[
#
#
]
,
[
#
⊔#
]
,
[
0qaceita
qaceita
]
,
[
qaceita0
qaceita
]
,
[
1qaceita
qaceita
]
,
[
qaceita1
qaceita
]
,
[
⊔qaceita
qaceita
]
,
[
qaceita⊔
qaceita
]
,
[
qaceita##
#
]}
O emparelhamento e´
[
#
#q0 ⊔#
] [
q0⊔
0qaceita
] [
#
#
] [
0qaceita
qaceita
] [
#
#
] [
qaceita##
#
]
Prove que TODASGLC e´ co-Turing-reconhec´ıvel. Pode usar o fato de que AGLC e´ decid´ıvel.
Resposta: A seguinte ma´quina de Turing reconhece TODASGLC:
U= “Sobre a entrada 〈G〉, onde G e´ uma grama´tica livre-do-contexto:
1. Gere cadeias wi ∈ Σ
∗, onde i = 1, 2, . . ., em ordem lexicogra´fica. Para cada wi:
1. Teste se wi ∈ L(G), usando o decisor para AGLC.
2. Se o decisor rejeita, aceite.