• Author / Uploaded
• brayan

• Categories
• Modelos de computación
• Informática
• Teoría de la computación
• Física y matemáticas
• Matemática

Citation preview

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 |