• Author / Uploaded
• Andrey Hinestroza

• Categories
• Formalismo (deductivo)
• Informática teórica
• Modelos de computación
• Métodos formales
• Teoría de la computación

Citation preview

Fase 5 - Desarrollar aplicaciones con Autómatas

ANDREY HINESTROZA COD: 29344645 DIEGO MISAEL GUIO NIÑO COD: 7185489 JEFFERSON CASTIBLANCO COD: 1020764041

GRUPO: 301405_24

Presentado a ROLANDO FABIAN JUNCO

Universidad Nacional Abierta y a Distancia UNAD ESCUELA DE INGENIERIA Y CIENCIAS BASICAS Julio del 2019

Introducción

En el presente documento se puede referenciar y así mismo evidenciar el desarrollo de los ejercicios propuestos para esta guía de la Fase 5 – desarrollo de aplicaciones con Autómatas, con base en la Guía de actividades y rúbrica de evaluación - Fase 5 - Desarrollar aplicaciones con Autómatas, donde se describe la construcción de gramáticas y autómatas mediante los mecanismos de representación formal, donde se logran identificar las características y de los autómatas finitos y no finitos determinísticos, el funcionamiento de las máquinas de Turing, la identificación de los elementos de quíntupla, la creación de tabla de transiciones, la minimización de un autómata para lograr hallar su expresión y lenguaje regular y el desarrollo de autómatas de pila.

Tabla de contenido Introducción .........................................................................................................................................2 Actividades Colaborativas: ...............................................................................................................4 Paso 1: .................................................................................................................................................4 Ejercicio 1: ......................................................................................................................................4 Ejercicio 2 .......................................................................................................................................6 Ejercicio 3. ......................................................................................................................................7 Ejercicio 4 .......................................................................................................................................9 Ejercicio 5 .....................................................................................................................................10 Paso 2 ................................................................................................................................................13 Ejercicio 2: ....................................................................................................................................13 Ejercicio 3: ....................................................................................................................................14 Ejercicio 4: ....................................................................................................................................17 Ejercicio 5 .....................................................................................................................................17 Conclusiones .....................................................................................................................................21 Bibliografía .......................................................................................................................................22

Actividades a desarrollar Actividades Colaborativas: El trabajo se desarrolla demostrando el procedimiento realizado paso a paso, no se tendrá en cuenta las respuestas o simulaciones en jFlap o VAS. Paso 1:

Ejercicio 1:

De cada uno de los siguientes autómatas, realizar el procedimiento paso a paso de hallar la expresión regular, el lenguaje regular y explicar el tipo de autómata que es:

TIPO DE AUTOMATA Este es un autómata finito no determinista AFND. -

Ya que tiene transiciones de un estado con mas de una letra. De q0 va con la letrea

del alfabeto a hacia q0 y a q2, con la letra b va desde q0 a q1 y q2.

Paso 1: - q0,q1,q2: Estados - q0: Estado inicial - q1: Estado final

- {a,b}: letras del alfabeto y cadena de caracteres

Minimizar.

Ya minimizado el autómata, podemos decir que su expresión regular es: ER: a*(b+ab)(b|a) LR: a+{b}+{ab}{b|a}

Ejercicio 2

Tenemos un autómata finito determinista, ya que ninguna de sus transiciones va de un estado a otro estado con la misma letra o alfabeto.

Tenemos una 5-tupla (K, Σ, δ, s, F)

M: {q0,q1,q2},{a,b},q0,{q1} K: {q0,q1,q2} Estados Σ: {a,b} alfabeto S: q0 estado inicial F: q1 estado final

Para hallar la expresión regular tenemos que minimizar, podemos empezar por:

ER: b*(ab+b+b) LR: {b*}[{ab}+{b}+{b}]

Ejercicio 3.

Tipo de autómata: 

De acuerdo con el autómata representado en el ejercicio 3, tenemos que es un autómata finito determinístico, ya que para cada una de las transiciones tenemos que se traslada con solo una letra por cada uno de los estados de transición.

5-tupla (K, Σ, δ, s, F): 

M: {q0, q1, q2}, {a, b} ρ: q0, {q2}

   

K: {q0, q1, q2} - Estados Σ: {a, b} - alfabeto S: q0 - estado inicial F: q2 - estado final

Tabla de transiciones: ẟ (q0, b) = q1 ẟ (q1, a) = q0 ẟ (q1, b) = q2 ẟ (q2, b) = q0 Minimización del autómata, hallar Lenguaje Regular y Expresión Regular:

ER: b*(a + b + b) LR: {b*} [{a}+{b}+{b}]

Ejercicio 4

El autómata que vamos a explicar corresponde a un autómata finito determinista AFD, ya que podemos observar que no hay más de 2 transiciones con la misma letra de un estado a otros.

Tenemos una 5-tupla (K, Σ, δ, s, F)

M: {q0,q1,q2,q3},{a,b},q0,{q3} K: {q0,q1,q2,q3} Estados Σ: {a,b} alfabeto S: q0 estado inicial F: q3 estado final

Por eliminación

Eliminamos q0, ya que por el mismo camino podemos llegar a q1.

Eliminamos q1, ya que podemos ir a q3 desde q2, quedando la siguiente expresión regular:

ER:a+b+ab+b LR: {a+b+(ab)+b}

Ejercicio 5

Tipo de autómata: De acuerdo con el autómata representado en el ejercicio 5, tenemos que es un autómata finito NO determinístico, ya que por lo menos uno de sus estados se traslada con la misma letra hacia dos estados diferentes, como es el caso del estado q2 que se traslada con la letra a desde el

estado q2 con estrella de kleene y la letra a hacia el mismo estado q2 y con la misma letra q se traslada hacia el estado q3. 5-tupla (K, Σ, δ, s, F): 

M: {q0, q1, q2, q3}, {a, b} ρ: q0, {q3}



K: {q0, q1, q2, q2} - Estados



Σ: {a, b} - alfabeto



S: q0 - estado inicial



F: q3 - estado final

Tabla de transiciones:

ẟ (q0, a) = q1 ẟ (q0, b) = q2 ẟ (q1, b) = q3 ẟ (q2, a) = q2 ẟ (q2, b) = q2 ẟ (q2, a) = q3

Minimización del autómata, hallar Lenguaje Regular y Expresión Regular:

ER: ab*(a + b + b +a) LR: {ab*} [{a}+{b}+{b}+{a}]

Paso 2

Ejercicio 2: Realizar la conversión de AFD a AFND o de AFND a AFD según corresponda. Teniendo en cuenta que nuestro autómata es un autómata finito determinístico, vamos a proceder a realizar nuestra tabla de transiciones y proceder con la conversión a un autómata finito no determinístico.

Ejercicio 3: Realice la minimización paso a paso del autómata finito determinista: 1.Describa la forma matemática del autómata

A= [(q0, q1, q2, q3, q4, q5), (a, b), q0, q1, δ] K= (q0, q1, q2, q3, q4, q5) Σ= (a, b) SϵA= q0 F⊆A= q0, q1 2. Plasme la tabla de transición.

q0 q1 q2 q3 q4 q5

a Q1 Q1 Q0 Q1 Q1 Q3

b

λ

--

---

Q2 Q0 Q2 Q3 Q4

Q4

Q4

Es un autómata finito determinista ya que ningún estado hacer transición a otro estado con la misma letra.

Minimización

Por el método de eliminación iniciamos con q5, ya que por este se pude realizar la transición a q3. Quedando b + ab.

Seguimos eliminando q0, ya que las transiciones realizadas desde q2 a q1 pasa por q0.

Seguimos eliminado q2, que tenía las transiciones desde q3 con b a q2 y con a q1 y de q1 a q2.

Se elimina q3, ya que la transición de q4 a q1 pasando por q3, sigue la misma ruta. ER: a*(a + ab) + (a + b + (b + (ab) + a) LR: {a*} [{a + ab} + {a + b + {b + {ab} + a}] Ejercicio 4: Realizar el autómata a Pila de L = {(ab+cn)*} Ejercicio 5: Realizar una máquina de turing de autoría propia y realice: a. Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la cinta como en la secuencia de entrada. b. Identifique una cadena que no sea válida y justifique el porqué. c. Ejecute el RunTest a una cadena aceptada que tenga los menos cinco símbolos. d. Identifique en qué momento la máquina se detiene.

a. Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la cinta como en la secuencia de entrada. La cadena ingresada es 10.

Recibe como entrada un 1.

Pasa la cinta a un 0 y se queda en 𝑞0.

Llega a q1 cambiando un 0 por 1 y avanza a la derecha.

Después reemplaza a 1 por 1 y retrocede.

Después reemplaza a 1 por vacío y avanza a la izquierda, llegando al estado q3.

Después reemplaza a 1 por vacío y avanza a la izquierda llegando al estado q4.

Después reemplaza a vacío por vacío y avanza a la izquierda llegando a q5.

Después reemplaza a vació por vació y avanza a la izquierda llegando a q6 que es el estado aceptador.

Conclusiones

Se concluye que, con el desarrollo de las actividades anteriormente indicadas, trabajamos o colocamos en práctica las temáticas aprendidas de las tres unidades del curso de autómatas y lenguajes formales.

Bibliografía

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

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

González, A. (2017). Minimización de un autómata. Recuperado de: https://youtu.be/eOynYG8Ibk0