Ejercicio Maquina de Turing 3

Cíclicas o iterativos

Elementos:

                Q=(0,1,A,B)

                =(a,b,B)   entrada à cinta

                M=|x,R)    graba à  memoria

                SP=|R)

∆	(a,B)	(b,B)	(a,a)	(a,b)	(B,a)	(b,b)	(B,B)	(b,b)
0	(A,R)	(B,R)	ᶿ	ᶿ	ᶿ	ᶿ	(1, ᴫ)	ᶿ
A	ᶿ	ᶿ	(A,R)	ᶿ	(1,ᴫ)	ᶿ	ᶿ	ᶿ
B	ᶿ	ᶿ	ᶿ	(A,R)	ᶿ	(B, ᴫ)	ᶿ	(1, ᴫ)
1	ᶿ	ᶿ	ᶿ	ᶿ	ᶿ	ᶿ	ᶿ	ᶿ

Expresiones:

aB

bB                                                          (a,b)B  L()=((abB) B/n ≥0)

B

aBaBB

Ejercicio Maquina de Turing 2

• DISEÑAR UNA MAQUINA DE TURING QUE CALCULA EL NUMERO CONSECUTIVO DE UN NUMERO DADO EN BINARIO

Vamos a considerar tres estados:

$$q_0,q_1,q_2$$

• Inicialmente, la MT está en el estado q₀ con la cabeza señalando la primera cifra del número.
  La MT recorre todo el número para ver si es par o impar sin modificar su cinta.
  
  $$\delta (q_0,0)=(q_0,0,R)$$
  $$\delta (q_0,1)=(q_0,1,R)$$
• Notemos que, por ahora, la MT se detiene al llegar al primer símbolo en blanco a la derecha del número.
  La MT vuelve a la anterior casilla (último número). Si es un 0, lo cambia por un 1 y pasa al estado final que es q₂ . Para hacer esto usaremos el estado q₁ :
  
  $$\delta (q_0,B)=(q_1,B,L)$$
  $$\delta (q_1,0)=(q_2,1,R)$$
• Si el número es impar, la MT no ha cambiado el último número, pero está en el estado q₁ . Tiene que cambiar todos los 1's consecutivos que haya de derecha a izquierda.
  
  $$\delta (q_1,1)=(q_1,0,L)$$
• Por ahora, la MT se para cuando llega al primer 0 (de derecha a izquierda) ó en un símbolo en blanco. Si es un 0, lo cambia por un 1 y el proceso finaliza:
  
  $$\delta (q_1,0)=(q_2,1,L)$$
  (Hemos escrito un desplazamiento a la izquierda, pero esto no tiene importancia ya que la MT ha llegado al estado final).
• Si lo que señala la cabeza es un blanco en vez de un 1, tiene que cambiarlo por un 1 y finalizar el proceso.
  
  $$\delta (q_1,B)=(q_2,1,L)$$

El diagrama de la máquina es

Ejercicio Maquina de Turing

DISEÑAR UNA MAQUINA DE TURING QUE ACEPTE EL LENGUAJE

L={0n1n :n>0}Lo primero que haremos es limitar el alfabeto a

$$\Sigma =\{0,1\}$$

así nos aseguramos de que sólo puede aceptar palabras con de entrada con símbolos 1 y 0.
Los símbolos de cinta serán

$$T=\{0,1,B,X,Y\}$$

siendo B el símbolo en blanco.
La MT consta de cinco estados:

$$q_0,q_1,q_2,q_3,q_4$$

Los estados q₀ y q₄ son el inicial y el final, respectivamente.
Inicialmente, la cabeza señala el primer 0. Lo cambia por X y se desplaza a la derecha en busca del primer 1 para cambiarlo por Y:

$$\delta (q_0,0)=(q_1,X,R)$$

$$\delta (q_1,0)=(q_1,0,R)$$

Es decir, mientras haya 0's, se mantiene en el estado q₁ .

$$\mathrm{abrá\; cambiado\; por Y ).\; La\; MT\; se\; quedará\; permanentemente\; en\; el\; estado q1 .}$$