• Author / Uploaded
• Herick Perez Lopez

• Categories
• Áreas de informática
• Informática
• Tecnología
• Ciencias de la Computación
• Ingeniería Informática

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

Ejercicio 3

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 -

Mediante la definición formal explicar las características de la

de la máquina de Turing

máquina de Turing. Máquina de Turing 𝑀𝑇 = (𝐾, ∑, 𝑇, 𝛿, 𝑆, 𝐵, 𝐹)

𝐾 ∑ 𝑇 𝑆 𝐹

= {𝑞0 , 𝑞1 } Estados = {𝑎, 𝑏, 𝑐} Alfabeto de entrada = {1, □} Alfabeto de la pila = {𝑞0 } Estado inicial = {𝑞1 } Estado final

δ= δ= δ= δ= δ= -

Funciónes de transición {𝑞0 , 𝑎} = {𝑞0 , 1, 𝑅} {𝑞0 , 𝑏} = {𝑞0 , 1, 𝑅} {𝑞0 , 𝑐} = {𝑞0 , 1, 𝑅} {𝑞0 , □} = {𝑞1 , □, 𝑆}

Realizar un cuadro donde explique las diferencias y similitudes de las máquinas reconocedoras y Transductoras Reconocedora Reconoce o acepta un lenguaje L Acepta el lenguaje L si dada una entrada en la cinta la máquina siempre se detiene y lo hace en un estado final si la entrada pertenece al lenguaje, si no pertenece al lenguaje podría no parar.

Transductora Modifica el contenido de la cinta realizando una cierta función. 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 crea una cinta con el alfabeto requerido:

-

Paso 2: La máquina lee de izquierda a derecha, de acuerdo al primer carácter leído 𝑎:

La transición indica que {𝑞0 , 𝑎} = {𝑞0 , 1, 𝑅}, esto quiere decir que la máquina permanece en el estado inicial 𝑞0 , y la cinta es sobrescrita con 1 y cambia al carácter de la derecha 𝑅:

-

Paso 3: La máquina lee el siguiente carácter 𝑏:

La transición indica que {𝑞0 , 𝑏} = {𝑞0 , 1, 𝑅}, esto quiere decir que la máquina permanece en el estado inicial 𝑞0 , la cinta es sobrescrita con 1 y cambia al carácter de la derecha 𝑅:

-

Paso 4: La máquina lee el siguiente carácter 𝑐:

La transición indica que {𝑞0 , 𝑐} = {𝑞0 , 1, 𝑅}, esto quiere decir que la máquina permanece en el estado inicial 𝑞0 , la cinta es sobrescrita con 1 y cambia al carácter de la derecha 𝑅:

-

Paso 5: La máquina lee el siguiente carácter {□}:

La transición indica que {𝑞0 , □} = {𝑞1 , □, 𝑆}, esto quiere decir que la máquina permanece cambia al siguiente estado 𝑞1 , estado final, la cinta permanece con el mismo carácter y la maquina termina su ciclo. Debido a que la cinta es infinita, mientras en esta sigan apareciendo los caracteres {𝑎, 𝑏, 𝑐} la maquina seguirá en estado inicial, al leer el carácter {□} la maquina cambia a estado final y habrá terminado un ciclo.

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.

1. La máquina de Turing creada en el ejemplo es una maquina es:

A. Máquina transductora B. Maquina reconocedora C. Maquina calculadora D. Máquina estabilizadora 2. En la máquina de Turing creada de ejemplo el símbolo que representa la cita es: A. B. C. D.

1 A L a

3. En la máquina de Turing creada de ejemplo la cadena que se ejecuta es: A. aa B. aab C. baa D. ab 4. En el ejercicio desarrollado es el video de Códigos Convolucionales Tellis y Viterbi la cadena que se utiliza es: A. B. C. D.

10100110 10010110 11010010 01011001