Fase_5 AUTOMATAS

Vista previa del material en texto

(
AUTOMATAS Y LENGUAJES FORMALES
)Tarea 5. Consolidación del aprendizaje PRESENTADO POR:
JAVIER MAURICIO BEDOYA CC: 1,088,014,692
GRUPO: 301405_90
PRESENTADO AL TUTOR: EDGAR ANTONIO CORTES
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD ESCUELA DE CIENCIAS BÁSICAS, INGENIERÍAS Y TECNOLOGÍAS
Diciembre de 2020
 (
EJERCICIOS A
 
DESARROLLAR
)A partir del siguiente ejercicio desarrollar los ejercicios propuestos:
Ejercicio 1: Realizar la conversión de AFD a AFND o de AFND a AFD según corresponda:
· Caracterización del autómata original.
	M
	({q0,q1,q2,q3,q4,q5},{a, b, λ}, δ, q0,
{q4,q5}
	K
	{q0, q1, q2, q3, q4, q5}
	Σ
	{a, b, λ}
	s
	q0
	F
	q4,q5
	Relación de transicione s δ
	{q0, q1, q2, q3, q4, q5}x{a, b, λ}
{q0, q1, q2, q3, q4, q5} Viene dada por:
δ (q0, a) = q1 δ (q0, b) = q2 δ (q1, a) = q2 δ (q1, b) = q4 δ (q2, a) = q2 δ (q2, b) = q3 δ (q3, a) = q5 δ (q3, λ) = q4 δ (q4, a) = q1 δ (q4, b) = q3 δ (q5, b) = q4 δ (q5, λ) = q3
Tabla de transiciones
	
	a
	b
	λ
	q0
	q1
	q2
	--
	q1
	q2
	q4
	--
	q2
	q2
	q3
	--
	q3
	q5
	--
	q4
	#q4
	q1
	q3
	--
	#q5
	--
	q4
	q3
· Procedimiento de conversión de Autómata de AFD a AFND o de AFND a AFD según corresponda con procedimiento paso a paso.
Creamos los conjuntos e identificamos los elementos del alfabeto que maneja el autómata.
Identificamos el estado inicial y validamos las transiciones vacías que lo afectan:
	
	a
	b
	A = {0}U{3,4}
	B = {1,2,5}U{3,4}
	C = {1,2,3}U{3,4}
Validamos las transiciones del conjunto B resultante
	
	a
	b
	B = {1,2,5}U{3,4}
	B = {1,2,5}U{3,4}
	D = {1,3,4}U{3,4}
Validamos las transiciones del conjunto C resultante
	
	a
	b
	C = {1,2,3}U{3,4}
	B = {1,2,5}U{3,4}
	D = {1,3,4}U{3,4}
Validamos las transiciones el conjunto D resultante
	
	a
	b
	D = {1,3,4}U{3,4}
	B = {1,2,5}U{3,4}
	D = {1,3,4}U{3,4}
Creamos la tabla del autómata convertido:
	
	a
	b
	A
	B
	C
	B
	B
	D
	C
	B
	D
	D
	B
	D
· Gráfica del Autómata final convertido.
Validación de cadenas en cada uno de los autómatas: Autómata inicial
Autómata convertido:
 (
Ejercicio 2
: Realice la minimización paso a paso del autómata finito determinista
)Autómata inicial
· Con el resultado del autómata del ejercicio 1, realice el proceso paso a paso de la minimización del autómata.
Definimos la quíntupla del autómata:
	M
	({A,B,C,D},{a, b}, δ, A,{B,D}
	K
	{ A,B,C,D }
	Σ
	{a, b}
	s
	{A}
	F
	{B,D}
	Relación de transicione s δ
	{A,B,C,D}x{a, b}	{A,B,C,D}
Viene dada por:
δ (A, a) = B
δ (A, b) = C
δ (B, a) = B
δ (B, b) = D
δ (C, a) = B
δ (C, b) = D
δ (D, a) = B
δ (D, b) = D
 (
Realizamos la minimización por medio de la eliminación de conjuntos, asignando cada
)uno de los estados a un conjunto aceptador o a un conjunto no aceptador: x = {B, D} Aceptadores
y = (A, C} No Aceptadores
Creamos una tabla para representar las transiciones de los estados aceptadores:
	
	a
	b
	B
	x
	x
	D
	x
	x
Creamos una tabla para representar las transiciones de los estados no aceptadores:
	
	a
	b
	A
	x
	y
	C
	x
	x
Creamos los nuevos conjuntos para agrupar los estados equivalentes: x = {B, D}
y = {A}
z = {C}
Realizamos nuevamente las tablas para representar las transiciones para el conjunto x{}:
	
	a
	b
	B
	x
	x
	D
	x
	x
Para el conjunto y{}:
	
	a
	b
	A
	x
	z
Para el conjunto z{}:
	
	a
	b
	C
	x
	x
· (
Gráfica del autómata final
 
minimizado.
)Realice la caracterización de ese autómata
	M
	({q0, q1, q2},{a, b}, δ, q0,{q2}
	K
	{q0, q1, q2}
	Σ
	{a, b}
	s
	{q0}
	F
	{q2}
	Relación de transicione s δ
	{q0, q1, q2}x{a, b}	{q0, q1, q2}
Viene dada por:
	
	δ (q0, a) = q2 δ (q0, b) = q1 δ (q1, a) = q2 δ (q1, b) = q2 δ (q2, a) = q2 δ (q2, b) = q2
Las mismas entradas del autómata inicial, son aceptadas por el autómata minimizado:
 (
Ejercicio 3
: Realizar el autómata a Pila que lea la expresión regular del autómata
)minimizado.
· Teniendo en cuenta la expresión regular del resultado del autómata minimizado del ejercicio 2, realice el autómata de pila que lea las mismas cadenas.
· Caracterización del autómata de pila
· Ejecute el Run Test a una cadena aceptada que tenga al menos cinco símbolos.
· Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la cinta como en la secuencia de entrada.
Ejercicio 4: Realizar una máquina de Turing que lea la expresión regular del autómata minimizado.
· Teniendo en cuenta la expresión regular del resultado del autómata minimizado del
ejercicio 2, realice la máquina de Turing que lea las mismas cadenas
· Caracterización de la máquina de Turing
· Ejecute el Run Test a una cadena aceptada que tenga al menos cinco símbolos.
· Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la cinta como en la secuencia de entrada.
 (
Recuerde utilizar los simuladores de JFlap (Anexo 1) o VAS (Anexo 2), para el desarrollo
)de la actividad.
 (
Bibliografía
)Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales. Universidad de Extremadura. Servicio de Publicaciones. (pp. 39 - 70). Recuperado de https://bibliotecavirtual.unad.edu.co/login?url=http://search.ebscohost.com/login.aspx?
direct=true&db=edsbas&AN=edsbas.62161440&lang=es&site=eds-live&scope=site
González, A. [Ángela]. (2017, noviembre 5). Autómatas Finitos. [Archivo de video]. Recuperado de http://hdl.handle.net/10596/10470
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