4.- Diseñar una Máquina de Turing que calcule la paridad de un número binario. Es decir, si el número de 1’s de la cadena es par, se añade un 0 al final, y si es impar, se añade un 1.

Como se ve en la siguiente imagen, el conjunto de símbolos que lee la máquina es {0,1}, el conjunto de símbolos que se escribe en la cinta es {0,1, □}, los estados son {q0, q1, q2}, el estado inicial es qo y el final q2

Grafo que representa la máquina de Turing

- q0 es el estado par, es decir que se ha leído un número de unos par en la palabra de entrada (considerándose 0 unos como par).

-q1 es el estado impar, es decir que se ha leído un número de unos impar en la palabra de entrada.

-q2 es el estado final de aceptación, al cual se tras escribir el 0 ó 1 final.

Procederé a explicar cómo funciona la máquina, se inicia en q0 en caso de que lea un ‘0’ en el primer espacio de la cinta se queda en el estado q0 escribe un ‘0’ y se recorre a la derecha, en caso de que el número sea ‘1’ se pasa al estado impar, se escribe un ‘1’ y se recorre a la derecha. En ambos estados hace lo mismo por lo que mientras se recorre la palabra la máquina pasa de un estado a otro, de q0 a q1, es decir de par a impar hasta que se encuentre un espacio en blanco, al encontrar el espacio en blanco dependiendo de en qué estado se quedó se escribe un 0 si es par mantener la paridad ó un 1 para conseguir la paridad y no se recorre la cinta.

Entrada Q0 Q1 Q20 0,RQ0 0,RQ1 N/A

1 1,RQ1 1,RQ0 N/Ab 0,SQ2 1,SQ2 N/A

Ejemplo

Para la entrada 10101

10101 10101 10101 10101 10101 10101□

q0q1 q1q1 q1q0 q0q0 q0q1 q1q2

final: 101011 ; lo cual indica que el número de unos es impar.

5.- Diseñar una MT que sea un contador unitario de caracteres del lenguaje con alfabeto {a,b,c}. Es decir, se deben devolver tantos unos como caracteres haya en la palabra de entrada. Considerar la codificación unitaria del 0.

Tomando en cuenta que no no dice, si conservar la palabra original o no, podemos tener dos soluciones una donde se conserve la palabra original y se cuenten los caracteres y otra donde no importe si se guarda la palabra original.

Caso número uno.

Grafo que representa el caso uno de la máquina de Turing

- q0 es el estado inicial, este estado contabiliza las a, b, c de la cinta cambiándolas por unos y recorriendo la cinta a la derecha pero manteniéndose en el estado q0.

-q1 es el estado final al que se llega cuando se encuentra un espacio vacío que indica el final de la palabra al darse esta transición se pone un espacio en blanco a la cinta y se para la cinta.

Procederé a explicar cómo funciona la máquina, se inicia en q0 cada que detecta una a. b o c se queda en el estado q0, cambia la letra por un uno y avanza a la derecha, en caso de leer el final de la palabra osea un espacio en blanco avanza al estado q1 escribiendo un espacio en blanco y deteniendo la cinta quedándose en este estado final y terminando la cuenta.

Entrada Q0 Q1a 1,RQ0 N/A

b 1,RQ0 N/Ac 1,RQ0 N/A

b* b*,SQ1 N/A

Ejemplo

Para la entrada aacbba

aacbba 1acbba 11cbba 111bba 1111ba 11111ª 111111□

q0q0 q0q0 q0q0 q0q0 q0q0 q0q0 q0q1

final: 111111□ ; lo cual indica una cuenta de 6 caracteres.

Caso número dos.

Grafo que representa el caso dos de la máquina de Turing

- q0 este estado funciona como marca de inicio para el conteo poniendo el primer grafo como mayúscula.

-q1 funciona como un estado de transición para recorrer la cinta a la derecha y contar el primer grafo.

-q2 funciona como un estado de transición para recorrer la cinta a la izquierda y te identifica el punto de inicio cambia la letra de inicio por minúscula y te manda a q0.

-q3 Este estado funciona como estado para identificar el final de conteo de los grafos te recorre los grafos a la izquierda y te manda al estado final.

-q4 es el estado final determina la aceptación.

Procederé a explicar cómo funciona la máquina, al momento de arranque la máquina el estado 0 cambia la primer letra a mayúscula para identificar el inicio de carrera y pasa al estado q1 el estado q1 se encarga de recorrer toda la cinta hasta encontrar un espacio en blanco y cambiarlo por un ‘1’ e iniciar el conteo pasando también al estado q2, el estado q2 recorre la cinta a la izquierda hasta identificar el inicio de carrera y te manda al estado q0 y recorre el inicio de carrera al segundo grafo, este ciclo se repite en cuantos grafos existan en la cinta. Cuando se llegue al final de la cinta el estado q0 mandará al estado q3 el cual se encargará de recorrer cada uno de los grafos a la izquierda y asegurarse de que ya no hay un punto de inicio mandando así al estado final q4.

Entrada Q0 Q1 Q2 Q3 Q4a A,RQ1 a,RQ1 a,LQ2 a,LQ3 N/Ab B,RQ1 b,RQ1 b,LQ2 b,LQ3 N/Ac C,RQ1 c,RQ1 c,LQ2 c,LQ3 N/A

1 1,LQ3 1,RQ1 1,LQ2 N/A N/Ab* N/A 1,LQ2 N/A b*,SQ4 N/A

A N/A N/A a,RQ0 N/A N/A

B N/A N/A b,RQ0 N/A N/A

C N/A N/A c,RQ0 N/A N/A

Ejemplo

Para la entrada abc

Abc□ Abc□ Abc□ Abc□ Abc1□ Abc1□ Abc1□ abc1□ aBc1□ aBc1□

q0q1 q1q1 q1q1 q1q2 q1q2 q2q2 q2q0 q0q1 q1q1 q1q1

aBc1□ aBc11□ aBc11□ aBc11□ abc11□ abC11□ abC11□ abC11□ abC111□ abC111□

q0q2 q2q2 q2q2 q2q0 q0q1 q1q1 q1q1 q1q2 q2q2 q2q2

□abC111□ □ abc111□ □ abc111□ □ abc111□ □ abc111□ □ abc111□ □ abc111□

q2q0 q0q3 q3q3 q3q3 q3q3 q3q4 Estado final

6.-Diseñar una máquina de turing que haga una copia de una cadena de símbolos {A, B, C}, sin carácter de separación por ejemplo “AABC”, devuelve el valor en cinta “AABCAABC”.

Grafo que representa la solución con máquina de Turing

- q0 te manda al estado q1 recorre la cinta a la derecha y reemplaza la letra con ella misma.

-q1 recorre la longitud total de la cinta hasta el primer espacio en blanco dónde colocara una Y para limitar la longitud de la palabra. Te pasa al estado q2, recorre la cinta a la izquierda después de colocar la Y que indica el final de cinta y mientras existan letras en la cinta las reemplaza consigo mismas desplazando hacia la derecha.

-q2 regresa la cinta a la izquierda reemplazando las letras consigo mismas hasta llegar al espacio vacío lo cual te manda a q3 y recorre a la derecha.

-q3 te manda a q4 sin importar que tipo de letra te encuentres pues la reemplaza consigo misma y te desplaza a la derecha.

-q4 actúa como el copiador de las letras dependiendo de la letra que este leyendo en ese momento, este te direccionará al ciclo para copiar, también al terminar el copiado de las letras a la derecha de la letra de inicio detecta una Y que indica el final de la palabra y recorre a la izquierda pasando al estado q11

-q5 reemplaza la letra A por una X y recorre la cinta a la derecha hasta encontrar un espacio vacío y reemplazarlo por una A y recorrer la cinta a la izquierda.

-q6 reemplaza la letra B por una X y recorre la cinta a la derecha hasta encontrar un espacio vacío y reemplazarlo por una B y recorrer la cinta a la izquierda.

-q7 reemplaza la letra C por una X y recorre la cinta a la derecha hasta encontrar un espacio vacío y reemplazarlo por una C y recorrer la cinta a la izquierda.

-q8 recorre la cinta a la izquierda hasta encontrar el espacio ocupado por la X y reemplazarlo por la letra A

-q9 recorre la cinta a la izquierda hasta encontrar el espacio ocupado por la X y reemplazarlo por la letra B

-q10 recorre la cinta a la izquierda hasta encontrar el espacio ocupado por la X y reemplazarlo por la letra C.

-q11 recorre la cinta hacia la izquierda hasta encontrar un espacio en blanco, lo reemplaza por un espacio en blanco y recorre a la derecha

-q12 este estado nos ayuda a copiar la primera letra de la palabra sin importar cuál sea, este estado te direcciona a la última etapa de copiado, dependiendo si la entrada es A, B, C. te direcciona al estado q13, q14 ó q15 respectivamente.

-q13 recorre la cinta a la derecha hasta encontrar la Y que limita el tamaño de la palabra y la reemplaza por una A y te manda a q16.

-q14 recorre la cinta a la derecha hasta encontrar la Y que limita el tamaño de la palabra y la reemplaza por una B y te manda a q16.

-q15 recorre la cinta a la derecha hasta encontrar la Y que limita el tamaño de la palabra y la reemplaza por una C y te manda a q16.

-q16 te termina de recorrer la cinta hacia la derecha y al encontrar un espacio en blanco lo reemplaza consigo mismo y se detiene la cinta y te manda al estado final.

-q17 Es el estado que valida la palabra.

Entrada q0 q1 q2 q3 q4 q5 q6A A,R-->q1 A,R-->q1 A,L-->q2 A,R-->q4 X,R-->q5 A,R-->q5 A,R-->q6B B,R-->q1 B,R-->q1 B,L-->q2 B,R-->q4 X,R-->q6 B,R-->q5 B,R-->q6C C,R-->q1 C,R-->q1 C,L-->q2 C,R-->q4 X,R-->q7 C,R-->q5 C,R-->q6Y N/A N/A N/A N/A Y,L-->q11 Y,R-->q5 Y,R-->q6X N/A N/A N/A N/A N/A N/A N/Ab N/A Y,L-->q2 b,R-->q3 N/A N/A A,L-->q8 B,L-->q9

q7 q8 q9 q10 q11 q12 q13A,R-->q7 A,L-->q8 A,L-->q9 A,L-->q10 A,L-->q11 A,R-->q13 A,R-->q13B,R-->q7 B,L-->q8 B,L-->q9 B,L-->q10 B,L-->q11 B,R-->q14 B,R-->q13C,R-->q7 C,L-->q8 C,L-->q9 C,L-->q10 C,L-->q11 C,R-->q15 C,R-->q13Y,R-->q7 Y,L-->q8 Y,L-->q9 Y,L-->q10 N/A N/A A,R-->q16

N/A A,R-->q4 B,R-->q4 C,R-->q4 N/A N/A N/AC,L-->q10 N/A N/A N/A b,R-->q12 N/A N/A

q14 q15 q16 q17A,R-->q14 A,R-->q15 A,R-->16 N/AB,R-->q14 B,R-->q15 B,R-->17 N/A

C,R-->q14 C,R-->q15 C,R-->18 N/AB,R-->q16 C,R-->q16 N/A N/A

N/A N/A N/A N/AN/A N/A b,S N/A

Tabla de comportamiento de la máquina de Turing en sus diferentes estados.

Demostración de funcionamiento de la máquina de Turing (a diferencia de los ejercicios anteriores el ejemplo será puesto con imágenes de JPLAB por su complejidad.

EL EJEMPLO SE DA CON LA SECUENCIA : ABCA

Secuencia paso a paso parte 1 Secuencia paso a paso parte 2

Secuencia paso a paso parte 3 Secuencia paso a paso parte 4

Secuencia paso a paso parte 5 Secuencia paso a paso parte 6

Secuencia paso a paso parte 7 Secuencia paso a paso parte 8

Secuencia paso a paso parte 9 Secuencia paso a paso parte 10

Secuencia paso a paso parte 11 final de la secuencia