PREGUNTA: Dado el alfabeto Σ = {x,y,z}, sea L
1 = {x
ny
nz
n: n > 0} y sea L
2 el lenguaje reconocido por la siguiente máquina de Turing (Nota: Se supone que la máquina tiene el mismo alfabeto Σ y el conjunto de símbolos de cinta es r = Σ U {B} donde B representa el símbolo en blanco. Cuando analiza una cadena, la máquina de Turing parte de la configuración inicial donde la cinta de entrada contiene un símbolo en blanco seguido de la cadena a analizar seguida de blancos; la cabeza de lectura/escritura se encuentra situada en el primer símbolo a la izquierda de la cadena).
¿Cuál de las siguientes afirmaciones es correcta?
a) L1 = L2
b) L1 ≠ L2
c) L1 ⊂ L2
d) L2 ⊂ L1
RESPUESTA: hay dos opciones que podrían considerarse correctas, la b y la c. Nosotros nos decantamos por responder la c) (ver el razonamiento seguido a continuación)
En primer lugar reflexionamos sobre el lenguaje L1. ¿El lenguaje L1 es un lenguaje regular? No, ya que es necesario contar el número de apariciones de cada carácter y esta capacidad no la tienen los autómatas finitos. ¿Es un lenguaje independiente del contexto? Lo será si es reconocible por un autómata a pila. Nos inclinamos por pensar que sí es un LIC, ya que por cada x de entrada podemos apilar dos equis, luego con cada y desapilar una x y con cada z desapilar otra x llegando a aceptación.
Son cadenas que pertenecen a L1: xyz, xxyyzz, xxxyyyzzz, etc.
El lenguaje L2 que reconoce la máquina de Turing no sabemos cuál es. Sabemos que su alfabeto es x, y, z al igual que el de L1. No resulta sencillo saber qué lenguaje representa una máquina de Turing a primera vista. Nosotros vamos a optar por probar a pasarle cadenas de entrada y comprobar qué hace la máquina, y comparar lo que acepta o no acepta con lo que es aceptado en L1.
Vamos pasándole a la máquina de Turing cadenas y comprobamos qué sucede.
Pasando x, ó y, ó z no hay aceptación. Si nos fijamos en la máquina, para pasar de q0 a q1 requiere una x, para pasar de q2 a q3 requiere una y, y para pasar de q4 a q5 requiere una z. Además en cada estado tiene bucles que le permiten consumir más caracteres.
Pasamos xyz. La ejecución es: q0xyz ├ q1Bxyz ├ q2xyz ├ xq2yz ├ q3xyz ├ q3Bxyz ├ q4xyz ├ xq4yz ├ xyq4z ├ xq5yz llega a ACEPTACIÓN.
Pasamos xzy. La ejecución es: q0xzy ├ q1Bxzy ├ q2xzy ├ xq2zy ├ xzq2y ├ xq3zy ├ q3xzy ├ q3Bxzy ├ q4xzy ├ xq4zy ├ q5xzy llega a ACEPTACIÓN
Pasamos xxyz. La ejecución es q0xxyz ├ q1Bxxyz ├ q2xxyz ├ xq2xyz ├ xxq2yz ├ xq3xyz ├ q3xxyz ├ q3Bxxyz ├ q4xxyz ├ xq4xyz ├ xxq4yz ├ xxyq4z ├ xxq5z llega a ACEPTACIÓN
Pasamos xxyyzz. La ejecución es q0xxyyzz ├ q1Bxxyyzz ├ q2xxyyzz ├ xq2xyyzz ├ xxq2yyzz ├ xq3xyyzz ├ q3xxyyzz ├ q3Bxxyyzz ├ q4xxyyzz ├ xq4xyyzz ├ xxq4yyzz ├ xxyq4yzz ├ xxyyq4zz ├ xxyq5yzz llega a ACEPTACIÓN
A la vista de los resultados (quizás algunas personas sean capaces de verlo más rápido, pero otras necesitaremos hacer estas pruebas para poder verlo) podemos decir que la máquina acepta cadenas que tengan al menos una x, una y y una z en cualquier orden sin necesidad de que estén balanceadas.
Podríamos alegar que en una cadena como xxyyzzzzz quedarán parte de las zetas sin inspeccionar, pero esto es algo propio de las máquinas de Turing. Las máquinas de Turing copian la cadena de inicio a la cinta y a partir de ahí trabajan con la cinta sin importarles la entrada, de ahí que puedan llegar a aceptación dejando parte de las cadenas sin inspeccionar.
Si tratamos de ver lo que hace la MT, en primer lugar se mueve a derechas hasta encontrar una x. Luego vuelve al principio de la cadena, hasta encontrar el blanco inicial. Luego se mueve a derechas hasta encontrar una y, y seguidamente vuelve al principio de la cadena, hasta encontrar el blanco inicial. Luego se mueve a derechas hasta encontrar una z y acepta.
Ahora analizamos las opciones.
a) ¿Son L1 y L2 iguales? No, L1 requiere balanceo y L2 no
b) ¿Son distintos? Lo dejamos pendiente
c) ¿Es L1 un subconjunto de L2?, es decir, ¿todas las cadenas de L1 están en L2? Esto equivale a decir, ¿todas las cadenas balanceadas son reconocidas por la máquina de Turing? La respuesta es sí
d) ¿Es L2 subconjunto de L1? Es decir, ¿dentro de L1 (insulto) cadenas no balanceadas? La respuesta es no.
La duda puede estar entre la opción b) y la c), ya que es verdad que son distintos y es verdad que L1 es subconjunto de L2. Esto en el examen podría comentarse (recomendamos hacerlo). Para responder, nos decantamos por la opción c) porque es la respuesta más precisa, pero recomendamos incluir una explicación al respecto en una hoja adicional.