• Categories
• Ciencias de la computación teórica
• Programación de computadoras
• Informática
• Áreas de la informática
• Tecnología

Citation preview

AUTOMATAS Y LENGUAJES FORMALES FASE 2 - CONOCER FORMALISMOS USADOS PARA DEFINIR LENGUAJES FORMALES

PRESENTADO POR: GABRIEL JAIME CHAVARRIA OCAMPO Código: 1036926740

GRUPO: 301405_19

TUTOR: JHEIMER JULIAN SEPULVEDA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA MARZO 2019

DESARROLLO DEL TRABAJO EJERCICIOS DE LA FASE 1 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

1. ACTIVIDAD 1: Conversión de un Autómata Finito a Expresión Regular

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 Ejercicio 5

Caracterización En este espacio se realiza: del autómata - Identificación del Autómata Finito Determinista o Autómata Finito No Determinista R/Autómata Finito Determinista

-

Explicar las características del tipo de autómata

Porque tiene todas sus transiciones no vacías y que por cada símbolo desde un estado de origen se llega a un único estado destino. Procedimiento de conversión de Autómata Finito a Expresión Regular paso a paso

Realice de manera detallada el procedimiento paso a paso de la conversión del autómata a expresión regular y según ejemplo revisado. - Paso 1… Se Calcula la primera ruta iniciando por el estado de entrada de q0 a el estado de aceptación q2, donde solo se hace transición por b, Según su representación

𝐪𝟎 → 𝐪𝟐 = 𝐛 - Paso 2… Se Calcula la segunda ruta iniciando por el estado inicial q0 pasando por el estado q1 y llegando finalmente al estado de aceptación q2. de q0 a q1 va por a y de q1 a q2 va con b. lo representamos así

𝐪𝟎 → 𝐪𝟏 → 𝐪𝟐 = 𝐚 𝐛 - Paso 3… Luego se suman los dos caminos encontrados: para hallar la expresión regular.

𝐄𝐑 = 𝐛 + 𝐚𝐛 Autómata Final convertido

Lenguaje regular

En este espacio se presenta la expresión correspondiente al autómata trabajado.

En este espacio agrega el lenguaje correspondiente a la expresión regular.

{ 𝒃 } ∪ { { 𝒂 } ∪ { 𝒃} }

regular

ACTIVIDAD 2: Conversión de Autómatas Finitos Deterministas a Autómatas Finitos No deterministas (AFD a AFND) y viceversa 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 1. Ejercicio 5

Caracterizació n del autómata

En este espacio se realiza: - Identificación del Autómata Finito Determinista o Autómata Finito No Determinista R/ Autómata Finito determinista -

Procedimiento

Explicar las características del tipo de autómata

Porque Cada estado tiene determinado hacia dónde ir. Ejemplo q0 vaya por la transición 1 solo va ir a q1 no tiene otro camino hacia donde ir Realice de manera detallada el procedimiento paso a

de conversión paso a paso

paso de la conversión del autómata según corresponda y según ejemplo revisado. - Paso 1… Los primero que hacemos es desplegar el estado normal por lo cual creamos otros estados para que se puedan dar la conversión.

Ahora comenzamos a eliminar estados iniciamos con q1

- Paso 2… Luego nos queda un nuevo estado el cual desplegamos para comenzar a eliminar los nuevos estados de q2

Ahora comenzamos la eliminación al estado q2

- Paso 3… Luego nos queda un nuevo estado el cual desplegamos para comenzar a eliminar los nuevos estados del estado final q3

Ahora comenzamos la eliminación al estado final q3

- Paso 4… Por ultimos nuevo estado el cual desplegamos para comenzar a eliminar el estado final q3

Como resultado nos queda la expresión regular: Autómata Final convertido

Practicar y verificar lo aprendido

(0+(11)+(00))+(01(ʎ))(01)*(1) En este espacio se presenta el autómata final

Apoyándose en el simulador JFlap o VAS ejecutar los dos autómatas, el original y el autómata resultado final de la conversión y validar por lo menos tres cadenas válidas y tres cadenas rechazadas.

En este espacio agregar las imágenes tomadas del simulador utilizado.

Preguntas de control 1. Dentro de las aplicaciones de autómatas se tiene: A. Alimentación B. Medicina C. Fabricación de calzado D. Educación

2. Dentro de la clasificación jerárquica de los autómatas se encuentran los intermedios en primer nivel, a su vez dentro de ellos están: A. Memoria Linealmente limitada B. Autómatas Finitos C. Máquinas de Turing D. Códigos convolucionales 3. Cuando se realiza la Conversión de AFN a AFD con transiciones vacías el resultado de C = {1, 3, 4} U {0, 1, 3} con transición X es: D = {1,2,3,4} U {0,1,3} C = {1,3,4} U {0,1,3} B = {1,2} U {0,1,3} D = {1,2} U {0,1,3} 4. Teniendo en cuenta la siguiente imagen cual es la respuesta:

A.

B.

C.

D.