lunes, 26 de mayo de 2008,9:40
T.A.L.F productions presenta... La última tarea
a:
Es imposible. Principalmente por que hay infinitos códigos de máquinas de Turing, lo cual nos hace llegar a la conclusión de que nunca tendríamos todos los códigos. Aunque tubiéramos un generador de códigos de MT's que luego se lo pasáramos a una MT que acabara diciéndonos que si que pertenece a un código de MT, esto nos llevaría a decir que al menos existe un código más que pertenece a este conjunto. Por ejemplo, podemos empezar a numerar en orden canónico los enteros positivos, hasta que lleguemos al infinito, pero seguro que existirá un entero positivo mayor que el ultimo que tenemos y que también pertenecerá a ese conjunto.
b:
Nuestra opinión es que la respuesta B es la correcta, nunca tendremos suficientes códigos, (nos sustentamos en la pregunta A), aunque seguramente también pensaría la C, solo por fastidiar y tal.
Etiquetas: tareas
viernes, 16 de mayo de 2008,5:26
Lenguajes diagonales
Aquí os dejamos la presentación de hoy de los lenguajes diagonales.
Etiquetas: presentación
lunes, 12 de mayo de 2008,4:08
La intersección de dos LREs es un LRE
Sean L1 y L2, L.R.E.-> existe M1,M2 | L1 = L(M1),L2 = L(M2), es decir, si x pertence a L1, M1 acepta y si x pertenece a L2, M2 acepta. Sea L = L1 intersección L2, ¿existe M | L = L(M)? Sí, construyendo M de la siguiente forma:
La construcción es correcta puesto que si x pertenece a L1 AND x pertenece a L2 ) x pertenece a (L1 intersección L2) = L .
(M1 y M2 aceptan -> M acepta) por lo tanto, si x pertenece a L, M acepta.
Si x no pertenece a L1 o L2 -> M1 o M2 no aceptan, por lo tanto M no acepta.
Posteado por: Jon o Jon Ander (según persona)
Link ~
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} |
| q0 | (q0, {0,R}, {a,R}) | (q1, {B,L}, {B,Z}) |
| q1 | (q2, {0,Z}, {b,R}) | (q3, {B,R}, {B,Z}) |
| q2 | (q1, {0,L}, {b,R}) |
|
| q3 | (q3, {0,R}, {a,R}) | (q4, {B,R}, {#,R}) |
| q4 |
|
|
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 ~
,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 |
| q0 | (q0, 0, R) | (q1, X, R) | (q4, B, L) |
|
| q1 | (q1, 0, R) | (q1, 1, R) | (q2, B, R) |
|
| q2 | (q2, 0, R) |
| (q3, 0, L) |
|
| q3 | (q2, 0, L) | (q2, 1, L) |
| (q0, X, L) |
| q4 | (q4, B, L) | (q4, B, L) | q5 |
|
| q5 |
|
|
|
|
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} |
| q0 | (q1, {B, R}, {0, R}) |
| (q3, {B, R}, {B, R}) |
| q1 | (q1, {B, R}, {B, Z}) | (q0, {B, R}, {B, Z}) | (q3, {B, R}, {B, R}) |
| q2 |
|
|
|
Posteado por: Jon o Jon Ander (según persona)
Link ~
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
