Fase 1 Grupo 301405_7 2e6v2r

Fase 1: Debatir y desarrollar los ejercicios planteados sobre lenguajes y expresiones regulares.

Yesika Paola Becerra Castro Código: 1.052.405.119 Brayan Lewis Muñoz Rivas Código: 1.028.025.777 Wilfredo Martínez González Código: 71.385.518 Diego Libardo Ulloa Prada Código: 13.271.220 Andres Felipe Bernal Franco Código: 9.861.104

Universidad Nacional Abierta Y A Distancia UNAD Escuela de Ciencias Básicas, Tecnología e Informática Colombia Octubre 2017

Fase 1: Debatir y desarrollar los ejercicios planteados sobre lenguajes y expresiones regulares.

Yesika Paola Becerra Castro Código: 1.052.405.119 Brayan Lewis Muñoz Rivas Código: 1.028.025.777 Wilfredo Martínez González Código: 71.385.518 Diego Libardo Ulloa Prada Código: 13.271.220 Andres Felipe Bernal Franco Código: 9.861.104

Autómatas y lenguajes formales Grupo 301405_7 Docente Víctor Fernando Canon Rodríguez

Universidad Nacional Abierta Y A Distancia UNAD Escuela de Ciencias Básicas, Tecnología e Informática Colombia Octubre 2017

Introducción.

En el siguiente trabajo se desarrollara la actividad Colaborativaindividual fase 1: Explorar. Debatir y desarrollar los ejercicios planteados sobre lenguajes y expresiones regulares. Solicitada en la guía integrada de actividades del curso Autómatas y lenguajes formales. El curso hace parte del campo de formación profesional básico del Programa de Ingeniería de Sistemas con un valor académico de tres (3) créditos académicos, dividido en tres unidades didácticas. Así: Unidad 1. Los lenguajes regulares para la construcción de analizadores léxicos. Unidad 2. Los lenguajes independientes del contexto para la construcción de analizadores sintácticos. Unidad 3. Didáctica (Lenguajes estructurados por frases incluidas las máquinas de Turing), son fundamentales para el estudio de la computabilidad y complejidad de problemas. Para el desarrollo óptimo del siguiente trabajo individual, es necesario dar solución a los tres ejercicios solicitada en la guía de actividades del curso.

1

Fase 1: Fase 1: - Debatir y desarrollar los ejercicios planteados sobre lenguajes y expresiones regulares. Ejercicio 1: Teniendo en cuenta el autómata realizar paso a paso el procedimiento de

1. Hallar la expresión regular 

Procedimiento

2

Eliminando q2



Procedimiento

3

Eliminado q3



Procedimiento

4

Eliminando q4

La expresión regular del autómata es = (a+ab(b)+a(ab))* 2. Hallar el lenguaje regular  Extensión A = [Autómata que empieza y termina en a]  Compresión = A [a] 3. Justificar el tipo de autómata que es  Es un autómata finito determinista, porque cada uno de los estados tiene 2 transiciones que llegan a diferentes estados

AUTÓMATA FINITO DETERMINÍSTICO

Autómata

Hallar la expresión regular (ER)

q

δ

(q,δ)

q0

a

q4

q0

b

q3

q2

a

q0

q2

b

q3

q3

a

q3

q3

b

q2

q4

(a+b)

q3

∗

𝐸𝑅(𝐴) = ((𝑎(𝑎 + 𝑏)(𝑎 + 𝑏𝑏) 𝑏𝑎) + (𝑏(𝑎 + 𝑏𝑏)∗ 𝑏𝑎)) Hallar el lenguaje regular

∗

𝐿(𝐴) = ([𝑎])

5

Es un Autómata Finito Determinístico (AFD): debido a que para cada transición se asigna sólo un estado Justificar el tipo de siguiente, por lo que se puede prever fácilmente los autómata que es caminos que recorrerá según el símbolo leído, además no existen transiciones vacías en él.

Ejercicio 2 Realizar la conversión del siguiente autómata, si el autómata es AFD convertirlo a AFND y si es AFND convertirlo a AFD, se debe mostrar el procedimiento paso a paso

AFND porque tiene una transición vacía y un estado que nos lleva a dos estados diferentes con la misma función 

Paso 1

Realizar la tabla de transiciones 0

1

0 = {0} U Φ

1=Φ

2 = {0,1} U Φ

1=Φ

1=Φ

1=Φ

2 = {0,1} U Φ

1=Φ

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

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

0 = {0} U Φ

4 = {0,1,2,3} U {1}

6

4 = {0,1,2,3} U {1}

5 = {0,2} U {1}

4 = {0,1,2,3} U {1}

5 = {0,2}U {1}

0 = {0} U Φ

4 = {0,1,2,3} U {1}

Reducir tabla de transición 0

1

0

1

2

1

1

1

2

1

3

3

0

4

4

5

4

5

0

4

El autómata finito determinista quedaría de la siguiente manera 0

1

-0

1

2

1

1

1

#2

1

3

#3

0

4

#4

5

4

#5

0

4

7

Ejercicio 3 Teniendo en cuenta el ejercicio anterior, seleccionar el autómata finito determinista (AFD). Con base a este autómata desarrolle 1. Describa la forma matemática del autómata  El autómata finito determinista (AFD) se define como una quíntupla M (Σ, Q, δ, q0, F) 2. Plasme la tabla de transición q

Ó

Δ(q, ó)

q0

0

q1

q0

1

q2

q2

0

q1

q2

1

q3

q3

0

q0

q3

1

q4

q4

1

q4

q4

0

q5

q5

0

q0

8

q5

1

q4

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  Σ = {0,1} Es el alfabeto del autómata  Q = {q0,q1,q2,q3,q4,q5} Es un conjunto finito o vacío de estados, es decir, 0 < |Q | <∞  δ= δ (q0,0) = q1 δ (q0,1) =q2 δ (q2,0) =q1 δ (q2,1) =q3 δ (q3,0) =q0 δ (q3,1) =q4 δ (q4,0) =q5 δ (q4,1) =q4 δ (q5,0) =q0 δ (q5,1) =q4 Función de transición, para cada estado y cada símbolo una transición  

q0 = q0 Estado inicial del autómata F = {q2,q3,q4,q5} conjunto de estados finales del autómata

4. Muestre en el simulador (gráficamente) como recorre una cadena valida. Explique cada secuencia.(No se trata solo captura las imágenes, estas deben ser explicadas en pie de página o de la contrario no tienen validez



Cadena “1”, empieza en q0 y termina en q2

9

10



Cadena “11” empieza en q0 pasa a q2 con 1 y a q3 con 1

11

12



Cadena “111” empieza en q0 pasa a q2 con 1 , a q3 con 1 y a q4 con 1

13

14



Cadena “1110” o “11111110”, porque q4 puede o no puede existir 1, entonces la cadena “1110” la leerá correctamente, la estrella de kleen en q4 se está refiriendo puede existir 0 o muchas veces, pasamos de q0 a q5 Cadena “1110”

15

16

17

Cadena “111111110”

18

19

20

En las siguiente grafica podemos visualizar en q4, que pasara 4 veces en q4 y después termina en q5

21

22

Recorreremos todo el autómata con la siguiente cadena “1101110011101000” La cadena recorre: q0 a q2, q2 a q3, q3 a q0, q0 a q2, q2 a q3, q3 a q4, q4 a q5, q5 a q0, q0 a q2, q2 a q3 , q3 a q4 , q4 a q5, q5 a q4 , q4 a q5, q5 a q0 y q0 a q1

23

24

25

26

27

28

29

30

31

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

32

Bibliografía. Hernández, R. (2010). Practique la teoría de autómatas y lenguajes formales. (pp. 1 -124). Recuperado del siguiente enlace: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=10566114&ppg= 10

Alfonseca, C., Alfonseca, M., Mariyón, S. (2009). Teoría de autómatas y lenguajes formales. (pp. 7-797). Recuperado del siguiente enlace: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=10498456&ppg= 6

Millán, J., Antonio J. (2009). Compiladores y procesadores de lenguajes. (pp. 28-62). Recuperado del siguiente enlace: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/detail.action?docID=10844351

Ferrando, J.C., and Gregori, V. (2012). Matemática discreta (2a. ed.). (pp. 207-232). Recuperado del siguiente enlac http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?ppg=260&docID=10751 543&tm=1481476339478

33

Alemán. H. [Helena]. (2017, Junio 19). Conceptualización de autómata [Archivo de video]. Recuperado del siguiente enlace: https://www.youtube.com/watch?list=PLYIk_3YB0nVyiNMAdrgiv0EoSHZtNto&v=z MhwYlXAHE4

González, A. [Ángela]. (2016, mayo 30). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista [Archivo de video]. Recuperado del siguiente enlace: https://www.youtube.com/watch?v=29Qp_AWXFt4

González, A. [Ángela]. (2016, mayo 30). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista con transiciones vacías – Método 1. [Archivo de video]. Recuperado del siguiente enlace: https://www.youtube.com/watch?v=NF47BSorRfU

González, A. [Ángela]. (2016, junio 6). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista con transiciones vacías – Método 2. [Archivo de video]. Recuperado del siguiente enlace: https://www.youtube.com/watch?v=KhgMam0DMmM

González, A. [Ángela]. (2016, Mayo 30). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista con transiciones vacías – Método 1. [Archivo de video]. Recuperado de https://youtu.be/NF47BSorRfU

34

Conversión de AFD a expresión regular, recuperado de http://conferencia2.unad.edu.co/p77tscx2n8p/?OWASP_CSRFTOKEN=7937483ee29cb2b 2a01de48f0086fc4d743e43f9e5e8d3140001806b02720b08

35