Grupo07IS17

lunes, 28 de abril de 2008,10:17

Generador de L={a^n b^2n a^n, con n>=0}

Hemos utilizado una M.t. modificada multicinta, con 2 cintas, en la primera se encuentra la cinta de entrada, en la segunda se generan las cadenas correspondientes al lenguaje L, el cual queremos conseguir.

En la cadena de entrada sólo recibiremos cadenas de 0´s, recorreremos el primer cabezál hasta encontrar un blanco (B), mientras por cada 0 que leamos escribiremos una (a), en la cinta de salida. Luego volvemos a recorrer la cadena hacia atras escribiendo 2 b´s, por cada 0 que encontramos, para ello utilizamos los estados q1 y q2. Para finalizar, cuando encontremos un blanco (B), volceremos a escribir en la cinta de salida a`s hasta encontrarnos al la derecha de la cadena de entrada una B, (blanco). Por finalizar escribiremos una almoadilla (#), en la cinta de salida para dejarla preparada para generar la siguiente cadena.

Aquí dejamos la tabla de transiciones de esta M.T. generadora:

	{0,B}	{B,B}
q₀	(q₀, {0,R}, {a,R})	(q₁, {B,L}, {B,Z})
q₁	(q₂, {0,Z}, {b,R})	(q₃, {B,R}, {B,Z})
q₂	(q₁, {0,L}, {b,R})
q₃	(q₃, {0,R}, {a,R})	(q₄, {B,R}, {#,R})
q₄

Posteado por: Natxo

Link ~ 1 Opiniones

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
q₀	(q₁, B, R)		(q₂, 0, L)
q₁	(q₁, 0, R)	(q₁, 1, R)	(q₀, $, R)
q₂	(q₂, 0, L)	(q₂, 1, L)	(q₃, B, R)	(q₂, $, L)
q₃	(q₄, B, R)	(q₅, B, R)		(q₁₂, B, R)
q₄	(q₄, 0, R)	(q₄, 1, R)	(q₂, 0, L)	(q₄, $, R)
q₅	(q₆, X, R)	(q₉, 1, R)
q₆	(q₆, 0, R)	(q₆, 1, R)	(q₇, B, L)	(q₆, $, R)
q₇	(q₈, B, L)			(q₁₀, $, L)
q₈	(q₈, 0, L)	(q₈, 1, L)		(q₈, $, L)	(q₅, X, R)
q₉	(q₉, 0, R)	(q₉, 1, R)	(q₁₀, B, L)	(q₁₀, $, R)
q₁₀	(q₁₀, 0, L)	(q₁₀, 1, L)		(q₁₀, $, L)	(q₁₁, 0, L)
q₁₁			(q₃, B, R)		(q₁₁, 0, L)
q₁₂	(q₁₂, B, R)		(q₁₃, B, L)
q₁₃

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}
q₀	(q₀, {0, Z}, {0, R})	(q₀, {0, Z}, {1, R})	(q₁, {0, Z}, {B, R})
q₁			(q₁, {B, R}, {0, R})	(q₂, {1, R}, {B, L})	(q₄, {B, Z}, {B, Z})
q₂	(q₂, {0, R}, {B, L})		(q₃, {0, L}, {B, R})	(q₃, {1, L}, {B, R})
q₃			(q₃, {0, L}, {B, Z})	(q₁, {B, R}, {B, Z})
q₄

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

Link ~ 1 Opiniones

,5:35

MT que calcula los bloques de 0's

Máquina de Turing "clásica"

Dada una cadena de (0+1)^*. La máquina debe indicar cuántos bloques de 0's hay. Por ejemplo, ante la siguiente entrada:

...B0001001001000100B...
debe obtener como salida
...B00000B...
ya que se le han pasado 5 argumentos en la cadena de entrada.

	0	1	B	X
q₀	(q₀, 0, R)	(q₁, X, R)	(q₄, B, L)
q₁	(q₁, 0, R)	(q₁, 1, R)	(q₂, B, R)
q₂	(q₂, 0, R)		(q₃, 0, L)
q₃	(q₂, 0, L)	(q₂, 1, L)		(q₀, X, L)
q₄	(q₄, B, L)	(q₄, B, L)	q₅
q₅

Máquina de Turing Multicinta

MT que calcula al igual que la anterior los bloques de 0's pero con una MT multicinta. Se utiliza una cinta de lectura que leerá la cadena que se le pasa y una cinta de salida para escribir el resultado del calculo.

	{0, B}	{1, B}	{B, B}
q₀	(q₁, {B, R}, {0, R})		(q₃, {B, R}, {B, R})
q₁	(q₁, {B, R}, {B, Z})	(q₀, {B, R}, {B, Z})	(q₃, {B, R}, {B, R})
q₂

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

Link ~ 1 Opiniones

jueves, 17 de abril de 2008,11:31

Lo que estamos haciendo esta semana

Vamos a ser buenos alumnos y a decir que estamos en paro, otras asignaturas nos han bombardeado a trabajos y ejercicios.

Lo único que hemos visto después de una reflexionada, meditada y saludable reflexión (después de tomarse una cerveza) fue mirarnos la explicación que nuestro compañero '...' dió de la máquina de Turing multicinta, pues creemos que no ha quedado demasiado claro.

Esto fue lo que miramos. Si es que... Si la profe talf hasta lo tenia publicado, tanto costaba en explicar esto.

Etiquetas: Agobio

Posteado por: Natxo

Link ~ 0 Opiniones

domingo, 13 de abril de 2008,5:12

Resumen Semanal

Esta semana la hemos dedicado a hacer el ejercicio de los divisores de N.
El trabajo lo hemos dividido en varios días.

El primer día lo dedicamos a debatir el diseño de la máquina de turing, es decir, como podíamos diseñar la MT para obtener los divisores de un número dado N, los movimientos que debía seguir el cabezal, como era la cinta de entrada y como debía acabar la cinta, etc.
El segundo día (el que más curro nos pegamos) lo dedicamos a realizar la tabla de estados de la MT con un solo cabezal y con una sola cinta. La verdad nos resulto más complicado de lo que nosotros pensábamos en un principio y más costoso en horas de trabajo, como que acabamos con la cabeza como un bombo.
El tercer y último día, lo dedicamos a hacer la tabla de estados para la MT multicabezal. Tomamos la decisión de diseñarla con tres cabezales de lectura/escritua. En un principio nos costo un poco acabar de entender como funcionaba y como teniamos que hacer la tabla, lo cual contribuyó a unos dolores de cabeza bastante agudos. Una vez le cogimos el punto a los cabezales completamos la tabla sin demasiados problemas y en menos tiempo de lo esperado.

Como conclusión, decir que el diseño de la MT con multicabezal se realiza en mucho menos tiempo que la MT normal y resulta mas eficiente.

SalU2.

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

Link ~ 1 Opiniones

sábado, 12 de abril de 2008,5:19

MT que obtiene los DIVISORES de N

MT normal

Esta es la Máquina de Turing que calcula los divisores de un número dado N con un solo cabezal y una sola cinta.

	0	1	B	$	X	Y
q₀	(q₁, 0, L)
q₁			(q₂, $, R)
q₂	(q₂, 0, R)		(q₃, $, L)
q₃	(q₄, X, L)			(q₅, $, L)
q₄	(q₅, X, L)			(q₅, $, L)
q₅	(q₅, 0, L)		(q₁₀, B, R)	(q₆, $, L)
q₆	(q₆, 0, L)		(q₇, 0, R)
q₇	(q₇, 0, R)			(q₇, $, R)	(q₃, X, L)
q₈	(q₈, 0, L)		(q₉, B, R)
q₉	(q₁₀, B, R)
q₁₀	(q₁₁, Y, R)			(q₁₅, $, L)
q₁₁	(q₁₁, 0, R)			(q₁₂, $, R)
q₁₂	(q₁₃, 0, L)			(q₁₃, $, L)	(q₁₂, X, R)
q₁₃				(q₁₆, $, R)	(q₁₄, 0, L)
q₁₄	(q₁₄, 0, L)			(q₁₄, $, L)	(q₁₄, X, L)	(q₁₀, 0, R)
q₁₅	(q₁₅, 0, L)		(q₁₀, B, R)
q₁₆	(q₁₆, 0, R)	(q₁₆, 1, R)	(q₁₇, 0, L)	(q₁₆, $, R)
q₁₇	(q₁₇, 0, L)	(q₁₇, 1, L)	(q₂₁, B, R)	(q₁₇, $, L)	(q₁₇, X, L)	(q₁₈, 0, R)
q₁₈	(q₁₆, Y, R)			(q₁₉, $, R)
q₁₉	(q₁₉, X, R)			(q₂₀, $, R)
q₂₀	(q₂₀, 0, R)		(q₁₇, 1, L)
q₂₁	(q₂₂, 0, R)
q₂₂				(q₂₃, B, R)
q₂₃				(q₂₄, 1, R)	(q₂₃, 0, R)
q₂₄

MT multicabezal

Esta es la Máquina de Turing que calcula los divisores de un número dado N utilizando 3 cabezales de lectura/ escritura. El uso de cada cabezal es el siguiente: el primero de ellos será el encargado de probar los divisores de N, empezando desde N/2 hasta 1. El segundo de ellos será el que vaya recorriendo N para comprobar si es divisor el número que se está probando. El tercer y último cabezal será el que escriba el divisor si corresponde.

	0	1	B	$
q₀	(q₀, {0, L}, {0, Z}, {0, R})		(q₁, {$, L}, {B, Z}, {$, R})
q₁	(q₂, {0, Z}, {0, R}, {0, Z})			(q₃, {$, Z}, {$, L}, {$, Z})
q₂	(q₁, {0, Z}, {0, R}, {0, Z})		(q₁, {0, L}, {B, Z}, {B, Z})	(q₃, {$, Z}, {$, L}, {$, Z})
q₃	(q₃, {0, R}, {0, L}, {0, Z})		(q₃, {B, R}, {B, Z}, {B, Z})	(q₄, {$, L}, {$, Z}, {$, Z})
q₄	(q₄, {0, L}, {0, L}, {0, Z})		(q₃, {B, R}, {B, Z}, {B, Z})	(q₅, {$, Z}, {$, R}, {$, Z})
q₅	(q₅, {0, R}, {0, Z}, {0, Z})		(q₅, {B, R}, {B, Z}, {0, R})	(q₆, {$, L}, {$, Z}, {1, R})
q₆	(q₆, {0, L}, {0, Z}, {0, Z})		(q₇, {B, R}, {B, Z}, {B, Z})
q₇	(q₈, {B, R}, {0, Z}, {0, Z})		(q₇, {B, Z}, {B, Z}, {B, Z})	q₉
q₈	(q₈, {0, Z}, {0, R}, {0, Z})			(q₃, {$, Z}, {$, L}, {$, Z})
q₉

En conclusión, un curro de la leche! xD

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

Link ~ 0 Opiniones