Máquina de Turing M3

Máquina de Turing M3

La MT M3 decide L={aibjck | i·j=k ∧ i,j,k<=1}

Ejemplos de cadenas inválidas "": No contiene ningún símbolo (i=j=k=0) ✗ "a": Solo contiene 'a', faltan 'b' y 'c' ✗ "ab": Faltan símbolos 'c' ✗ "aabccc": i=2, j=1, k=3 (2×1≠3) ✗ "aabbccc": i=2, j=2, k=3 (2×2≠3) ✗ "abbc": i=1, j=2, k=1 (1×2≠1) ✗ "acb": Orden incorrecto de símbolos ✗

Ejemplos de cadenas válidas "abc": i=1, j=1, k=1 (1×1=1) ✓ "aabcc": i=2, j=1, k=2 (2×1=2) ✓ "abbcc": i=1, j=2, k=2 (1×2=2) ✓ "aabbcccc": i=2, j=2, k=4 (2×2=4) ✓ "aaabbbccccccccc": i=3, j=3, k=9 (3×3=9) ✓

Máquina Unicinta

Definición de Alto Nivel de la MT

La máquina de Turing unicinta tiene que comprobar que la entrada cumpla estas condiciones para reconocer el lenguaje L = {aibjck| i·j = k ∧ i,j,k<=1}: La cadena tiene que tener esta forma: 1. Primero todas las 'a', luego todas las 'b', y finalmente todas las 'c'. 2. El número de ‘a’ multiplicado por el número de ‘b’ tiene que ser igual al número de ‘c’. 3. El número de ‘a’, ‘b’ y ‘c’ tiene que ser mayor o igual a 1.

La máquina operará en varias fases: Fase 1: Verificación del formato de la entrada Fase 2: Verificación de la condición i·j = k:

Definición de Alto Nivel de la MT

Fase 1: Verificación del formato de la entrada

• La máquina verificará que la cadena comience con al menos una 'a', seguida de al menos una 'b', seguida de al menos una 'c'.
• La máquina verificará que no haya otros símbolos.
• En caso contrario, la máquina rechaza la cadena.

1. Posicionarse al inicio de la cadena. 2. Marcar la primera 'a' (cambiándola a '@'). 3. Para cada 'a': Marcas esa ‘a’. Te desplazas a las ‘b’ y marcas una b (cambiándola a B). Te desplazas a las ‘c’ y marcas una 'c' (cambiándola a 'C'). Vuelves a las ‘b’ y repites hasta que te quedes sin ‘b’. 4. Cuando todas las ‘a’ sean ‘A’: Verificar que todas las 'c' estén marcadas (no queden 'c' sin marcar). Si quedan 'c' sin marcar, rechazar. Si todas las 'c' están marcadas, aceptar.

Fase 2: Verificación de la condición i·j = k:

Definición formal de la máquina

1. Alfabeto de entrada (Σ) Σ = {a, b, c} 2. Alfabeto de cinta (Γ) Γ = {a, b, c, A, B, C, @, _} 3. Conjunto de estados (Q) Q = {q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,qacc,qrej}

M = (Q, Σ, Γ, δ)

Demostración por Inducción

Parte 1: Demostración de que la máquina acepta todas las cadenas en L

Caso Inductivo Para cualquier combinación de valores i,j,k ≥ 1 tales que i·j=k. Consideremos el caso (i+1,j,k+j) donde (i+1) · j =(i · j) + j = k + j . Para la cadena ai+1 · bj · ck+j : La máquina verifica que la cadena tiene el formato correcto (a+b+c+) Para cada ‘a’ (i): Por cada uno de los j 'b', marca una 'c' adicional (marca j ‘b’ y j ‘c’) Quita las marcas de las ‘b’ En total, se han marcado ( i · j )+j=(k+j) 'c' La máquina comprueba si todas las ‘c’ están marcadas. Como todas lo están, la máquina acepta la cadena. Por lo tanto, por inducción, la máquina acepta todas las cadenas ai· bj · ck donde i · j =k y i,j,k ≥ 1 .

Caso Base: i=j=k=1 Para la cadena "abc" La máquina verifica que la cadena tiene el formato correcto (a+b+c+). Marca la única 'a' como 'A': "Abc". Procesa la única 'b' y marca la única 'c': "AbC". No quedan 'a' sin procesar. Verifica que todas las 'c' estén marcadas. Como todas las 'c' están marcadas, la máquina acepta la cadena.

Demostración por Inducción

Parte 2: Demostración de que la máquina rechaza todas las cadenas que NO están en L

Tipo 2: Cadenas donde i *j≠ k: Caso 2.1: i · j< k Si i · j < k, entonces después de procesar todas las 'a' y 'b', la máquina habrá marcado exactamente i · j 'c'. Como i · j < k, quedarán (k - i · j) 'c' sin marcar. En la fase de verificación final (estado q11), la máquina encontrará estas 'c' sin marcar y rechazará la cadena.

• Tipo 1: Las cadenas que tienen un formato incorrecto

Si una cadena no tiene el formato a+b+c+, la máquina la rechaza en la fase de verificación:

• Cadenas vacías ("")
• Cadenas que no comienzan con 'a' ("bc")
• Cadenas sin 'b' después de las 'a' ("aacc")
• Cadenas sin 'c' después de las 'b’ ("abb")
• Cadenas con símbolos en orden incorrecto ("abcba")

Caso 2.2: i · j> k Si i · j> k, entonces durante el procesamiento de las 'a' y 'b', la máquina intentará marcar (i · j) 'c'. Como i · j> k, en algún momento la máquina intentará marcar una 'c' que no existe. En este punto, la máquina rechazará la cadena. Por lo tanto, la máquina rechaza todas las cadenas que no pertenecen a L.

Análisis de Complejidad Temporal

Análisis de Complejidad Temporal

La complejidad temporal se mide en términos del número de pasos que la máquina realiza en función del tamaño de la entrada

Análisis por Fases

• Fase 1: Verificación del formato

Recorrido inicial: O(n) pasos, donde n es la longitud de la cadena.Regreso al inicio: O(n) pasos.

• Fase 2: Verificación de i · j k

Por cada 'a' (hay i 'a'): Marca la 'a' como 'A': O(1) Recorre hasta el primer 'b': O(i) en el peor caso Por cada 'b' (hay j 'b'): Marca el 'b' como 'B': O(1) Busca una 'c' sin marcar: O(k) en el peor caso Marca la 'c' como 'C': O(1) Regresa al 'B': O(k) en el peor caso Restaura los 'b': O(j) Regresa a la A marcada: O(i) Fase 3: Verificación de i · j= k comprobar que no hay más ‘c’ sin marcar: j+k

Análisis de Complejidad Espacial

Análisis de Complejidad Espacial

En una máquina de Turing, el espacio utilizado se mide por el número máximo de celdas a las que se ha accedido durante la ejecución.

Análisis del Espacio UtilizadoConsideraremos:1. El espacio ocupado por la cadena de entrada original.2. El espacio adicional que la máquina pueda requerir para su procesamiento.Espacio para la Entrada La cadena de entrada ocupa n = i + j + k celdas en la cinta. Espacio Adicional Utiliza el espacio ocupado por la cadena de entrada más uno de leer el primer blanco para comprobar que hemos llegado al fin de cadena.

Complejidad Espacial TotalLa complejidad espacial total es: O(n) + O(1) = O(n)Esta complejidad espacial es la óptima, ya que cualquier máquina de Turing que reconozca este lenguaje debe al menos leer toda la entrada, lo que requiere O(n) espacio.

Implementación en Simulador

Selección del SimuladorHemos decidido usar turingmachinesimulator.com Implementación de la Máquina M3 A continuación se presenta la implementación completa de la máquina de Turing unicinta M3 que reconoce el lenguaje L = {aibjck| i·j = k ∧ i,j,k 1}:

Código

Máquina Multicinta

Definición de Alto Nivel de la MT

La máquina de Turing multicinta reconocerá el mismo lenguaje L = {aibjck| i·j = k ∧ i,j,k<=1}, es decir, las cadenas en las que el número de ‘a’ multiplicado por el número de ‘b’ es igual al número de ‘c’.

Uso de múltiples cintasPara la máquina de Turing multicinta, usaremos 3 cintas: Cinta 1 (c1): Almacena la cadena de entrada y se usará para verificar el formato de esta. Cinta 2(c2): Se usará para contabilizar las ‘a’ y poder verificar la condición. Cinta 3(c3): Se usará para contabilizar las ‘c’ y poder verificar la condición.

Definición de Alto Nivel de la MT

Funcionamiento general La máquina operará en varias fases:

Fase 1 - Verificación de formato de entrada:

Verificamos en la cinta 1 que la cadena tenga el formato correcto (a+b+c+), es decir, que no falte ninguna ‘a’, ‘b’, o ‘c’ y que no haya otros símbolos. Si esto ocurre la máquina rechaza.

Fase 2 - Preparación de las 3 cintas:

Escribimos ‘@’ en el inicio de las 3 cintas para delimitarlas por la izquierda. Copiamos las 'a' a la cinta 2 y copiamos las ‘c’ a la cinta 3.

La máquina efectuará las siguientes operaciones: 1. Para cada 'a' en la cinta 2: a. Te desplazas a las ‘b’ en la cinta 1. b. Marcas esa ‘a’. c. Por cada ‘b’ en la cinta 1 marcas una ‘c’ en la cinta 3. 2. Cuando todas las ‘a’ en la cinta 2 esten marcadas: a. Verificar que todas las 'c' en la cinta 3 estén marcadas. i. Si quedan 'c' sin marcar, rechazar. ii. Si todas las 'c' están marcadas, aceptar.

Fase 3 - Verificación de la condición i · j = k:

Definición formal de la máquina

1. Alfabeto de entrada (Σ) Σ = {a, b, c} 2. Alfabeto de cinta (Γ) Γ = {a, b, c, A, B, C, @, _} 3. Conjunto de estados (Q) Q = {q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,qacc,qrej}

M = (Q, Σ, Γ, δ)

Implementación en Simulador

Selección del SimuladorHemos decidido usar turingmachinesimulator.com Implementación de la Máquina M3 A continuación se presenta la implementación completa de la máquina de Turing multicinta M3 que reconoce el lenguaje L = {aibjck| i·j = k ∧ i,j,k 1}:

Código

Demostración por Inducción

Parte 1: Demostración de que la máquina acepta todas las cadenas en L

• Caso Inductivo (Para cualquier combinación de valores i,j,k ≥ 1 tales que i·j=k)

• Consideremos el caso (i+1,j,k+j) donde

(i+1) · j =i · j +j = k + j . Para la cadena ai+1 · bj · ck+j :

• La máquina verifica que la cadena tiene el formato correcto (a+b+c+)
• Marca las i+1 'a' y las copia a la cinta 2.
• Marca las j 'b' como 'B'.
• Marca las k+j 'c' en la cinta 3
• Por cada i+1 'a' en la cinta 2, la máquina marca j 'C' como 'c' en la cinta 3.
• Las primeras i 'a' marcan i·j = k 'C'. La 'a' adicional marca j 'C' más.
• En total, se marcan i · j + j = k + j 'C', que es exactamente el número de 'c' en la cadena.

• La máquina comprueba si todas las ‘c’ están marcadas.

• Por lo tanto, por inducción, la máquina acepta todas las cadenas ai· bj · ck donde i · j =k y i,j,k ≥ 1 .

• Caso Base: i=j=k=1

Para la cadena "abc"

• La máquina verifica que la cadena tiene el formato correcto (a+b+c+).
• Marca la única 'a' y la copia en la cinta 2.
• Marca la única 'b'. Marca la única 'c' en la cinta 3.
• Procesa la 'a' de la cinta 2 y avanza para encontrar 'B'
• Procesa la 'c' de la cinta 3
• Verifica que todas las 'c' estén marcadas.
• Como todas las 'c' están marcadas, la máquina acepta la cadena.

Demostración por Inducción

• Tipo 2: Cadenas donde i*j≠ k:
• Caso 2.1: i · j< k
• Si i · j < k, entonces después de procesar todas las 'a' y 'b', la máquina habrá marcado exactamente i · j 'c' como 'C' en la cinta 3.

• Como i · j < k, quedarán (k - (i · j)) 'c' sin marcar (representadas como 'C' en la cinta 3).
• En la fase de verificación final (estado q11), la máquina encontrará estos 'C' sin convertir a 'c' y rechazará la cadena.

Parte 2: Demostración de que la máquina rechaza todas las cadenas que NO están en L

• Tipo 1: Las cadenas que tienen un formato incorrecto

Si una cadena no tiene el formato a+b+c+, la máquina la rechaza en la fase de verificación:

• Cadenas vacías ("")
• Cadenas que no comienzan con 'a' ("bc")
• Cadenas sin 'b' después de las 'a' ("aacc")
• Cadenas sin 'c' después de las 'b’ ("abb")
• Cadenas con símbolos en orden incorrecto ("abcba")

• Caso 2.2: i · j> k
• Si i · j > k, entonces durante el procesamiento de las 'a' y 'b', la máquina intentará marcar (i · j) 'c' como 'C'.
• Como i · j > k, en algún momento la máquina intentará marcar una 'c' que no existe (es decir, no habrá suficientes 'C' en la cinta 3).

• En este punto, la máquina rechazará la cadena.

• Por lo tanto, la máquina rechaza todas las cadenas que no pertenecen a L.

Análisis de Complejidad Temporal

Análisis de Complejidad Temporal

Medimos la complejidad temporal en términos del número de pasos que la máquina realiza en función del tamaño de la entrada. Para esta máquina de Turing multicinta que reconoce el lenguaje L = {aibjck| i·j = k ∧ i,j,k 1}, analizaremos cuántos pasos requiere para procesar una cadena de entrada de longitud n = i + j + k.

Análisis por Fases

En esta fase, la máquina recorre la cadena de entrada una vez para verificar que tenga el formato correcto (a+b+c+). Luego, regresa al inicio de la cinta. Recorrido inicial: O(n) pasos, donde n es la longitud de la cadena. Regreso al inicio: O(n) pasos.

Fase 1: Verificación del formato

Marcar las 'a' como 'A' y copiarlas a la cinta 2: O(i) pasos. Marcar las 'b' como 'B': O(j) pasos. Marcar las 'c' con 'C' en la cinta 3: O(k) pasos Retroceder en todas las cintas: O(n) pasos.

Fase 2: Conteo y preparación

Fase 3: Verificación de i · j = k

Por cada 'a' en la cinta 2 (hay i 'a'): a. Avanzar hasta encontrar la primera 'B': O(i) en el peor caso b. Por cada 'b' (hay j 'b'): i. Marcar un 'C' como 'c' en la cinta 3: O(1) ii. Retroceder para procesar la siguiente 'a': O(j)

Análisis de Complejidad Espacial

Análisis de Complejidad Espacial

Medimos la complejidad espacial como el máximo de celdas accedidas por cada cinta durante la ejecución.

Análisis del Espacio Utilizado Analizamos las celdas accedidas en cada cinta:

• Cinta 1: La cinta 1 contiene la cadena de entrada original, que ocupa n = i + j + k celdas.

• Cinta 2: La cinta 2 se utiliza para almacenar las 'a', ocupando i celdas.

• Cinta 3: La cinta 3 se utiliza para contener las 'c', ocupando k celdas.

Complejidad Espacial Total La complejidad espacial es la suma de las celdas utilizadas en cada cinta: O(i + j + k) + O(i) + O(k) = O(2i + j + 2k) = O(i + j + k) = O(n) Por lo tanto, la complejidad espacial de la máquina de Turing multicinta es O(n).