• Author / Uploaded
• ANYERINA PAOLA CABARCAS DIAZ

Citation preview

Fase 5 - Desarrollar aplicaciones con Autómatas

Francisco Javier Guzmán Polo, código: 72208315 Rossihell Gutiérrez Cotes, Código: 1067719954 Yeimy Bianney Gómez Méndez Maira Alejandra Castro Ochoa, código 1007316924

No. De Grupo: 44

Rolando Fabian Junco Docente Tutor

Universidad Nacional Abierta Y A Distancia Escuela de Ciencias Básicas, Tecnología e Ingeniería Autómatas y Lenguajes Formales Diciembre 2019

Introducción

El presente trabajo esta realizado con el fin de poner en practica lo estudiado en las unidades 1, 2 y 3 visto durante el curso, en la cual se busca desarrollar autómatas aplicaciones con autómatas, realizando el procedimiento paso a paso de hallar la expresión regular, el lenguaje regular e identificando el tipo de autómata, además de abordar los temas de conversión, minimización , autómata de pila y la máquina de Turing, mostrando lo aprendido durante el curso.

Actividades a desarrollar

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: Expresión regular: Estado inicial: q0 Estados finales: q4 Se puede llegar por diferentes caminos al estado de aceptación q4 Primer camino de q0 a q1 a q4 =10 Segundo camino de q0 a q2 a q4 =00 Tercer camino de q2 a q0 a q1 a q4=110 Cuarto camino de q1 a q4=10 ER=1*0(10+00+110)

1.

2.

Lenguaje regular: LR = 1*0.{10,00,110} M : (∑, K, δ, q1, F) ∑ = {0,1} s ∊ K : q0 F ⊆ K : {q4} δ : K x {∑ ⋃ ∊} → P(K) : {(q0,1,q1),(q0,0,q2),(q1,1,q1),(q1,0,q4), (q2,1,q0), (q2,0,q4) } Explicar el tipo de autómata: Es un autómata finito determinístico: La transición no se repite desde un estado a otro con el mismo carácter del alfabeto, Expresión regular: Estado inicial: q0 Estados finales: q4 Se puede llegar por diferentes caminos al estado de aceptación q4 Primer camino de q0 a q4 =1 Segundo camino de q0 a q2 a q4 =00 Tercer camino de q4 a q4=0 Cuarto camino de q2 a q0 a q4=11 Quinto camino de q4 a q0 a q2 a q4=100

ER=0*(1+00+0+11+100) Lenguaje regular: LR = 0*{1,00,0,11,100} M : (∑, K, δ, q1, F) ∑ = {0,1} s ∊ K : q0 F ⊆ K : {q4} δ : K x {∑ ⋃ ∊} → P(K) : {(q0,1,q4),(q0,0,q2),(q2,1,q0),(q2,0,q4), (q4,1,q0), (q4,0,q4)} Explicar el tipo de autómata: Es un autómata finito determinístico: porque para cada estado existe siempre no más de una transición posible desde ese estado y con ese mismo símbolo Expresión regular: Lenguaje regular: Explicar el tipo de autómata: 3. Expresión regular: Lenguaje regular: Explicar el tipo de autómata: 4.

5.

Expresión regular: Estado inicial: q0 Estados finales: q1 y q2 𝑞0 = 1𝑞0 + 0𝑞2 + 0𝑞1 𝑞1 = 1𝑞3 𝜆 𝑞3 = 1𝑞2 𝑞2 = 𝜆 Reemplazando q2 en q3 => 𝑞3 = 1 q3 en q1 => 𝑞1 = 11 q1 y q2 en q0 => 𝑞0 = 1𝑞0 + 0 + 011 Al aplicar el lema de Arden en

𝑞0 = 1𝑞0 + 0 tenemos: 𝑬𝑹 = 𝟏∗ 𝟎 + 𝟎𝟏𝟏 Con el Método de eliminación de estados obtenemos: Se elimina q3

Se elimina q1

Se elimina q0

ER=1*0+011 Lenguaje regular: LR = 1*.{0,011} = {1}*.({0}⋃{011}) M : (∑, K, δ, q1, F) ∑ = {0,1} s ∊ K : q0 F ⊆ K : {q1,q2} δ : K x {∑ ⋃ ∊} → P(K) : {(q0,1q0),(q0,0,q1),(q0,0,q2),(q1,1,q3),(q3,1,q2) } Explicar el tipo de autómata: Es un autómata finito no determinista: La transición se repite desde un estado a otro con el mismo carácter del alfabeto, en este caso se observa que el estado q0 sale un 0 hasta el estado

q2 y también sale un 0 al estado q1, en ambos caminos llega al estado de aceptación q2 Teniendo en cuenta el siguiente autómata realizar los puntos siguientes:

Ejercicio 2: Realizar la conversión de AFD a AFND o de AFND a AFD según corresponda Conversión de AFN A AFD Paso 1:tabla de transición Estado q0 q1 q2 q3 q4 q5

a q1 q5 q2 -

b q5 q2,q3 q4 q1 q4,q5

Paso 2: Se evalúan desde q0 y se reevalúan los grupos de estados o estados que aparezcan Estado q0 q1 q5 q4,q5 q1,q4,q5

a q1 -

b q5 q4,q5 q1,q4,q5 q1,q4,q5

Paso 3: Graficar

Ejercicio 3: Realice la minimización paso a paso del autómata finito determinista

𝑀 = {𝑞0, 𝑞1, 𝑞2, 𝑞3}, {𝑎, 𝑏}, 𝛿, 𝑞0, {𝑞2, 𝑞3} 𝐾 = {𝑞0, 𝑞1, 𝑞2, 𝑞3} ∑ = {𝑎, 𝑏} 𝑆 = 𝑞0 𝐹 = 𝑞2, 𝑞3 Tabla de transiciones

>q0 q1 *q2 *q3

a q1 -

b q2 q3 q3

𝛿(𝑞0, 𝑎) = 𝑞1 𝛿(𝑞0, 𝑏) = 𝑞2 𝛿(𝑞2, 𝑏) = 𝑞3 𝛿(𝑞3, 𝑏) = 𝑞3 Por medio de la eliminación de conjuntos Estados aceptadores x = {q2, q3}

*q2 *q3

A -

b x x

A y -

B x -

Estados no aceptadores y = {q0, q1}

>q0 q1

Se identifica que existen estados equivalentes, con lo que se obtienen los siguientes conjuntos.

A = {*q2, *q3} B = {q0} C = {q1} Se vuelve a verificar los nuevos conjuntos para verificar nuevos estados equivalentes.

Estados aceptadores x = {A}

*A

A -

B x

A y -

B X -

Estados no aceptadores y = {B. C}

>B C

No se encuentran estados equivalentes, por lo cual ya no se puede minimizar Vamos a encontrar hacia donde apuntan según el lenguaje los nuevos estados.

*A >B C

a C -

B A A -

Cambiando los nombres de los estados y graficando el nuevo autómata

*q0 >q1 q2

a q2 -

b q0 q0 -

Dando como resultado

Ejercicio 4: Realizar el autómata a Pila de L = {(abb+ccn)*}

Procedimiento paso a paso del recorrido de la cadena “abbabbcc”

Transición ơ(q0, a, a)=(q1, a) -Paso 1: cuando el autómata se encuentra en el estado q0, lee el símbolo de entrada a y tiene el símbolo a en la cima de la pila.

Transición ơ(q1, b, b)=(q2, b) - Paso 2: El autómata pasará a algún estado q2, lee el símbolo b no desapila nada e inserta el símbolo b en la cima de la pila.

Transición ơ(q2, b, b)=(q3, b) - Paso 3: El autómata pasa al estado q3, lee el símbolo b no desapila nada e inserta el símbolo b en la cima de la pila.

Transición ơ(q3, a, ʎ)=(q0, ʎ) - Paso 4: El autómata pasa al estado q0, lee el símbolo a y desapila el símbolo b en la cima de la pila.

Transición ơ(q0, a, b)=(q1, a) - Paso 5: El autómata pasa al estado q1, lee el símbolo a no desapila nada e inserta el símbolo a en la cima de la pila.

Transición ơ(q1, b, b)=(q2, b) - Paso 6: El autómata pasa al estado q2, lee el símbolo b no desapila nada e inserta el símbolo b en la cima de la pila.

Transición ơ(q2, b, b)=(q3, b) - Paso 7: El autómata pasa al estado q3, lee el símbolo b no desapila nada e inserta el símbolo b en la cima de la pila.

Transición ơ(q3, c, c)=(q3, c) - Paso 8: El autómata sigue en el estado q3, lee el símbolo c no desapila nada e inserta el símbolo c en la cima de la pila.

Transición ơ(q3, c, c)=(q3, c) - Paso 9: El autómata sigue en el estado q3, lee el símbolo c no desapila nada e inserta el símbolo c en la cima de la pila. Finaliza la lectura de la cinta.

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 la menos cinco símbolos. d. Identifique en qué momento la máquina se detiene.

Caracterización de la máquina de Turing: Definición formal: M= (Σ, Q, Γ, s, b, f, δ) Σ: {0,1} Q: {q0, q1, q2, q3} Γ: {0, 1, b} s: {q0} b: {b} f: {q3} δ(q0, 0) = (1, R, q0) δ(q0, b) = (0, R, q0) δ(q0, 1) = (b, R, q1) δ(q1, b) = (1, R, q1) δ(q1, 0) = (0, R, q2) δ(q1, 1) = (0, L, q2) δ(q2, 0) = (0, R, q2) δ(q2, 1) = (1, L, q3)

Procedimiento de paso a paso del recorrido de una cadena: Cadena: 01000110 Cinta: Cabezal

0

1

0

0

0

1

1

Izquierda

0

Derecha

Iniciamos: q0

0

1

0

0

0

1

1

0

Paso 1. Estando en el estado q0, el cabezal señala el primer elemento que es un 0. δ(q0, 0) = (1, R, q0) Paso 2. El cabezal lo cambia por el término 1, se mueve a la derecha y mantiene el estado q0 q0

1

1

0

0

0

1

1

0

Paso 3. Estando en el estado q0, el cabezal señala el término 1. δ(q0, 1) = (b, R, q1)

Paso 4. El cabezal lo cambia por un espacio en blanco, se mueve a la derecha y cambia al estado q1

q1

1

0

0

0

1

1

0

Paso 5. Estando en el estado q1, el cabezal señala el término 0. δ(q1, 0) = (0, R, q2) Paso 6. El cabezal mantiene el 0, se mueve a la derecha y cambia al estado q2 q2

0

0

0

0

1

1

0

Paso 7. Estando en el estado q2, el cabezal señala el término 0. δ(q2, 0) = (0, R, q2) Paso 8. El cabezal mantiene el 0, se mueve a la derecha y permanece en el estado q2 q2

0

0

0

0

1

1

0

Paso 9. Estando en el estado q2, el cabezal señala el término 0. δ(q2, 0) = (0, R, q2) Paso 10. El cabezal mantiene el 0, se mueve a la derecha y permanece en el estado q2 q2

0

0

0

0

1

1

0

Paso 11. Estando en el estado q2, el cabezal señala el término 1. δ(q2, 1) = (1, L, q3) Paso 12. El cabezal mantiene el 1, se mueve a la izquierda y cambia al estado final q3

q3

0

1

0

0

0

1

1

0

La cadena pasa como válida.

b. Identifique una cadena que no sea válida y justifique el porqué. La cadena “011000” no es válida porque cundo la máquina llega al último carácter de esta, es decir un cero (0) se queda en el estado q2 y no puede avanzar al estado final, el cual requiere de un uno (1) para poder avanzar. c. Ejecute el RunTest a una cadena aceptada que tenga al menos cinco símbolos. Para el Run Test utilizaremos la cadena “01001” que al ser ejecutada en JFLAP queda la siguiente secuencia: Paso 1

Paso 2

Paso 3

Paso 4

Paso 5

Paso 6

d. Identifique en qué momento la máquina se detiene.

La máquina se detiene cuando recibe un uno (1) al final de la cadena, realiza un movimiento hacia la izquierda y llega al estado final.

Bibliografía Alfonseca C, E., Alfonseca M, M., Mariyón S, R. (2009). Teoría de autómatas y lenguajes formales. (pp. 19 - 65). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=10498 456&ppg=6 Bonilla, L. [Luis] (2018, mayo 23). Códigos Convolucionales Tellis y Viterbi. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=Oe9WEAOLeyc&t=1218s Bonilla, L. [Luis] (2018, mayo 23). Diagrama de árbol. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=HNS4IQw64Sk Bonilla, L. [Luis] (2018, mayo 23). Diagrama de estados. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=JTJkNco2tjQ&t=5s Bonilla, L. [Luis] (2018, mayo 23). Diagrama de trellis. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=21JKzST2ZJY Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. (pp. 11 - 80). Recuperado de http://bibliotecavirtual.unad.edu.co:2051/login.aspx?direct=true&db=nlebk&AN =318032&lang=es&site=edslive&ebv=EB&ppid=pp_Cover CK-12, (2012). Case History: How Math, Science, and Engineering Led to the First Pocket Radio. [OVI]. Recuperado de http://www.ck12.org/book/Engineering%3A-AnIntroduction-for-High-School/section/5.2/ González, A. [Ángela]. (2018, junio 1). Lenguajes Estructurados por Frases. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18316 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=10566 114&ppg=10 Rosenfeld, D. (2016). Computabilidad, Complejidad computacional y verificación de programas. (pp. 7 - 27). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=11201 616&ppg=12