TLP - Poblemas Tema 5 - Escuela Técnica Superior de Ingeniería de Sistemas Informáticos PDF

Preview

Summary

Escuela Técnica Superior de Ingeniería de Sistemas Informáticos...

Description

Tema 5 MÁQUINAS DE TURING

Ejercicio 1 ( Junio 95 ) Dada la máquina de Turing M = ( Q, å, G, d, q0 , B, F ) Q (conjunto de estados) = { q0 , q1 , q2 ,q3 , q4 , q5 } å (alfabeto de entrada) = { a, b, c } G (alfabeto de cinta ) = { a, b, c, X, Y, Z, B } d (función de transición) = d (q0 , a ) = (q1 , X, R ) d (q0 , Y ) = (q4 ,Y, R ) d (q1 , a ) = (q1 , a, R ) d (q1 , b ) = (q2 , Y, R ) d (q1 , Y) = (q1 , Y, R ) d (q2 , b ) = (q2 , b, R ) d (q2 , c ) = (q3 , Z, L ) d (q2 , Z ) = (q2 , Z, R ) d (q3 , a ) = (q3 , a, L ) d (q3 , b ) = (q3 , b, L ) d (q3 , X ) = (q0 , X, R ) d (q3 , Y ) = (q3 , Y, L ) d (q3 , Z ) = (q3 , Z, L ) d (q4 , Y ) = (q4 , Y, R ) d (q4 , Z ) = (q4 , Z, R ) d (q4 , B ) = (q5 , B, L ) B (blanco) q0 (estado inicial) F (estados finales) = { q5 } Se pide: 1. Representar formalmente las transiciones de la máquina para las entradas aabbcc y abcc indicando, en cada caso, si el cómputo es aceptado. 2. Determinar el lenguaje reconocido por esta Máquina de Turing.

146

MÁQUINAS DE TURING

SOLUCIÓN: Apartado 1 aabbcc q0

Xabbcc q1

Xabbcc q1

XaYbZc q3

XaYbZc q3

XaYbZc q3

XaYbZc q

XXYbZc

XXYbZc

XXYYZc

XXYYZc

q

q1

1

XXYYZZ q3 XXYYZZ q4

XXYYZZ q3 XXYYZZ q4

XaYbcc q2

XaYbcc q2

3

q2

q2

XXYYZZ q3

XXYYZZ

XaYbZc q0 XXYYZZ q3 XXYYZZ

q0

XXYYZZB q4

q4

XXYYZZBB q5

En definitiva, la palabra aabbcc sí es reconocida. Para la palabra abcc: abcc q0 XYZc q

0

Xbcc q1

XYcc q2

XYZc

XYZc

q4

q

XYZc q3

XYZc q3

4

No es posible aplicar más transiciones. Como no se consigue alcanzar el estado q5, la palabra abcc no es reconocida por esta Máquina de Turing. Apartado 2 El lenguaje reconocido por esta Máquina de Turing es L = {an bn cn | n > 0 }, ya que su esquema de funcionamiento es el siguiente: 1. Localiza la primera de las a´s de la palabra y la marca con una X ( estado q0 ). 2. Avanza a la derecha hasta que encuentra un símbolo b, que marca con una Y (estado q1 ). 3. Continúa a la derecha hasta llegar a una c, que marca con una Z (estado q2 ). 4. Vuelve hacia atrás hasta encontrar la última a marcada, es decir, la X que está más a la derecha (estado q3 ).

147

MÁQUINAS DE TURING

5. Repite los pasos 1 a 4 hasta que se han marcado todas las a´s, en cuyo caso comprueba que todas las letras se encuentran marcadas (estado q4). 6. Finalmente reconoce la palabra en q5 . Este razonamiento se puede ver más claramente en el siguiente grafo de transiciones: X;XR

b;YR

a;XR

q1

q 0

Z;ZL b;bL a;aL Y;YL

Z;ZR b;bR

Y;YR a;aR

q2

c;ZR q 3

Y;YR

q 4

q 5 B;BL

Y;YR

Z;ZR

Ejercicio 2 Definir una Máquina de Turing para cada uno de los siguientes lenguajes sobre el alfabeto å = {a,b}. • aba* b • { w | la longitud de w es par } • { an bm | m >= n , n > 0 , m > 0 } • { w | contiene igual nº de a´s que de b´s } • { w c w | w Î {a, b}* } ( å = {a,b,c} ) • { w w | w Î {a, b}* } Indicar también el tipo de cada uno de los lenguajes según la clasificación de Chomsky.

SOLUCIÓN: Apartado 1 L = aba* b Dado que el lenguaje se encuentra especificado con una expresión regular, se trata de un lenguaje de tipo 3 o regular. De forma que la Máquina de Turing que se planteará a continuación funcionará de una manera muy similar a un autómata finito:

148

MÁQUINAS DE TURING

Q = {q0, q1, q2, q3, q4 } å = {a, b} G = { a, b, B } d (q0, a) = (q1, a, R) d (q1, b) = (q2, b, R) d (q2, a) = (q2, a, R) d (q2, b) = (q3, b, R) d (q3, B) = (q4, B, L) B --> blanco q0 --> estado inicial F = { q4 }

--> Reconocimiento de a --> Reconocimiento de b --> Reconocimiento de a* --> Reconocimiento de b

a;aR

q 0

a;aR

q 1

b;bR q 2

b;bR

B;BL q 3

q 4

Como se puede observar, la Máquina de Turing no necesita utilizar la cinta de entrada a modo de memoria auxiliar para reconocer las palabras, al igual que un Autómata Finito. Apartado 2 L = { w | la longitud de w es par } Se trata también de un lenguaje regular, que puede ser fácilmente especificado con una expresión regular: ((a|b)(a|b))* . Por tanto, la Máquina de Turing que se propondrá a continuación tampoco necesitará utilizar en absoluto la cinta de entrada como memoria. Para resolver este apartado se supondrá que la longitud cero también es par. Q = {q0, q1, q2 } å = {a, b} G = { a, b, B } d (q0, a) = (q1, a, R) d (q0, b) = (q1, b, R) --> Longitud par en q0 d (q1, a) = (q0, a, R) d (q1, b) = (q0, b, R) --> Longitud impar en q1 d (q0, B) = (q2, B, L) --> Reconocimiento de longitudes pares. B --> blanco q0 --> estado inicial F = { q2 }

149

MÁQUINAS DE TURING

q

2

b;bR

B;BL

a;aR q

q

0

1

a;aR b;bR

Apartado 3 L = {an bm | m >= n, n > 0 , m> 0 } Se trata de un lenguaje de tipo 2 o de contexto libre, por lo que la Máquina de Turing ya tendrá que utilizar la cinta de entrada como memoria auxiliar. Es decir, realizará ciertas marcas en la cinta que le servirán en las sucesivas pasadas que haga por ese punto de la cinta. En líneas generales, el esquema de la Máquina de Turing que se plantea a continuación es el siguiente: Por cada a que marca a la izquierda de la palabra con una X, marca una b a la derecha con una Y. De manera que si cuando termine de marcar todas las a´s quedan cero o más b´s, la palabra será correcta. El grafo de transiciones de la Máquina de Turing que realiza este proceso puede ser el siguiente: a;aR q1

Y;YR

a;XR b;YL q0

X;XR

q2

Y;YL a;aL

Y;YR

q3 B;BL

q4

Y;YR b;bR

De forma más detallada, las transciones representadas tienen la siguiente funcionalidad: Marcar la primera a de la palabra con una X.

150

MÁQUINAS DE TURING

d (q0, a) = (q1, X, R) Avanzar a la derecha en búsqueda de la primera b sin marcar, que marcará con una Y. d (q1, a) = (q1, a, R) d (q1, Y) = (q1, Y, R) d (q1, b) = (q2, Y, L) Volver atrás hasta localizar la última a marcada (una X). A partir de ese punto se puede comenzar otra vez el proceso anterior para la siguiente pareja de a y b. d (q2, Y) = (q2, Y, L) d (q2, a) = (q2, a, L) d (q2, X) = (q0, X, R) Si se han marcado todas las a´s comprobar que sólo quedan b´s. d (q0, Y) = (q3, Y, R) d (q3, Y) = (q3, Y, R) d (q3, b) = (q3, b, R) Reconocimiento de la palabra. d (q3, B) = (q4, B, L) Como se ve, no se puede realizar comparación alguna con un Autómata a Pila, ya que la forma en que gestiona una Máquina de Turing la memoria no tiene nada que ver con una estructura de pila.

Apartado 4 L = { w | contiene igual nº de a´s que de b´s } El esquema de funcionamiento de la Máquina de Turing será: cuando localiza una a, la marca con una X y se pone a buscar a la derecha una b que marcará con Y. Si lo que localiza primero es una b, tratará de buscar a la derecha una a para equipararla.

151

MÁQUINAS DE TURING

B;BR

Y;YR X;XR a;aR

a;XR

q1

b;YL q3

q 0

Y;YL X;XL b;bL a;aL

b;YR q 2

a;XL

B;BL

q4

Y;YR X;XR b;bR

De forma más detallada: Marcar la primera letra: si es una a se marca con X, y si es una b con Y. d (q0, a) = (q1, X, R) d (q0, b) = (q2, Y, R) Buscar una b para marcarla con Y. d (q1, a) = (q1, a, R) d (q1, X) = (q1, X, R) d (q1, Y) = (q1, Y, R) d (q1, b) = (q3, Y, L) Buscar una a para marcarla con X. d (q2, b) = (q2, b, R) d (q2, X) = (q2, X, R) d (q2, Y) = (q2, Y, R) d (q2, a) = (q3, X, L) Volver al comienzo de la palabra para repetir el proceso anterior. d (q3, a) = (q3, a, L) d (q3, b) = (q3, b, L) d (q3, X) = (q3, X, L) d (q3, Y) = (q3, Y, L) d (q3, B) = (q0, B, R) Saltar todos los símbolos ya marcados. d (q0, X) = (q0, X, R) d (q0, Y) = (q0, Y, R) Reconocer la palabra cuando todos los símbolos estén marcados. d (q0, B) = (q4, B, L)

152

MÁQUINAS DE TURING

Se trata de un lenguaje de contexto libre. Si el lenguaje a reconocer fuera L = { w | contiene igual nº de a´s que de b´s que de c´s }, la forma de operar de la Máquina de Turing correspondiente sería muy similar. Apartado 5 L = { w c w | w Î {a, b}* } No se trata de un lenguaje de tipo 2, ya que es imposible reconocerlo con un esquema de pila. Para dilucidar si se trata de un lenguaje de tipo 0 o de tipo 1 veremos si la Máquina de Turing que se propondrá a continuación necesita de una cantidad de memoria limitada, en cuyo caso se trata de un autómata linealmente acotado, y por tanto un lenguaje de tipo 1. Para reconocer este lenguaje se considerarán dos partes distintas en la palabra separadas por el símbolo c: w1 o parte de la izquierda y w2 o parte de la derecha. El problema que se plantea pues es comprobar que w1 y w2 son exactamente iguales. Los símbolos de w1 que ya hayan sido equiparados se marcarán con una X, mientras que los símbolos ya equiparados de w2 se marcarán con una Y. b;bR a;aR

Y;YR c;cR q

a;XR q

q

1

3

a;YL

0

q

b;XR

c;cR

q

Y;YR

Y;YL c;cL b;bL a;aL

2

c;cR

q

4

5

b;YL X;XR

a;aR b;bR

q6

B;BL q7

De forma más detallada: Marcar la primera letra de w1. d (q0, a) = (q1, X, R) d (q0, b) = (q2, X, R) Saltar símbolos hasta encontrar la c. d (q1, a) = (q1, a, R) d (q1, b) = (q1, b, R) d (q2, a) = (q2, a, R)

Y;YR

MÁQUINAS DE TURING

153

d (q2, b) = (q2, b, R) d (q1, c) = (q3, c, R) d (q2, c) = (q4, c, R) Saltar todas las letras ya marcadas de w2. d (q3, Y) = (q3, Y, R) d (q4, Y) = (q4, Y, R) Comprobar que la letra alcanzada de w2 coincide con la que se marcó en w1. d (q3, a) = (q5, Y, L) d (q4, b) = (q5, Y, L) Volver atrás hasta encontrar una X (la última letra marcada de w1 ) y comenzar de nuevo el proceso. d (q5, Y) = (q5, Y, L) d (q5, c) = (q5, c, L) d (q5, a) = (q5, a, L) d (q5, b) = (q5, b, L) d (q5, X) = (q0, X, R) Comprobar que todas las letras de w2 están equiparadas. d (q0, c) = (q6, c, R) d (q6, Y) = (q6, Y, R) Reconocimiento final de la palabra. d (q6, B) = (q7, B, L) Esta Máquina de Turing necesita para su ejecución únicamente el espacio de cinta destinado para almacenar la palabra de entrada, por lo que se trata de un Autómata Linealmente Acotado. En definitiva, el lenguaje es de tipo 1. Apartado 6 L = { ww | w Î {a, b}* } Aunque pueda parecer un lenguaje similar al anterior, plantea un problema importante: se desconoce el punto donde termina w1 y comienza w2 (antes estaba perfectamente indicado con un símbolo c). Debido a esto, la Máquina de Turing que se va a proponer a continuación va a funcionar de forma no determinista. Si el primer símbolo de w1 es una a, avanzará hasta encontrar otra a, pero este símbolo puede ser el comienzo de w2 o pertenecer todavía a w1 ( no determinismo ). La Máquina de Turing que especifica este no determinismo puede ser la siguiente:

154

MÁQUINAS DE TURING

q a;XR q

a;YL

b;bR a;aR

b;bR a;aR 1

b;bL a;aL Y;YL

a;YL q3

0

b;XR q2

b;YL

a;aR b;bR

X;XR

Y;YR Y;YR q a;XR

5

q7

Y;YR

q4

Y;YR q

q9 b;XR

10

B;BL q

Y;YR

6

Y;YR q8 b;bR a;aR b;YL

De forma detallada: Marcar la primera letra de w1. d (q0, a) = (q1, X, R) d (q0, b) = (q2, X, R) Si se ha localizado una a (q1) saltar hasta encontrar otra, que puede que pertenezca a w1 o ser el comienzo de w2. d (q1, b) = (q1, b, R) d (q1, a) = { (q3, Y, L), (q1, a, R) } Si se ha localizado una b (q2) saltar hasta encontrar otra, que puede que pertenezca a w1 o ser el comienzo de w2. d (q2, a) = (q2, a, R) d (q2, b) = { (q3, Y, L), (q2, b, R) } Volver al comienzo de la palabra (última X marcada). d (q3, Y) = (q3, Y, L) d (q3, a) = (q3, a, L) d (q3, b) = (q3, b, L) d (q3, X) = (q4, X, R) Una vez marcada la separación de las palabras (con una Y), la forma de trabajar es muy similar al apartado anterior. Marcar la siguiente letra de w1. d (q4, a) = (q5, X, R) d (q4, b) = (q6, X, R) Avanzar hasta encontrar la primera Y marcada (la separación).

MÁQUINAS DE TURING

155

d (q5, a) = (q5, a, R) d (q5, b) = (q5, b, R) d (q6, a) = (q6, a, R) d (q6, b) = (q6, b, R) d (q5, Y) = (q7, Y, R) d (q6, Y) = (q8, Y, R) Saltar las Y´s. d (q7, Y) = (q7, Y, R) d (q8, Y) = (q8, Y, R) Confirmar que la letra alcanzada de w2 coincide con la que se marcó en w1. d (q7, a) = (q3, a, L) --> El estado q3 volvía a la última X. d (q8, b) = (q3, b, L) Comprobar que todas las letras de w2 están equiparadas. d (q4, Y) = (q9, Y, R) d (q9, Y) = (q9, Y, R) Reconocimiento final de la palabra. d (q9, B) = (q10, B, L) Para terminar, cabe reseñar que no se reconoce la palabra: e, que sí pertenece al lenguaje. Para incorporarla, se añade la siguiente transición: d (q0, B) = (q10, B, L) El lenguaje considerado también es de tipo 1, ya que el autómata propuesto es un autómata linealmente acotado ( no necesita más memoria que el espacio ocupado por la cadena de entrada en la cinta ).

156

MÁQUINAS DE TURING

Ejercicio 3 (Junio 97) Dado el alfabeto å = {a, b, c}, definir una Máquina de Turing que reconozca el siguiente lenguaje: L = {c an c b2n c | n >= 0 }.

SOLUCIÓN: Como existe una relación entre a´s y b´s (el doble de las segundas que de las primeras), deben marcarse las ya contabilizadas en cada momento para ver que efectivamente se cumple esa relación. Así, las a´s se marcarán con X´s y las b´s se marcarán con Y´s. En cuanto a las c´s existentes, bastará con comprobar que existe una en cada uno de los tres puntos requeridos. El esquema de funcionamiento de la máquina de Turing propuesta es el siguiente: 1. Comprobar que empieza por una c. 2. Establecer un bucle en el que en cada iteración se marcará una a y dos b´s: • Marcar una a con X. • Saltar el resto de a´s. • Saltar la c que separa las a´s y las b´s. • Saltar las b´s ya marcadas (Y´s). • Marcar dos b´s con Y´s. • Volver a la izquierda hasta encontrar la última a marcada (X). 3. Salir del bucle cuando todas las a´s estén marcadas, es decir, se encuentra la c. 4. Saltar todas las b´s marcadas (Y´s). 5. Saltar la última c. 6. Encontrar el blanco (B) final y reconocer la palabra.

a;aR

a;XR c;cR

c;cR

q2

b;YR

q1

q0

X;XR

c;cR

q5 b;YL

Y;YR

Y;YR

q3

q6

Y;YL c;cL a;aL

c;cR q7 B;BL

q8

q4

157

MÁQUINAS DE TURING

Ejercicio 4 Se pretende construir Máquinas de Turing que realicen operaciones entre números naturales mayores que cero. Para lo cual, un entero positivo se representa mediante cadenas de a´s. Así, el número n estaría representado por an . Cuando se quiere realizar una operación, por ejemplo n+m, la entrada sería B an B am B, donde B es el símbolo blanco. La salida en el caso de la suma sería B an+m B. Se pide: 1 Construir la Máquina de Turing que realice la operación n + m. 2 Igual para la resta n - m, para n > m. 3 Igual para el producto n * m.

SOLUCIÓN: Apartado 1 Se tiene una cadena de n a´s, un blanco y una cadena de m a´s; y se pretende obtener una cadena de n+m a´s. De forma que para conseguirlo basta con cambiar el blanco por una a, y borrar la última a. La Máquina de Turing que realiza este proceso puede ser la siguiente:

a;aR

a;aR B;aR q0

B;BL q1

a;BL q2

q3

Apartado 2 Para la operación n - m, la Máquina de Turing podría actuar de la siguiente manera: 1. Borrar la a de más a la izquierda en an . 2. Borrar la a de más a la izquierda en am. 3. Volver atrás y repetir los pasos 1 y 2 hasta que am desaparezca.

158

MÁQUINAS DE TURING

B;BR

a;aR B;BR

q

q1

2

a;BR

q

a;BR B;BL

0

q

3

q 6

a;aL

B;BR q

5

a;aL

a;aL

q4

B;BL

Apartado 3 Para realizar la operación n * m, la Máquina de Turing puede operar de la siguiente manera: 1. Borrar la a de más a la izquierda de an. 2. Ir hasta am y, por cada símbolo a, copiarlo al final (después del blanco). 3. Repetir los pasos 1 y 2 hasta que desaparezca an . 4. Borrar , am . a;aR a;aR a;XR

q

3

B;BR a;aR

B;BR q

q

1

a;BR

q4

2

B;BL q

q5

0

B;BR B;BR

B;BL q q

a;BR

q6

7

X;aL 8

B;BR q

9

a;aL

a;aL B;BL

B;aL

159

MÁQUINAS DE TURING

Explicación un poco más detallada del grafo de transiciones: n • q0 y q1: Borrar la a de más a la izquierda de a y desplazarse a la derecha hasta alcanzar m a . m • q2, q3, q4 y q5: Bucle que copia cada a de a al final de la cadena. Para ello, cada a de m a que ya ha sido copiada se marca con una X. m • q6: Recuperar a transformando las X´s en a´s. n • q7: Volver al comienzo de a . m • q8: Eliminar finalmente a . Este autómata propuesto no sería un autómata linealmente acotado, ya que necesita escribir de forma indeterminada más allá del final de la cadena de entrada.

Ejercicio 5 Construir una Máquina de Turing que numere de forma progresiva todos los números binarios comenzando por el cero. Es decir, el contenido de la cinta evolucionará de la siguiente manera: B0B ==>* B1B ==>* B10B ==>* B11B ......

SOLUCIÓN: Se trata de analizar cómo, a partir de un número binario cualquiera, es posible incrementarlo en una unidad con una Máquina de Turing. Dicho esquema es el siguiente: Posicionarse en el bit de más a la derecha y realizar el siguiente proceso: • Si es un 0 se transforma en 1 y se termina el proceso. • Si es un 1 se transforma en 0 y se pasa al bit de la izquierda. • Este proceso se repite hasta encontrar un bit 0 o hasta encontrar el B de la izquierda, que se transformaría en 1. Por ejemplo, el número B11B sufriría las siguientes transformaciones: B11B ==> B10B ==> B00B ==> B100B No debe olvidarse que antes y después de la cadena de entrada hay infinitos blancos. 0;0R 1;1R B;BL q

1;0L q

0

1

0;1R B;1R

El funcionamiento de esta Máquina sería infinito, de ahí que no tenga ningún estado final.

160

MÁQUINAS DE TURING

Ejercicio 6 Construir una Máquina de Turing que enumere todos los números binarios en su cinta, manteniendo simultáneamente todos los que haya enumerado hasta el momento, separándolos con un blanco. La Máquina de Turing comenzará por e...