Autómatas de Pila

Vista previa del material en texto

Tarea 3
Construcción de Autómatas de Pila
Estudiante
Código: 15518622
Helena Clara Isabel Alemán
Tutora 
Grupo 9
Universidad Abierta y a Distancia
UNAD
Octubre 2022
EJERCICIOS PARA DESARROLLAR 
A continuación, se definen los ejercicios a desarrollar: 
Ejercicios 1: Autómata de Pila 
Deben diligenciar la siguiente información:
	EJERCICIO A TRABAJAR
	
	Caracterización del autómata a pila
	Definición formal
Es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce
Séptupla del autómata
𝐴𝑃 = (𝑄, Σ, Γ, 𝛿, 𝑠, 𝑍0, 𝐹) 
𝑄: {𝑞0, 𝑞1} Conjunto finito de estados
Σ: {a, b} Alfabeto finito de entrada
Γ: {𝜆, 𝐴, 𝐵}: Alfabeto de Pila
𝛿: 𝑄 𝑥 Σ 𝖴 {ϵ} 𝑥 Γ → 2𝑄𝑥𝛤∗ Función de transición 𝛿 (𝑞, 𝑎, 𝑋) → (𝑝, 𝛾), {𝑝, 𝑞} ∈ 𝑄, 𝑎 ∈ Σ 𝖴 {𝜀}, 𝑋 ∈ Γ y Υ ∈ Γ {ϵ }, reemplaza a X.
𝑠 ∶ 𝑞0 Símbolo inicial del autómata
𝐹 ⊆ 𝑄: 𝑞1 Conjunto de estados finales
Transiciones
b, λ, b
a, λ, a
λ, λ, λ
a, a, λ
b, b, λ	
Equivalencia entre AP por vaciado de pila y AP por estado final
Un 𝐴𝑃 = (𝑄, Σ, Γ, 𝛿, 𝑠, 𝑍0, 𝐹) puede reconocer palabras del alfabeto de entrada de dos formas distintas:
Por estado final:
𝐿𝐹(𝐴𝑃) = {𝑥 | (𝑞0, 𝑥, 𝑍0) ├ ∗ (𝑝, λ, X), (p ∈ F, X ∈ Γ∗}
Por vaciado de pila:
𝐿𝑣(𝐴𝑃) = {𝑥 | (𝑞0, 𝑥, 𝑍0) ├ ∗ (p, λ, λ), con p ∈ Q}
𝐿𝐹(𝐴𝑃) 𝑦 𝐿𝑉(𝐴𝑃) representan a los lenguajes reconocidos por el autómata 𝐴𝑃 por estado final y por vaciado de pila respectivamente.
Cuando la aceptación se realiza por vaciado de pila, el conjunto de estados finales 𝐹 es irrelevante.
Equivalencias de 𝐴𝑃
Dos autómatas a pila (por vaciado de pila o por estado final), 𝐴𝑃1 y 𝐴𝑃2, son equivalentes, si aceptan el mismo leguaje, es decir, si 𝐿(𝐴𝑃1) = 𝐿(𝐴𝑃2)
	Procedimiento de paso a paso del recorrido de una cadena
	Gráficamente en un autómata de pila existe una cinta de entrada ésta permite ingresar caracteres de diversos tipos, un mecanismo de control que se sitúa en el primer estado y una cadena memoria de la Pila. La cadena escogida para este ejercicio es: aabab.
Inicialmente tenemos lo siguiente:
Se observa que la lectura de la cinta inicia en 𝑍0 la cual es la posición inicial de la pila como se puede ver en la memoria de la pila y en la posición 𝑞0 cómo se puede evidenciar en el mecanismo de control.
Con la tabla inicial comenzamos a analizar tenemos que:
Se observa que la lectura de la cinta se encuentra en (a) por lo tanto se inicia en base a la primera función de transición 𝛿 (𝑞0, a, λ) = {(𝑞0, a)} donde se encuentra en la posición 𝑞0, no existe 𝑍 por lo tanto se dirige hacia 𝑞0 y apila una a.
La lectura de la cinta se mueve al siguiente carácter de la cadena la cual sigue en (a) y permanece en la posición 𝑞0 por lo tanto se sigue utilizando la primera función de transición 𝛿 (𝑞0, a, λ) = {(𝑞0, a)} donde se encuentra en la posición 𝑞0; no obstante, no existe 𝑍, por lo tanto, se dirige hacia 𝑞0 y apila nuevamente una a.
La lectura de la cinta se mueve al siguiente carácter de la cadena la cual sigue en (b) y permanece en la posición 𝑞0 por lo tanto se sigue utilizando la primera función de transición 𝛿 (𝑞0, b, λ) = {(𝑞0, b)} donde se encuentra en la posición 𝑞0; se dirige hacia 𝑞0 y apila una b.
La lectura de la cinta se mueve al siguiente carácter de la cadena la cual sigue en (a) y permanece en la posición 𝑞0 por lo tanto se sigue utilizando la primera función de transición 𝛿 (𝑞0, a, λ) = {(𝑞0, a)} donde se encuentra en la posición 𝑞0; no obstante, no existe 𝑍, por lo tanto, se dirige hacia 𝑞0 y apila nuevamente una a.
La lectura de la cinta se mueve al siguiente carácter de la cadena la cual sigue en (b) y permanece en la posición 𝑞0 por lo tanto se sigue utilizando la primera función de transición 𝛿 (𝑞0, b, λ) = {(𝑞0, b)} donde se encuentra en la posición 𝑞0; apila una b.
A terminar pasa a la posición 𝑞1
Verificando en jflap:
	Practicar y verificar lo aprendido
	
	
Cadenas aceptadas y rechazadas
	Lenguaje regular
	
Ejercicio 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 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. 
Gramática del autómata.
Se define la gramática como:
 Alfabeto (son terminales – no se pueden derivar)
· Se valida que genera “a” a ó “b” genera a 
· Luego se valida que nada genera “a” a 
Bibliografía
Amarillo, A. M. (16 de mayo de 2017). Minimizacion de automata,Youtube. Youtube: https://youtu.be/eOynYG8Ibk0
Amarillo, A. M. (9 de mayo de 2020). Autómatas de pila,YouTube. YouTube: https://youtu.be/o9eUECLgQno
Carrasco, R. C. (2010). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. http://bibliotecavirtual.unad.edu.co: http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?docID=10566114&ppg=10
Contreras, L. C. (6 de octubre de 2020). Autómatas de Pila (Clase completa),YouTube. YouTube: https://youtu.be/lwoHC2Qyi20