• Categories
• Modelos de computación
• Ciencia cognitiva
• Sicología y ciencia cognitiva
• Física y matemáticas
• Matemática

Citation preview

UNIDAD 1: FASE 2 - CONOCER FORMALISMOS USADOS PARA DEFINIR LENGUAJES FORMALES

INTEGRANTES:

JUAN PABLO MORALES

Cod.1053770857

FABIAN LEONARDO GOMEZ Cod. 1.115.792.758 JAIRO ANDRES BENAVIDEZ Cod. 87.215.325 EDNA ROCIO CORTES HERNANDEZ Cod.1118025591

GRUPO 301405_47

TUTOR JHEIMER JULIAN SEPULVEDA

UNIVERSIDAD NACIONAL ABIERTA A DISTANCIA (UNAD) ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA (ECBTI) MARZO 12 DEL 2019

INTRODUCCION El curso de autómatas y lenguajes formales es esencialmente una metodología que permite el examen de distintos objetos o campos, en la perspectiva de emitir una opinión independiente sobre la validez científica y/o la técnica del sistema de control que gobierna una determinada realidad que pretende reflejar adecuadamente y/o cumple las condiciones que le han sido prescritas. En esta primera unidad nos permite ejecutar programas en los simuladores JFLAP, VAS. Para comprender como maniobra o se ejecuta una cadena a partir de una expresión regular, con paso a partir de un autómata finito determinístico a un autómata finito no determinístico. También vemos que al graficar el diagrama se tiene en cuenta un estado de inicio las transiciones y un estado final. En este trabajo encontraremos una serie de conocimientos y conceptos relacionados al estudio y desarrollo de la revisión del módulo de autómatas y lenguajes formales donde se dará a conocer los temas que aborda la unidad 1

OBJETIVOS

OBJETIVO GENERAL  Reconocer los lenguajes regulares, autómatas finitos y su aplicación. OBJETIVOS ESPECIFICOS  Estudiar la aplicación de los lenguajes regulares y los autómatas finitos.  Adquirir las habilidades necesarias para desarrollar autómatas y máquinas que reconozcan lenguajes o computen funciones.  Distinguir los diferentes tipos de lenguajes formales existentes.  Adquirir el conocimiento y competencia para poder recrear autómatas sencillos en un simulador. De igual forma verificar el lenguaje que reconoce.

EJERCICIOS DE LA FASE 2 Presentado por: EDNA ROCIO CORTES 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 1. Ejercicio 1

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

EJERCICIO TRABAJAR

A

Caracterización del autómata

-

Identificación del Autómata Finito Determinista o Autómata Finito No Determinista. Respuesta: El autómata del ejercicio 2 corresponde a un Autómata Finito No Determinista

-

Explicar las características del tipo de autómata Respuesta: Un autómata finito no determinista consta con las siguientes características: • •

Su transición desde un estado puede tener múltiples destinos. Permite transiciones con cadenas vacías.

•

Requiere menos espacio

Una cadena es aceptada si solo una de todas sus posibles transiciones es hacia un estado final. 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.

Procedimiento de - Paso 1:Lo primero que vamos a realizar es a través de método conversión de de eliminación de estados eliminamos 𝑞1 Autómata Finito a Expresión Regular paso a paso

Obtendríamos de q0 a q2 la transición 2+12*1 - Paso 2: Eliminamos q0 tendríamos

- Paso 3: ER=𝟏 ∗ (𝟐 + 𝟏𝟐 ∗ 𝟏) Autómata Final convertido Lenguaje regular

ER= 𝟏 ∗ (𝟐 + 𝟏𝟐 ∗ 𝟏) LR= {1} ∗ 2 + {1,2} + 1 ∗ {1}

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

Caracterización del autómata

En este espacio se realiza: - Autómata Finito No Determinista - Este es un autómata finito no determinista (AFND), puesto que como podemos ver el estado q0, q2,q3 posee dos transiciones.

Procedimiento de conversión paso a paso

Realice de manera detallada el procedimiento paso a paso de la conversión del autómata según corresponda y según ejemplo revisado. - Paso 1: Primero identificamos las transacciones entre los estados y los símbolos que maneja. a

b

q0 q1 q3 q2 q1, q3 q2,q3

q1, q3 ---------------------

----q2 q3,q2 ----q2,q3 q2,q3

- Paso 2: debemos reconocer cual es el estado inicial y cual el final. Estado inicial

Estado final

- Paso 3… Autómata Final convertido

Practicar y verificar lo aprendido

Resultado final de la conversión y validar por lo menos.

EJERCICIOS DE LA FASE 2 Presentado por: FABIAN LEONARDO GOMEZ CADENA 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 2. Ejercicio 2

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

Caracterización En este espacio se realiza: del autómata - Identificación del Autómata Finito Determinista o Autómata Finito No Determinista. Respuesta: El autómata del ejercicio 2 corresponde a un Autómata Finito No Determinista -

Explicar las características del tipo de autómata Respuesta: Un autómata finito no determinista consta con las siguientes características: • • • •

Su transición desde un estado puede tener múltiples destinos. Permite transiciones con cadenas vacías. Requiere menos espacio Una cadena es aceptada si solo una de todas sus posibles transiciones es hacia un estado final.

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: Eliminamos el estado “q1”

-

Paso 2: Eliminamos el estado “q0”

Autómata Final convertido

Lenguaje regular

Paso 3: Hallamos la expresión regular para el autómata. 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

2. Ejercicio 2

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

Caracterización En este espacio se realiza: del autómata - Identificación del Autómata Finito Determinista o Autómata Finito No Determinista. Respuesta: El autómata del ejercicio 2 corresponde a un Autómata Finito No Determinista -

Explicar las características del tipo de autómata

Respuesta: Un autómata finito no determinista consta con las siguientes características: Su transición desde un estado puede tener múltiples destinos. • Permite transiciones con cadenas vacías. • Requiere menos espacio • Una cadena es aceptada si solo una de todas sus posibles transiciones es hacia un estado final. Realice de manera detallada el procedimiento paso a paso de la conversión del autómata según corresponda y según ejemplo revisado. •

Procedimiento de conversión paso a paso

- Paso 1

a

b

q0

q1, q3

-

q1

-

q2

q2

-

q3

-

q2, q3

- Paso 2 a

b

q1, q3

-

q2, q3

q2, q3

-

q3, q2

q1, q3

-

q0

Autómata Final convertido

Practicar y verificar lo aprendido

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.

Autómata original

Autómata resultado final

EJERCICIOS DE LA FASE 2 Presentado por: JUAN PABLO MORALES 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 2.

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: EJERCICIO # 3

Caracterizaci ón del autómata

En este espacio se realiza: - Identificación del Autómata Finito Determinista o Autómata Finito No Determinista - Explicar las características del tipo de autómata Autómata finito No determinista Las características de este autómata son:  Posee cuatro transiciones desde “q0” para el símbolo de entrada “0”.  Las transiciones tienen múltiples destinos Se determinan los estados:  Q= q0, q1, q2  Estado inicial= q0  Estado final o aceptación= q2

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… - Paso 2… - Paso 3… Teniendo en cuenta el ejemplo revisado el procedimiento que se debe tener en cuenta para la

conversión de un autómata a expresión regular el siguiente:

es

- Paso 1. Eliminando q1 Quedándonos de la siguiente manera

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.

ER=(ab)*(a+ab)

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

EJERCICIO # 3

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 No Determinista -

Explicar las características del tipo de autómata

Características del autómata: • • • Procedimiento de conversión paso a paso

Su transición desde un estado puede tener múltiples destinos. Permite transiciones con cadenas vacías. Requiere menos espacio.

a A={0} U {2} B={1,3} U {-} B={1,3} U {-} ----C={2} U {2} ----D={2} U {-} -----

a

b C={2} U {2} D={2} U {-} ---------

b

>A B C D Autómata Final convertido

Practicar y verificar lo aprendido

B -------------

C D ---------

EJERCICIOS DE LA FASE 2 Presentado por: JAIRO ANDRES BENAVIDES 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 5. EJERCICIO 5

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla: EJERCICIO A Registre aquí el Ejercicio a trabajar. Por favor TRABAJAR agregue la imagen

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

-

Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino

Explicar las características del tipo de autómata Formalmente, una máquina de estados finitos es una 5-tupla (K, Σ, δ, s, F) donde:     

K es un conjunto finito de estados; Σ es un alfabeto finito de símbolos de entrada; s es el estado inicial en K; F es el conjunto de estados finales o de aceptación y (evidentemente) subconjunto de K. δ es la relación de transiciones, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.

5-tupla (K, Σ, δ, s, F) donde: M = ({q0, q1, q2}, {a, b, c}, δ, q0, {q2}) K = {q0, q1, q2} Σ = {a, b, c)

s = q0 F = q2 Donde la función δ: {q0, q1, q2} × {a, b, c} → {q0, q1, q2} viene dada por: Entrada a b c estado q0 q1 q2 q0 ∅ ∅ q1 q2 ∅ ∅ ∅ q2

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. El proceso que se realizara para la conversión a expresión regular se el método por eliminación de estados. - Paso 1: Procedemos eliminar q1

- Paso 2: En este paso eliminaremos q2

- Paso 3: En este paso quedaría q0 expresión regular de la siguiente forma

Autómata Final convertido

En este espacio se presenta la expresión correspondiente al autómata trabajado. ER= c*(b+ab)

Lenguaje regular

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

5. Ejercicio 5

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla: EJERCICIO A Registre aquí el Ejercicio a trabajar. Por favor TRABAJAR agregue la imagen

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 No determinista -

Procedimient o de conversión paso a paso

Explicar las características del tipo de autómata  Posee dos posibles transiciones desde “q0” para el símbolo de entrada “0”  Posee transiciones vacías

Realice de manera detallada el procedimiento paso a paso de la conversión del autómata según corresponda y según ejemplo revisado. - Paso 1… Se determinan los estados:  Q= q0, q1, q2, q3  Estado inicial= q0  Estado final o aceptación= q3 - Paso 2… Se determina= El alfabeto : ∑=0,1 Transición : λ - Paso 3…

Tabla de transición

A={0} U {3} B={0,2} U {3} C={0,1} U {3} D={0,1,3} U {3} E={0,2,3} U {3}

-

E={0,2,3} U {3} E={0,2,3} U {3} B={0,2} U {3}

1 C={0,1} U {3} D={0,1,3} U {3} C={0,1} U {3} C={0,1} U {3} D={0,1,3} U {3}

Paso 4… Cuadro de transición del autómata finito determinista

 A B C #D #E

Autómata Final convertido

0 B={0,2} U {3} B={0,2} U {3}

0 B B E E B

1 C D C C D

En este espacio se presenta el autómata final

Practicar y verificar lo aprendido

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. Cadena Autómata Autómata de inicial final validació (original) n 1110101 1

0010111

10000

101010

1110

1011101

Actividad Colaborativa 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. M= ({A, B, C}, {a, b}, δ, A, {A, C}) 2. Plasme la tabla de transición.

# →A B #C

a B -----

b C C ---

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. Formalmente, una máquina de estados finitos es una 5-tupla (K, Σ, δ, s, F) donde: K es un conjunto finito de estados; Σ es un alfabeto finito de símbolos de entrada; S es el estado inicial en K; F es el conjunto de estados finales o de aceptación y (evidentemente) subconjunto de K. δ es la relación de transiciones, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado. Ahora lo aplicamos a nuestro ejercicio. 5-tupla (k, £, δ, s, F) donde: M= ({A, B, C}, {a, b}, δ, A, {A, C}) K= {A, B, C} £= {a, b} s= A F= {A, C} Donde la función δ: {A, B, C} x {a, b} → {A, B, C} viene dada por: Conjunto A δ (A, a) = {B} δ (A, b) = {C} Conjunto B δ (B, a) = {--} δ (B, b) = {C} Conjunto C δ (C, a) = {--} δ (C, b) = {--} 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). Podemos ver el recorrido de la cadena a

Figura. 2(Realizando ingreso de entrada a). EN el autómata, ingresamos un elemento del alfabeto en este caso es “a”, como vemos puede finalizar en el estado.

Figura .3 (Entrada a). Ingresamos la entrada a, como vemos puede recorrer los estados A y B ya que como vemos con el elemento del alfabeto a, es una entrada para el estado B

Figura .4 (entrada b). Se ingresa la entrada b y como vemos es aceptada por el estado A

Figura .5(entrada b). Como vemos el estado C, acepta la entra b, por ende, la entrada b, recorre los estados A y C

Figura. 6(entrada ab) Se ingresa la entra ab, como vemos es aceptada por el estado inicial A.

Figura. 7(entrada ab) Se ingresa la entra ab, como vemos es aceptada por el estado inicial A, recorrer hacia el estado B.

Figura. 7(entrada ab) Se ingresa la entra ab, como vemos es aceptada por el estado inicial A, recorrer hacia el estado B y finaliza en el estado C

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).

Diagrama de Moore en JFALP

Similitudes

Diagrama de Moore en VAS

Diferencias

Las dos herramientas utilizan Java. JFlap, permite más funcionalidades que VAS, vas solo permite AFD y maquinas turin Las dos herramientas permite Vas no visualiza las transiciones diseñar autómatas AFND y AFD. por estado. Las dos herramientas permiten JFlap permite visualizar las entender las transiciones. aceptaciones de las entradas y visualizar su recorrido por estados, vas solo acepta entradas. Tienen diferentes entornos. JFlap, tiene un entorno más amigable y didáctico que VAS.

CONCLUSIONES Gracias al presente trabajo se logró aprender y apropiar conceptos de lo que son los autómatas y los lenguajes formales, revisando a profundidad el tema de lenguajes formales y autómatas, vemos la grandeza y complejidad que manejaban los grandes matemáticos entre ellos Alan Turing y Chomsky, Aprendimos a trabajar con herramientas que nos facilitaban la simplificación y proceso de un autómata dentro de la ingeniería computacional, estamos conscientes que es el inicio de la materia y que su complejidad ira en ascenso a medida que pasemos los niveles, excelente ejercicio para razonar matemáticamente.

BIBLIOGRAFÍA  Carrasco, R., Calera, R., Forcada, M. (2016). Teoría

De

Lenguajes, Gramáticas Y

Autómatas

Para Informáticos. Recuperado de

https://web-a-ebscohostcom.bibliotecavirtual.unad.edu.co/ehost/ebookviewer/ebook?sid=eb734de c-c0c7-4710-82153292d0b7acb4%40sessionmgr4009&ppid=pp_Cover&vid=0&format=EB

 Hernández, R. (2010). Practique lenguajes

formales.

(pp.

1

la

teoría

de

autómatas

y

-124). Recuperado

de https://ebookcentral-proquestcom.bibliotecavirtual.unad.edu.co/lib/unadsp/reader.action?docID=319984 5&ppg=10  Alfonseca, C., Alfonseca, M., Mariyón, S. (2009). Teoría de

autómatas y lenguajes formales. (pp. 7-797). Recuperado De https://ebookcentral-proquestcom.bibliotecavirtual.unad.edu.co/lib/unadsp/reader.action?docID=319512 9&ppg=6