Exercícios
Capítulo 3 – A Tese de Church-Turing
Sipser – Introdução à Teoria da Informação
Erick Vagner Cabral
Igor Lucena
Vitor Baptista
Exercicío 3.1
 d) 000
Exercicío 3.2
 a)
Exercicío 3.4
 Definindo um Enumerador:
7-upla (Q, ∑, Γ, δ, q0 , qaceita, qimprime)
δ: QxΓ
Q x Γ x {E,D} x ∑€
FITA DE IMPRESSÃO
FITA DE TRABALHO
mt
abbba
δ define se a cada passo, escreverá na fita de impressão
δ(q0, a) = (q1,a, R, m)
δ(q1, b) = (qprint,a, R, t)
Sempre que entrar no qimprime, “limpa” a fita de impressão
e volta o cabeçote da fita de impressão para o inicio
Pará quando entrar no qaceita
Exercício 3.6
 Definição válida para enumerador?
E = “Ignore a entrada
1. Repita o que se segue para i = 0,1,2,...
2. Rode M sobre si.
3. Se ela aceita, imprime si.”
Se M entrar em loop para uma certa entrada si?
E nunca irá testar as entradas posteriores à si(si+1, si+2, ...).
Logo o enumerador irá falhar para L(M).
Exercício 3.7
 Por que não é legítima?
M = “A entrada é um polinômio p sobre as x1, x2,..., xk ”
1. Tente todas as possíveis valorações de x1, x2,..., xk para valores
inteiros.
2. Calcule o valor de p sobre todas essas valorações.
3. Se alguma dessas valorações torna o valor de p igual a 0, aceite;
caso contrário, rejeite.”
- Não é uma descrição legítima.
- O erro está no fato de que uma sequencia x1, x2,..., xn tem um
conjunto infinito de possibilidades. E em uma MT é necessário que
possamos descrever cada estágio em uma sequencia finita de
passos.
Problema 3.9
 Seja um k-AP um autômato de pilha que tem k pilhas.
Portanto, um 0-AP (AFN) < 1-AP (AP convencional).
a) 2-AP’s são mais poderosos que 1-AP’s?
Resposta:
Seja A = {an bn cn | n ≥ 0} , pelo lema do bombeamento,
provamos um autômato de pilha não é capaz de reconhecer
essa linguagem.
Já se temos 2 pilhas podemos reconhecer essa linguagem
facilmente, fazendo os seguintes passos.
Problema 3.9
cont. 2-AP’s são mais poderosos que 1-AP’s?
A = {an bn cn | n ≥ 0}
-Empilha todos os a’s que aparecerem no
a)
começo da cadeia na Pilha A.
-Empilha todos os b’s que aparecerem
após os a’s na pilha B.
-Lembre-se da ordem! Se aparecer algum
a enquanto estava empilhando b’s. REJEITA.
-Por fim, a partir do primeiro c visto,
Desempilha um a e um b para cada c.
-Se restar algum a ou algum b. REJEITA.
- Se as pilhas A e B estão vazias no fim, ACEITA.
Pilha A
Pilha B
Problema 3.9
cont. 2-AP’s são mais poderosos que 1-AP’s?
-EXEMPLO: w = aabbcc
A = {an bn cn | n ≥ 0}
a)
ACEITA!
a
b
a
b
Pilha A
Pilha B
Problema 3.11
Para provarmos que uma MT M com fita duplamente infinita é
semelhante a uma MT comum, basta provarmos que
podemos simular uma MT comum em uma MT com fita
duplamente infinita.
... a b a a b b b ...
Problema 3.11
Podemos simular uma MT com fita duplamente infinita,
utilizando uma MT com 2-fitas, que é equivalente a uma MT
comum.
a b a b a a ...
M
...
A idéia é separar a fita duplamente infinita em 2 partes.
Problema 3.12
 Máquina de Turing com reinicialização à esquerda.
δ: QxΓ
Q x Γ x {D, REINICIA}
Para provarmos que uma MT M com reinicialização
reconhecem a classe de linguagens Turing-recinhecíveis, basta
provarmos que podemos simular uma MT comum em uma
MT com reinicialização à esquerda.
Problema 3.12
 Máquina de Turing com reinicialização à esquerda.
δ: QxΓ
Prova:
Q x Γ x {E, D}
a a b b c c a b a ...
FITA MT COMUM
Problema 3.12
 Máquina de Turing com reinicialização à esquerda.
δ: QxΓ
Prova:
Q x Γ x {D, REINICIA}
.
a a b b c c a b a ...
FITA MT REINICIA
Problema 3.13
Essa variação da máquina de turing pode ser simulada por um
autômato finito não-determinístico.
Assim como os autômatos essa variante não pode tornar a ler
símbolos que já foram lidos. A leitura do próximo símbolo
é equivalente a andar para a direita. A ação de permanecer
no mesmo local pode ser simulada pelos movimentos
vazios que podem ocorrer nesses autômatos e dispensam a
leitura do próximo símbolo.
Problema 3.15 – Turing-Decidíveis
Concatenação
Para quaisquer 2 linguagens decidíveis L1 e L2 , sejam M1 e M2
MT’s que as decidem. Contruímos uma MT M’ que decide
a concatenação de L1 e L2:
“Sobre a entrada w:
1. Dividir w em 2 partes w1, w2 para cada combinação.
2. Rode M1 sobre w1
3. Rode M2 sobre w2
4. Se as duas aceitarem. Aceite. Continue com os próximos w1
, w2
5. Se todos foram testados sem obter sucesso, Rejeite.
b)
Problema 3.16 – Turing-Reconhecíveis
Concatenação
Para quaisquer 2 linguagens Turing-Reconhecíveis L1 e L2 , sejam M1 e M2 MT’s
que as reconhecem. Contruímos uma MT M’ que reconhece a concatenação
de L1 e L2:
“Sobre a entrada w:
1.
Dividir w em 2 partes w1, w2 para combinação escolhida nãodeterminiscamente.
2.
Rode M1 sobre w1, se parar e rejeitar, Rejeite. Se aceitar, Aceite e vá para o
próximo passo.
3.
Rode M2 sobre w2, se parar e rejeitar, Rejeite. Se aceitar, Aceite.
b)
OBS:
- M’ aceitará porque chega a seu estado de aceitação após um número finito
de passos.
- Se uma delas entrarem em loop, M’ entrará em loop.
Problema 3.15 – Turing-Decidíveis
DICAS:
c) Estrela
Dica: w = w1, w2, ..., wn
Se aceitar à cada w, no término aceitará.
d) Complementação
Roda M. Então se M aceita, REJEITE, Se M rejeitar, ACEITE.
e) Intersecção
Só aceitará se M1 e M2 ambos aceitarem.