• Author / Uploaded
• Gerardo Araque

Citation preview

EJERCICIOS DE LA FASE 4 ACTIVIDAD INDIVIDUAL De acuerdo al último dígito de su cédula o tarjeta de identidad, identifique el ejercicio asignado en la siguiente tabla: Último dígito de la Cédula o TI 1y9 2y8 3y7 4y6 5y0

Ejercicio Ejercicio Ejercicio Ejercicio Ejercicio Ejercicio

1 2 3 4 5

ACTIVIDAD 1: Maquinas de Turing 1. Ejercicio 1

2. Ejercicio 2

3. Ejercicio 3

4. Ejercicio 4

5. Ejercicio 5

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla: EJERCICIO A TRABAJAR

Registre aquí el Ejercicio a trabajar. Por favor agregue la imagen

Caracterización En este espacio se realiza: de la máquina - Mediante la definición formal explicar las características de turing de la máquina de Turing.

Las principales características de la máquina de Turing eran las siguientes: 

La entrada que tiene la cinta antes de que comience el cálculo debe consistir en un número finito de símbolos.



La cinta de la máquina tiene una de longitud ilimitada.



El cabezal de lectura y escritura puede ser programable.



La máquina de Turing es capaz de hacer seis tipos de operaciones fundamentales: leer, escribir, mover hacia la izquierda, mover hacia la derecha, cambiar de estado y detenerse.



Tiene la capacidad de computar cualquier cosa que cualquier computadora moderna pueda calcular.



Está formada por un alfabeto de entrada y uno de salida y por un símbolo especial llamado blanco.

-

Realizar un cuadro donde explique las diferencias y similitudes de las máquinas reconocedoras y Traductoras Máquinas reconocedoras MT capaz de reconocer un lenguaje L. MT capaz de aceptar un lenguaje L.

Una MT RECONOCE un lenguaje L, si dada una entrada (w) en la cinta, la MT SIEMPRE se para, y lo hace en un EF si y sólo si: w ∈ L Una MT ACEPTA un lenguaje L, si dada una entrada (w) en la cinta, la MT se para en un Estado Final si y sólo si: w∈L Así, en este caso, si w ∉ L, la MT podría no parar. Ejs: MT que reconoce el lenguaje a*b*, MT que acepta el lenguaje anbncn …

Máquinas Transductoras Modifica el contenido de la cinta realizando cierta función. Modifica el contenido de la cinta realizando cierta función. Ejs: MT que sustituye los dígitos por cero, MT que añade un bit de paridad a la entrada, MT que duplica el número de 1s que hay en la cinta … Si la Entrada está bien formada: debe terminar en un Estado Final.

Si la Entrada No está bien formada: debe terminar en un Estado No Final.

Procedimiento de paso a paso del recorrido de una cadena

Realice de manera detallada y grafica el procedimiento paso a paso del recorrido de una cadena (La cadena la selecciona el estudiante, debe contener como mínimo 10 caracteres) en la máquina de turing. Describir cómo funciona el almacenamiento mediante el uso de las cintas, etc.

- Paso 1… Se digita la cadena 1100011000

- Paso 2… Vemos que se va a su estado inicial, escribe el símbolo 1

- Paso 3…

Escribe un nuevo valor de la cinta y borra el anterior, se mantiene en el mismo estado q0 y mueve la cabeza a la derecha

- Paso 4… Escribe un nuevo valor de 0 y la cinta borra el anterior, se mantiene en el mismo estado q0 y mueve la cabeza a la derecha

- Paso 5…

Escribe un nuevo valor de 0 y la cinta borra el anterior, se mantiene en el mismo estado q0 y mueve la cabeza a la derecha. Así se mantiene hasta que lee en blanco en la cinta.

- Paso 6… Lee una célula en blanco y cambia al estado q1 y mueve la cabeza a la izquierda.

- Paso 7… Escribe un nuevo valor de 0 y la cinta borra el anterior, y cambia al estado q2 y mueve la cabeza a la izquierda.

- Paso 8… Escribe un nuevo valor de 0 y la cinta borra el anterior, se mantiene en el mismo estado q2 y mueve la cabeza a la izquierda.

Así se mantiene hasta que lee un valor en blanco en la cinta.

Paso 9… Lee una célula en blanco y cambia al estado q4 y mueve la cabeza a la derecha.

Paso 10… Llega a su estado final q4, y escribe un 1, siendo la cadena valida

Practicar y verificar lo aprendido

Apoyándose en el simulador JFlap o VAS ejecutar y validar por lo menos cinco cadenas válidas y 5 cadenas rechazadas por la máquina. En este espacio adjunta la imagen.