BelloEdgar_Ej16 - Edgar Bello

Vista previa del material en texto

INSTITUTO POLITÉCNICO NACIONAL 
Escuela Superior De Cómputo 
 
 
 
 
 
 
Teoría Computacional 
Lista de Automatas 
 
 
 
 
Alumnos: 
Carrillo Rodríguez Antonio 
Galindo Cruz Paola Leticia 
Bello Muñoz Edgar Alejandro 
Montoya Bautista Miguel Ángel 
 
Ciclo Escolar 2021-1 
 
 
 
 
Maquina de Turing Complemento a 1 
Automata de Maquina de Turing; 
 
Probando numero binarios Negativos a Complemento a 1 
1010 a C1 0101 
Insertando la cadena; 
 
Verificando los pasos; 
 
 
 
Probando con 1111 a C1 0000 
 
Resultado; 
 
 
Probando 1100 a C1 0011 
 
Resultado; 
 
 
 
 
Probando con 1001 a C1 0110 
 
Resultado; 
 
2.- Numero consecutivo de un numero binario 
Se el automata de la maquina de turing 
 
 
Realizamos pruebas 
Entrada 000 
 Donde : 
Entrada 0011 
 Donde: 
Entrada 111 
Donde; 
Por ultimo tenemos 
Entrada 1 
 Donde su resultado es; 
 
 
 
 
3.-Maquina de Turing que acepta un lenguaje 
Sea el autómata; 
 
Haciendo la entrada en base a la lista tenemos 
Entrada 000111 
 Donde ; Tomando el cuenta el lenguaje que 
acepta este autómata 
4.- Maquina de Turing para una palabra w, de su inversa 
Se tiene el automata; 
 
 
 
 
 
 
Probamos con las cadenas 1100, 0110 y 1001 
Entrada 1100; Donde 
Tomando en cuenta que la maquina de turing pasa por varios estados como lo es A,Z y Y para 
poder retomar estados y devolver en el estado final 
Entrada 0110; donde; (Error) 
Entrada 1001 donde (Error) 
podemos ver que algunas cadenas no es compatible o no es aceptado el lenguaje y nos retoma al 
mismo numero/palabra.