Grupo07IS17
sábado, 26 de abril de 2008,6:16
MT que comprueba el orden ascendente de los bloques de 0's
Máquina de Turing "clásica"

Dada una cadena de (0+1)*. La máquina indica si los bloque de ceros están ordenados por orden creciente. Por ejemplo, debe aceptar la siguiente entrada:
...B00100100010000001000000000B...

y rechazar la siguiente:
...B000001000000100B...

ya que el segundo bloque tiene 6 ceros y el tercero tiene menos, sólo 2 ceros.

0

1

B

$

X

q0

(q1, B, R)


(q2, 0, L)



q1

(q1, 0, R)

(q1, 1, R)

(q0, $, R)



q2

(q2, 0, L)

(q2, 1, L)

(q3, B, R)

(q2, $, L)


q3

(q4, B, R)

(q5, B, R)


(q12, B, R)


q4

(q4, 0, R)

(q4, 1, R)

(q2, 0, L)

(q4, $, R)


q5

(q6, X, R)

(q9, 1, R)




q6

(q6, 0, R)

(q6, 1, R)

(q7, B, L)

(q6, $, R)


q7

(q8, B, L)



(q10, $, L)


q8

(q8, 0, L)

(q8, 1, L)


(q8, $, L)

(q5, X, R)

q9

(q9, 0, R)

(q9, 1, R)

(q10, B, L)

(q10, $, R)


q10

(q10, 0, L)

(q10, 1, L)


(q10, $, L)

(q11, 0, L)

q11



(q3, B, R)


(q11, 0, L)

q12

(q12, B, R)


(q13, B, L)



q13









Máquina de Turing Multicabezal

MT que hace el mismo trabajo que la MT anterior pero con multicabezal. Se utilizan dos cabezales; el primero de ellos es el encargado de ir recorriendo la cadena que se tiene que comprobar y el segundo irá copiando bloques de 0's para ir comparando con el primer cabezal si el orden es el correcto.


{0, 0}

{0, 1}

{0, B}

{1, B}

{B, B}

q0

(q0,

{0, Z},
{0, R})

(q0,
{0, Z},

{1, R})

(q1,
{0, Z},

{B, R})



q1



(q1,

{B, R}, {0, R})

(q2,

{1, R},
{B, L})

(q4,

{B, Z}, {B, Z})

q2

(q2,
{0, R},

{B, L})


(q3,

{0, L},
{B, R})

(q3,

{1, L},
{B, R})


q3



(q3,
{0, L},
{B, Z})

(q1,
{B, R}, {B, Z})


q4








 
Posteado por: Jon o Jon Ander (según persona) Link ~


1 Opiniones:


Publicar un comentario ~ Atrás