Fase1_grupo52 1m5p3c

AUTOMATAS Y LENGUAJES FORMALES Fase 1 Debatir y desarrollar los ejercicios planteados sobre lenguajes y expresiones regulares

Presentado por: JOHN MAURICIO TEJADA GUTIERREZ LIEVER ROJAS SCARPETA JAMER DAVID VILORIA JULIO

Cód. 4520348 Cód. 1075283152 Cód. 1118808074

Presentado a: Tutor EDGAR ANTONIO CORTES

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD ESCUELA DE CIENCIAS BASICAS, TECNOLOGIA E INGENIERIA ECBTI 2018 – 3

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

Ejercicio

1y9

Ejercicio 1

2y8

Ejercicio 2

3y7

Ejercicio 3

4y6

Ejercicio 4

5y0

Ejercicio 5

ACTIVIDAD 1: Conversión de un Autómata Finito a Expresión Regular El diseño solicitado corresponde al diligenciamiento de la siguiente tabla: Registre aquí el Ejercicio a trabajar. Por favor agregue la imagen / Ejercicio No.2

Ejercicio a Trabajar

Caracterización del autómata

En este espacio se realiza: - Identificación del Autómata Finito Determinista o Autómata Finito No Determinista Autómata Finito Determinista (AFD) q  (q, ) q0 a q1 q0 B q2 q1 a q1 q1 B q2 - Explicar las características del tipo de autómata Es un Autómata Finito Determinista, ya que desde q0 puedo ir a q1, pero desde q0 también puedo ir a q2, pero

siempre nos permitirá conocer el siguiente estado. 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. Por medio de eliminación de estado, Eliminamos q1, ya que no es única salida para llegar a q2. Lo que equivaldría a: A estrella de Kleene, + b (Dirección q0 a q2)+ab (Dirección q0 a q1 y q1 a q2). Procedimiento de conversión de Autómata Finito a Expresión Regular paso a paso

- Paso 2. Por medio de eliminación de estado, eliminamos a q0

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

En este espacio agrega el lenguaje correspondiente a la expresión regular. Lenguaje regular ER= a*(b+ab)

regular

Actividad 3: Teniendo en cuenta los ejercicios desarrollados por los estudiantes el Grupo, selecciona uno de los autómatas finitos deterministas (AFD). Con base en ese autómata desarrollan: 1. Describa la forma matemática del autómata, Es un Autómata Finito Determinista, ya que desde q0 puedo ir a q1, pero desde q0 también puedo ir a q2, pero siempre nos permitirá conocer el siguiente estado. 𝑄 = {𝑞0, 𝑞1, 𝑞2} Estados del Autómata. 𝑞0 = Estado Inicial. Σ = {𝑎, 𝑏} Alfabeto del autómata. 𝐹 = {𝑞3} Estados Final del Autómata. 𝛿 = Transiciones 𝛿(𝑞0, 𝑎) = 𝑞1 𝛿(𝑞0, 𝑏) = 𝑞2 𝛿(𝑞1, 𝑎) = 𝑞1 𝛿(𝑞1, 𝑏) = 𝑞2 𝐴 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹)

2. Plasme la tabla de transición. Autómata Finito Determinista (AFD) q  (q, ) q0 a q1 q0 b q2 q1 a q1 q1 b q2 𝛿(𝑞0, 𝑎) = 𝑞1 𝛿(𝑞0, 𝑏) = 𝑞2 𝛿(𝑞1, 𝑎) = 𝑞1 𝛿(𝑞1, 𝑏) = 𝑞2 3. Identifique los elementos (tupla, estado final, inicial, alfabeto, etc.). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales. El autómata es un autómata finito determinista y se puede definir como una quíntupla, ya que esta posee cinco elementos: estados, estado inicial, estados finales, alfabeto, y transiciones. Estados (Q): son nodos o estaciones de recorrido del autómata. Estado inicial (q0): Es el estado donde inicia el recorrido del autómata. Estados Finales (F): Es el estado donde termina y es aceptado el recorrido del autómata. Alfabeto (∑): Son los valores o símbolos que le ingresan al autómata para realizar su recorrido.

Transiciones (δ): Es el paso a paso, de todos los posibles recorridos que puede tener el autómata. 4. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben ser explicadas en pié de página o de lo contrario no tienen validez)

5. Muestre el diagrama de Moore generado en JFLAP y en VAS y comente tres similitudes y tres diferencias que encuentra al realizarlo en los dos simuladores. (Ventajas que ofrezca uno u otro).

REFERENCIAS BIBLIOGRAFICAS Gonzalez Amarillo, A. M. (01 de Julio de 2018). Lenguaje regular. Obtenido de http://hdl.handle.net/10596/18315 MonitoresUCaldas. (18 de Actubre de 2013). Convertir un Automata No determinista a Determinista. Obtenido de Youtobe: https://www.youtube.com/watch?v=6YeeMQPuGeo