• Author / Uploaded
• eduar vela

Citation preview

AUTOMATAS Y LENGUAJES FORMALES - (301405A_764) Tarea 3 Construcción De Autómatas De Pila

GRUPO 74

Luis Eduardo Obando Bonilla Código: 1.105.614.452 Alejandra Morales Ropero Código: 1.110.535.917 Lucas Hernando Bonilla Conde Código: Eduar Ricardo Vela Pinilla Código:1110586450

Presentado a: Tutor Edgar Antonio Cortes

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela De Ciencias Básicas, Tecnología E Ingeniería Programa Ingeniería De Sistemas Ibagué 2020

TABLA DE ELECCIÓN DE EJERCICIOS:

Nombre del estudiante

Rol a desarrollar

Eduar Ricardo Vela Pinilla

Revisor

Lucas Hernando Bonilla Conde

Evaluador

Luis Eduardo Obando Bonilla

Entregas

Alejandra Morales

Alertas

Grupo de ejercicios a desarrollar paso1. El estudiante desarrolla los ejercicios D en todos los tres tipos propuestos. El estudiante desarrolla los ejercicios C en todos los tres tipos propuestos. El estudiante desarrolla los ejercicios A en todos los tres tipos propuestos. El estudiante desarrolla los ejercicios X en todos los tres tipos propuestos. El estudiante desarrolla los ejercicios B en todos los tres tipos propuestos.

Ejercicios 1: Autómata de Pila: Ejercicio A Desarrollado por: Luis Eduardo Obando Bonilla EJERCICIO A TRABAJAR

Ejercicio A

Caracterización del autómata a pila

En este espacio se realiza: - Mediante la definición formal explicar las características del autómata, identificación de la séptupla. Σ = {a,b} r = {a, λ} Q = {q0, q1} AO: ɛr = λ qoɛQ = {q0} FCQ = {q1} F = σ = (q0, a, λ), (q0,a) σ = (q0, b, a), (q1, λ) σ = (q1, b, a), (q1, λ) - Realizar la tabla de transición Q0 #Q1

a Q0 -

b Q1 Q1

- Realizar un cuadro comparativo de la Equivalencia entre AP por vaciado de pila y AP por estado final: Los autómatas de pila tienen dos tipos de aceptación: - Por estado Final - Por Vaciado de Pila Ambos equivalentes:

Procedimiento de paso a paso del recorrido de una cadena

Por Estado Final

Por Vaciado de Pila

– sea P = (Q, Σ, Γ, δ, q0, Z0, F) un AP – L(P), el lenguaje aceptado por P por estado final es – {w | (q0, w, Z0) ├* (q, ε, α)} – para algún estado q de F y cualquier cadena de pila α

Para todo AP P = (Q, Σ, Γ, δ, q0, Z0) se define el lenguaje que acepta como: – N(P) = {w | (q0, w, Z0) ├* (q, ε, ε)} para cualquier estado q

Cinta de entrada: a

a

a

b

b

Paso 1: Recorreremos la cadena: (q0,a, λ), (q0,a) de la siguiente manera: a

a

a

b

b

a Zo

Como vemos la primer transición apila (a) dejando nuestro mecanismo de control en q0. Paso 2: Recorremos de nuevo: (q0,a, λ), (q0,a) de la siguiente manera: a

a

a a Zo

a

b

b

Apilando una segunda (a) y dejando de nuevo nuestro mecanismo de control en q0.

Paso 3: Una vez más recorremos: (q0, a, λ), (q0, a) a

a

a

b

b

a a a Zo

Apilando una tercera (a) y continuando el mecanismo de control en q0. Paso 4: Ahora recorreremos (q0, b, a), (q1, λ): a

a

a

b

b

a a Zo

Desapilamos según la transición una de nuestras (a) y nuestro mecanismo de control justo entre q0 y q1.

Paso 4 Por último, recorremos (q0, b, a), (q1, λ):

a

a

a

b

b

a Zo Por último, desapilamos una (a) más según nuestra última transición, y ubicando nuestro mecanismo de control en el estado de aceptación en q1. Practicar y verificar lo aprendido

Ejecutar y validar por lo menos cinco cadenas válidas y 5 cadenas rechazadas por el autómata. En este espacio adjunta la imagen.

Vemos que la primera cadena allí es la explicada en el paso a paso, la cual comprobaremos a continuación:

Ejercicio a Trabajar

Caracterización del autómata pila

Lenguaje regular

1-identificación de la séptupla.

∑ ¿{a , b }

r ={a , λ } Q={q 0 , q 1 } A 0 ε r =A 0=λq 0 ε r={ q 0 } F C Q ={q 1}

a ¿ bb¿

σ =( q 0 , a , λ ) , ( q 0 , a ) σ =( q 0 , b , λ ) ,(q 0 , b) σ =( q 1 , a , a ) , ( q 1, λ ) σ =( q 1 , b , b ) , ( q 1, λ ) 2-Realizar la tabla de transición A  Q0 #Q1

Ejercicio B

Q0 Q1

B Q0 Q1

Desarrollado por: Alejandra Morales Ropero

Procedimiento de paso a paso del recorrido de una cadena

A continuación, muestra la cinta de entrada

aaabb σ =( q 0 , a , λ ) , ( q 0 , a ) σ =( q 0 , b , λ ) ,(q 0 , b) σ =( q 1 , a , a ) , ( q 1, λ ) σ =( q 1 , b , b ) , ( q 1, λ )

PASO NUMERO UNO El mecanismo de control esta posicionado en q0, donde σ =( q 0 , a , λ ) , ( q 0 , a ) se apilara una “a”

PASO NUMERO DOS

El mecanismo de control esta posicionado en q0, donde σ =( q 0 , a , λ ) , ( q 0 , a ) se apilara segunda “a”

PASO NUMERO TRES El mecanismo de control esta posicionado en q0, donde

σ =( q 0 , a , λ ) , ( q 0 , a ) se apilara tercera “a”

PASO NUMERO CUATRO El mecanismo de control esta posicionado en q0, donde σ =( q 0 , b , λ ) ,( q 0 , b) apilamos una b

PASO NUMERO CINCO El mecanismo de control se sitúa en q1 donde σ =( q 1 , a , a ) , ( q 1, λ ) donde desapilamos “b”

PASO NUMERO SEIS El mecanismo de control se sitúa en q1 donde σ =( q 1 , b , b ) , ( q 1, λ ) desapilamos una “a”, quedando como referencia final en el estado de aceptación q1

Practicar y verificar lo aprendido

NOTA: se trabaja solamente por estado final ya que se presenta error see ejecuta por vaciado de pila y no es equivalente, reportado el día 29/10/2020 en sesión de las 5:00pm. Evidenciando que landa divide los autómatas q0 y q1,

Lenguaje regular

aa ¿ b¿

Ejercicio C Desarrollado por: Lucas Fernando EJERCICIO A TRABAJAR

Caracterizaci ón del autómata a pila

AP={Σ,R,Q,A0,q0,f,F)donde: Σ: es el alfabeto de entrada: Σ={0,1,λ) R: es el alfabeto de la pila: r={a, λ ,X} Q:es un conjunto finito de estados: Q={q0,q1,q2} A0 ∈ r: Es un símbolo especial de pila A0= λ A0 ∈ Q = q0: el estado inicial del autómata: A0 ∈ Q = q0 F⊆Q : es el conjunto de estados finales: F⊆Q = {q2} F: es una aplicación denominada función de transición de ternas. F: σ={q0,a,λ),(q0,a) TABLA DE TRANSICIONES TRANSICIONES

FUNCIONES

DE

TRANSICIONES

L=Símbolo de cadena de entrada

la

qi,L,D),(estado

F: σ =( q 0,0 , λ ) ,(q 0 , a) σ =( q 0,1 , a ) ,(q 1 , λ) σ =( q 1,1 , a ) ,(q 1 , λ) σ =( q 1 , λ , Z ) ,(q 2 , X )

L=0 L=1 L=λ D= Símbolo desapila

(estado qll,A)

que

D= λ D=a D=z A=Símbolo que apila A=a A= λ A=x -

Realizar un cuadro comparativo de la Equivalencia entre AP por vaciado de pila y AP por estado final por pila vacía

autómata con pila 

Siendo  : se puede llegar a través de P con 0 o más pasos. el lenguaje aceptado por P por pila vacía es

el lenguaje aceptado por P por estado final es

Procedimient o de paso a paso del recorrido de una cadena

PASO 1 Comenzamos el recorrido de nuestra cadena con 0 como cadena valida correspondiente a una cadena valida, haciendo push en la pila ya con un valor valido para ser almacenado en la pila, este ciclo lo repite dos veces mas según la cadena propuestas. TRANSICION F¿ ( q 0,0 , λ ) ,( q 0 , a)

Se almacena la cadena de valor de a por segunda vez teniendo en cuenta que la cadena propuesta lee de nuevo 0 como alfabeto de entrada.

Se almacena la cadena de valor de a por tercera vez teniendo en cuenta que la cadena propuesta lee de nuevo 0 como alfabeto de entrada.

PASO 2 Ahora en el recorrido de nuestro automata lee como alfabeto de entrada el numero 1 teniendo en cuenta que este tiene un alfabeto de pila λ, esto nos indica

que debemos hacer desapilar el valor de la cabeza de pila en este caso a. TRANSICION (q0,1,a),(q1,λ)

PASO 3 Como el caso anterior el recorrido lee como alfabeto de entrada el numero 1 teniendo en cuenta que este tiene un alfabeto de pila λ, esto nos indica que

debemos hacer desapilar el valor de la cabeza de pila en este caso a. TRANSICION (q0,1,a),(q1,λ)

PASO 4 Ya nuestra cadena esta leyendo por tercera vez una el numero 1 como alfabeto de entrada y al a ver una alfabeto de pila en valor λ, hay nuevamente que desempilar, pero como indicar la norma si una pila esta vacia y el valor de entrada es λ se ingresa su valor de pila la cadena es aceptada.

Practicar y verificar lo aprendid o

CADENAS ACEPTADAS 0011

01

000111

00001111

CADENAS RECHAZADAS 00011

0000111

0000001111

00100111

000000011111

Lengua je regular

R={0*11*}

Ejercicio D Desarrollado por: Eduar Ricardo Vela Pinilla EJERCICI

Ejercicio A

OA TRABAJA R

Caracteriza ción del autómata a pila

En este espacio se realiza: - Mediante la definición formal explicar las características del autómata, identificación de la séptupla. AP={Σ , R,Q,A0,q0,f,F)donde: Σ: es el alfabeto de entrada: Σ={b , c ¿ R: es el alfabeto de la pila: r={ λ , a } Q :es un conjunto finito de estados :Q= {q 0 , q 1 } A0 ∈ Q = q0: el estado inicial del autómata: A0 ∈ Q = q0 F⊆ Q: es el conjunto de estados finales: F⊆ Q = {q1} F: es una aplicación denominada función de transición de ternas. F: σ ={ q 0 , a , λ ) ,( q 0 , a) - Realizar la tabla de transición Transiciones y Funciones de transición (0,Z , B¿ Función de Transición σ =( estado qi ,l , D ) , ( estado qll , A ) (L,D,A) L=B= Símbolo de la cadena de F: σ =( q 0,0 , Z ) ,( q 0 , B) σ =( q 0,0 , C ) ,(q 0 , BC ) entrada σ =( q 0,0 , B ) ,(q 0 , C) D= λ=Simbolo que desapila σ =( q 0,1 , C ) ,(q 1, λ) A1= Símbolo que apila σ =( q 1,1 , C ) ,(q 1 , λ) -

Realizar un cuadro comparativo de la Equivalencia entre AP por vaciado de pila y AP por estado final por pila vacía autómata con pila Siendo   : se puede llegar a través de P con 0 o más pasos.

el lenguaje aceptado por P por pila vacía el lenguaje aceptado por P por estado final es

Procedimie

Expresión gramatical

nto de paso a paso del recorrido de una cadena

q0->0q0|1q1 q1->1q1|λ Realice de manera detallada y grafica el procedimiento paso a paso del recorrido de una cadena (La cadena la selecciona el estudiante, debe contener como mínimo 5 caracteres) en el autómata a pila. Describir cómo funciona el almacenamiento en la pila, como funciona LIFO, etc. - Paso 1… Tomamos como ejemplo para validar el recorrido de cada cadena, las siguientes cadenas. 0 0 1 1 Tomamos los valores iniciales, el estado q0, y la raíz, así se inicia el autómata. Cuando ejecutamos la primera transición me dice que se lee el punto 0 que no extraiga ninguna operación para la pila, en este caso insertaríamos una 0 en la pila Estado Por leer Pila Q0 0011 Z0

0 Z0 - Paso 2… Seguimos con la transición en este caso nos tocaría evaluar las faltantes que serían 011, se nos agrega otra 0, ya que se vuelve y se lee en la transacción Estado Por leer Pila Q0 0011 Z0 Q0 011 0 0 0 Z0 - Paso 3… Seguimos con la lectura de la cadena en 1. tan pronto lleguemos la lectura 1, pasamos al estado q1. En este caso nos quitaría una a de la pila

Estado Q0 Q0

Por leer 0011 011

Pila Z0 0

Q1

11

00

0 Z0 -Paso 4 - Como último paso terminamos con la lectura de la última 1. de la cadena. Vuelve a quedar en el fondo o vacía la pila, entonces la cadena es reconocida. En este caso llega otra vez hasta z0 el valor inicial Estado Por leer Pila Q0 0011 Z0 Q0 011 0 Q1 11 00 Q1 1 0 λ Q1 Z0

Practicar y verificar lo aprendido

Lenguaje regular

Z0 Ejecutar y validar por lo menos cinco cadenas válidas y 5 cadenas rechazadas por el autómata. En este espacio adjunta la imagen.

0*11*

Ejercicio E Desarrollado por:

Ejercicios 2: Gramática del autómata El estudiante realiza paso a paso la gramática del autómata que seleccionó. Identifique su gramática (de forma manual) por la derecha o izquierda y la caracteriza. Debe incluir el diagrama de estados con los componentes de la gramática asociados a las variables y a las constantes. Ejercicio A

Desarrollado por: Luis Eduardo Obando Bonilla

qo ⮕ aq0 | bq1 q1 ⮕ bq1| λ

Ejercicio B Desarrollado por:

Ejercicio C Desarrollado por:

Ejercicio D Desarrollado por:

Ejercicio E Desarrollado por:

Ejercicio Grupal: Minimización de autómatas

EJERCICIO A TRABAJAR

Ejercicio A

Procedimiento de minimización

Realice de manera detallada el procedimiento paso a paso de la minimización del autómata. - Paso 1: Identificamos la quíntupla. M = ({q0, q1, q2, q3, q4, q5, q6, q7, q8, q9}, {1, 2}, δ, q0, {q3, q5, q7}) K = {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9} Σ = {1, 2} s = q0 F = q3, q5, q7 Donde la función δ: { q0, q1, q2, q3, q4, q5, q6, q7, q8, q79} x {1, 2} → { q0, q1, q2, q3, q4, q5, q6, q7, q8, q9} viene dada por: δ (q0, 1) = q2 δ (q0, 2) = q1

δ (q1, 1) = q0 δ (q1, 2) = q2 δ (q2, 1) = q3 δ (q2, 2) = q5 δ (q3, 1) = q1 δ (q3, 2) = q4 δ (q4, 1) = q6 δ (q4, 2) = q2 δ (q5, 1) = q7 δ (q5, 2) = q6 δ (q6, 1) = q9 δ (q6, 2) = q4 δ (q7, 1) = q8 δ (q7, 2) = q8 δ (q8, 1) = q6 δ (q8, 2) = q9 δ (q9, 1) = q7 δ (q9, 2) = q5 -

Paso 2: Identificación del tipo de autómata:

Autómata finito Determinista, pues no conduce desde un estado en particular con un mismo número en este caso 1 o 2 hacia otro estado adicional. -

Paso 3: Transición de estados δ (q0, 1) = q2 δ (q0, 2) = q1

δ (q5, 1) = q7 δ (q5, 2) = q6

δ (q1, 1) = q0 δ (q1, 2) = q2

δ (q6, 1) = q9 δ (q6, 2) = q4

δ (q2, 1) = q3 δ (q2, 2) = q5

δ (q7, 1) = q8 δ (q7, 2) = q8

δ (q3, 1) = q1 δ (q3, 2) = q4

δ (q8, 1) = q6 δ (q8, 2) = q9

δ (q9, 1) = q7 δ (q4, 1) = q6 δ (q9, 2) = q5 δ (q4, 2) = q2 1 2 q0 Y Y Identificamos los grupos equivalentes: q1 X =Y{q3, q5, Y q7} Aceptador q2 X X q4 Y =Y Y q2, q4, q6, q8, q9} No Aceptador {q0, q1, q6 Y Y q8 Y Y q9 X X

q3 q5 q7

1 Y X Y

2 Y Y Y

Identificamos los conjuntos aceptadores y no aceptadores: X = {q3, q7} Aceptador V = {q5} Aceptador 2

L {q0, q1, q4, q6, q8} E {q2, q9} L q0 q1 q4 q6 q8

1 E L L E L

2 L E E L E

E q2 q9

1 X X

2 V V

X q3 q7

1 L L

2 L L

V q5

1 X

2 L

Separamos los nuevos conjuntos: X = {q3, q7} Aceptador V = {q5}

M {q0, q6} N {q1, q4, q8} E {q2, q9}

Grupo Aceptador

Segundo Grupo Aceptador

Desaparecemos el Grupo L y traemos los nuevos grupos: X = {q3, q7} Aceptador V = {q5}

M {q0, q6} N {q1, q4, q8} E {q2, q9} Identificamos los nuevos grupos y hallamos la tabla de transiciones: X q3 q7

1 N N

2 N N

E q2 q9

1 X X

2 V V

M q0 q6

1 E E

2 N N

N q1 q4 q8

1 M M M

2 E E E

V q5

1 X

2 M

X E M N V

1 N X E M X

2 N V N E M

Generamos el nuevo autómata dejando dos estados aceptadores (los que incluían q3, q7 y q5 y un estado inicial que contenía q0.

Resultado del Autómata minimizado

Notación formal del autómata minimizado

-

En este espacio agrega la notación formal del autómata. Identifique la quíntupla del autómata minimizado.

M = ({M, N, E, V, X}, {1, 2}, δ, M, {V, X}) K = {∑M, N, E, V, X} Σ = {1,2} s=M F = V, X Donde la función δ: {M, N, E, V, X } x {1,2} → { M, N, E, V, X } viene dada por: δ (X, 1) = N δ (X, 2) = N δ (E, 1) = X δ (E, 2) = V δ (M, 1) = E δ (M, 2) = N δ (N, 1) = M δ (N, 2) = E δ V, 1) = X

δ V, 2) = M -

Realice la tabla de transición X E M N V

Caracterización del autómata parte teórica

1 N X E M X

2 N V N E M

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. A continuación, se describen cada uno de los elementos y su definición. Tupla: Secuencia o lista de “N” objetos. DETERMINISTA: hace referencia a que cada estado en que se encuentre el autómata, y con cualquier símbolo alfanumérico incluido en este, existe siempre no más de una transición posible desde ese estado y con ese símbolo. M= demuestra cuales son los estados que componen el autómata, el alfabeto, estados iniciales y estados finales M = ({M, N, E, V, X} {1, 2}, δ, M, {V, X}) K= hace referencia a cada uno de los estados que componen el autómata. K = {M, N, E, V, X} Σ= Sigma, hace referencia al alfabeto empleado o entrada en el autómata, como se indicó en el concepto general puede tener cualquier símbolo alfanumérico. Σ = {1,2} S= Hace referencia al estado inicial en el automata. s=M

F= Hace referencia al estado o estados finales que puede tener el automata. F = V, X Lenguaje Regular Gramática del autómata

Validación de cadenas

Practicar y verificar lo aprendido

En este espacio agrega el lenguaje regular del autómata. M ⮕ 1E | 2N N ⮕ 1M| 2E E ⮕ 1X | 2V X ⮕ 1N | 2N | λ V ⮕ 1X | 2M | λ - Identifique 5 cadenas aceptadas y cinco cadenas rechazadas

Muestre en el simulador JFLAP (Anexo 1 - JFLAP) o VAS (Anexo 2- VAS) (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 pie de página o de lo contrario no tienen validez) -

Primero ingresamos el recorrido aceptado que esperamos

realizar:

-

Iniciamos con el recorrido del primer 1 llevándonos al estado E

-

De E con el 2 pasamos a V:

-

Con 1 ahora pasamos al estado X:

-

Ahora con 2 vamos hacia el estado N:

-

Con otro 2 vamos ahora hacia E:

-

Finalmente vamos con 1 hacia el estado aceptador X y como pudimos ver hicimos recorrido por todos los estados de nuestro autómata hasta llegar a uno de los dos estados aceptadores que tenemos:

REFERENCIAS BIBLIOGRÁFICAS González, A. [Ángela]. (2018, junio 1). Lenguajes Regulares. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18315 González, A. [Ángela]. (2020, julio 14). Lenguajes Regulares. [Archivo web]. Recuperado de https://campus113.unad.edu.co/ecbti73/mod/hvp/view.php?id=1672 González, A. [Ángela]. (2017, noviembre 5). Autómatas Finitos. [Archivo de video]. Recuperado de http://hdl.handle.net/10596/10470 ¿Que son las Tuplas, para qué sirven? - Juan Morillo. (s. f.). Medium. https://medium.com/@JuanMorillios/que-son-las-tuplas-para-qu%C3%A9-sirven-ac0d9abddafb