TCOMP Lista 01

Prévia do material em texto

Teoria da Computabilidade
Lista de Exercícios 1
Prof. Werton Araujo
30/07/2019
1. Dê a definição formal de máquina de Turing, descrevendo detalhadamente cada elemento da tupla.
2. Considere a máquina de Turing definida por M = ({q0, q1, q2, q3, qA, qR}, {0, 1}, {0, 1, X, Y,␣}, δ, q0, qA, qR),
onde δ é dada na tabela abaixo (por simplicidade, as transições para o estado de rejeição não são mostradas).
Desenhe o diagrama de estados equivalente a essa tabela.
Estado 0 1 X Y ␣
q0 (q1, X,D) – – (q3, Y,D) –
q1 (q1, 0, D) (q2, Y, E) – (q1, Y,D) –
q2 (q2, 0, E) – (q0, X,D) (q2, Y, E) –
q3 – – – (q3, Y,D) (qA,␣, D)
3. Considere a máquina de Turing definida por M = ({q1, . . . , q14, qA, qR}, {0, 1,#}, {0, 1,#, x,␣}, δ, q1, qA, qR),
onde δ é dada na tabela abaixo (por simplicidade, as transições para o estado de rejeição não são mostradas).
Estado 0 1 # x ␣
q1 (q2, x,D) (q3, x,D) (q8,#, D) – –
q2 (q2, 0, D) (q2, 1, D) (q4,#, D) – –
q3 (q3, 0, D) (q3, 1, D) (q5,#, D) – –
q4 (q6, x, E) – – (q4, x,D) –
q5 – (q6, x, E) – (q5, x,D) –
q6 (q6, 0, E) (q6, 1, E) (q7,#, E) (q6, x, E) –
q7 (q7, 0, E) (q7, 1, E) – (q1, x,D) –
q8 – – – (q8, x,D) (qA,␣, D)
Dê a sequência de configurações pelas quais essa máquina passa quando recebe as cadeias
a) 1##1.
b) 10#11.
c) 10#10.
4. Construa uma máquina de Turing que efetue a conjunção lógica (operação AND) de dois dígitos binários,
dados nas duas primeiras posições da fita. Dê a descrição formal dessa máquina, usando uma tabela ou um
diagrama para a função de transição.
5. Construa uma máquina de Turing que desloque a cadeia de entrada uma posição à esquerda, descartando o
primeiro símbolo. Dê sua descrição formal, usando uma tabela ou um diagrama para a função de transição.
O alfabeto de entrada é {0, 1} e comprimento da cadeia de entrada é no mínimo 2.
6. Dê a definição formal da função de transição δ para uma máquina de Turing
a) cujo cabeçote pode não se mover quando ocorre uma transição.
b) com k fitas.
c) não determinística.
7. Explique a razão pela qual uma máquina de Turing com múltiplas fitas e uma máquina de Turing não
determinística são equivalentes em poder a uma máquina de Turing determinística com uma única fita.
1
8. Dê a definição formal de enumerador, descrevendo detalhadamente cada elemento da tupla.
9. Dê uma definição informal de máquina de Turing universal.
10. Descreva cada elemento da tupla geralmente utilizada para representar uma transição da máquina de Turing.
11. Usando a notação de Turing, converta em uma cadeia de símbolos a descrição da máquina de Turing com
Σ = {0, 1} que
a) troca todos os 0s e 1s por brancos.
b) troca 0s por 1s e 1s por 0s.
12. Considere as linguagens definidas abaixo:
I. AAFD = {〈B,w〉 | B é um AFD que aceita a cadeia w}.
II. EAFD = {〈A〉 | A é um AFD e L(A) = ∅}.
III. AExR = {〈R,w〉 | R é uma expressão regular que gera a cadeia w}.
IV. EQGLC = {〈G,H〉 | G e H são GLCs e L(G) = L(H)}.
V. AMT = {〈M,w〉 |M é uma MT e M aceita a cadeia w}.
São decidíveis somente as linguagens definidas em
a) I, III e V.
b) II e IV.
c) I, II e III.
d) IV e V.
13. Desenhe um gráfico mostrando a relação entre as linguagens regulares, as linguagens livres do contexto, as
linguagens decidíveis, as linguagens Turing-reconhecíveis e todas as linguagens.
14. O teorema 4.22 do livro-texto prova que uma linguagem é decidível quando essa linguagem e seu complemento
são Turing-reconhecíveis. Com base nesse teorema, mostre que existem linguagens Turing-irreconhecíveis.
15. Dê um exemplo de uma linguagem que, da mesma forma que AMT, seja Turing-irreconhecível.
2