Teoria da Computação aula 10

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Máquinas de Turing 
exercícios 
Remis Balaniuk
*
*
Desenhe no JFLAP a seguinte MT
L = {anbn | n ≥1}
*
*
*
Desenhe no JFLAP a seguinte MT
Qual a linguagem que ela reconhece?
*
*
Implemente as seguintes MTs
Faça uma MT que substitua todos os 0s de uma cadeia de 0s e 1s por 1s e todos os 1s por 0s. 
Obs.: A MT trabalha com os símbolos 0, 1 e quadrado vazio.
Faça uma MT que aceite o conjunto de todas as cadeias de 0s e 1s contendo pelo menos um 1.
*
*
Implemente as seguintes MTs
Faça uma MT que aceite o conjunto de cadeias não vazias de parênteses bem balanceados.
( ( ) ( ( ) )) é bem balanceado
( ( ) ( ( ) ) não é bem balanceado
Faça uma MT que soma uma unidade a um número binário qualquer
*
*
MT como calculadoras
Até agora usamos as máquinas de Turing somente como aceitadores de linguagem.
É também importante usar estas máquinas como dispositivos que computam funções numéricas, isto é, que mapeiam Nk N. 
Iremos então codificar o conjunto dos números naturais na notação unária: 
Então o código para 0 é 1, o código para 1 é 11, 2 é 111, 3 é 1111, etc. 
Escreve-se n^ para simbolizar o n codificado em unário.
*
*
MT como calculadoras
Dada uma máquina de Turing sobre um alfabeto que inclui o símbolo 1, pode-se dizer como interpretar o comportamento de uma máquina de Turing tal que ela possa ser pensada como um dispositivo que computa uma função numérica. 
 Descrição instantânea inicial para computar fk(n1, ..., nk):
... B q0 1 1 1 ... 1 B 1 ... 1 1 1 B .... B 1 ... 1 1 1 1 B ...
 <- n1 + 1 -> <-- n2 + 1 --> <--- nk + 1 --->
*
*
MT como calculadoras
Uma máquina de Turing M computa uma função jM (k) de aridade k como se segue:
Na entrada (n1, ..., nk), n1, ..., nk são colocados na fita de M em unário, separados por brancos simples 
A cabeça de M é colocada sobre o 1 mais a esquerda de n1^, e o controle de estados finitos de M é colocado em q0. 
Em outras palavras, M tem DI inicial
q0n1^Bn2^B ... Bnk^
Se e quando M terminar o processamento, os 1’s na fita são contados (eles podem não aparecer em um bloco) e seu total é o valor de fk(n1, ..., nk)
Note que se a MT não mudar nada da entrada então f1(n1)=n1+1 (função sucessora) e f2(n1,n2)=n1+n2+2 
Se M nunca pára, diz-se que fk(n1, ..., nk) é indefinido. 
Refere-se a fk como a (k-ésima) semântica de M.
*
*
MT como calculadoras
Exemplo:
Faça uma MT que calcule a subtração de dois números M – N, sendo que a fita se encontra em situação padrão. 1M+1B1N+1 
Solução: 
δ(q0,1)=(q0,1,R)
δ(q0,B)=(q1,B,R)
δ(q1,1)=(q1,1,R)
δ(q1,B)=(q2,x,L)
δ(q2,1)=(q2,1,L)
δ(q2,B)=(q3,B,R)
δ(q3,1)=(q4,B,L)
δ(q4,B)=(q4,B,L)
δ(q4,1)=(q5,B,R)
δ(q5,B)=(q5,B,R)
δ(q5,1)=(q4,B,L)
δ(q5,x)=(qa,B,R)
*
*
Implemente as seguintes MTs
Especifique uma máquina de Turing que calcule a função assim definida f (n) = 2n.
Construa uma máquina de Turing que calcule a função , definida por g(n) = n (mod 3) (resto da divisão inteira de n por 3).
Faça uma MT que calcule a divisão de dois números M / N