Tarea 2 - Diseño de Autómatas
Nasly Emilce Diaz
Omar Ivan Babativa Bonilla
Liby Tatiana Mosquera
Diego Alexander Villalba
Oscar Javier Ortegon
Tutor:
Vermen Rainer Ayala
Grupo:
301405_26
Universidad Nacional Abierta y a Distancia (UNAD)
AUTOMATAS Y LENGUAJES FORMALES - (301405A_764)
Octubre 2020
Ejercicio Grupal: Construir un autómata que realice lo siguiente:
ER = {(a)*+cd(ab)*b}
Deben diligenciar la siguiente información:
EJERCICIO A TRABAJAR
Notación formal del
autómata minimizado Identificación de la quíntupla del autómata:
A = (Q, Σ, δ, q0, F),
Q= {q0, q1, q2, q3, q4, q5} Estados
Σ = {𝑎, 𝑏, 𝑐, 𝑑} Alfabeto
δ(q0,d) = q2
δ(q1,b) = q2
δ(q2,a) = q1
δ(q2,b) = q3
δ(q4,a) = q4
δ(q5,a) = q4
δ(q5,c) = q0
s = q5
F = q3, q4, q5
Tabla de transición
a b c d
q0 --- --- --- q2
q1 --- q2 --- ---
q2 q1 q3 --- ---
#q3 --- --- --- ---
#q4 q4 --- --- ---
#q5 q4 ---- q0 ---
Caracterización del Los autómatas finitos deterministas quedarán formalmente
autómata parte teórica definidos mediante una quíntupla:
AFD=(Σ,Q,q0,F,f)
Donde:
Σ Alfabeto de símbolos de entrada
Q Conjunto finito de estados, también llamado
conjunto de estados.
q0 q0 Q – estado inicial previsto
F F Q - es el conjunto de estado finales de
aceptación.
f Función de transición de estados definida como
f: Q x ∑ Q
de modo que dado un estado y un símbolo del
alfabeto se produce otro estado. A esta función se
le llama función de transición
El autómata es un mecanismo con 2 partes:
• Una caja negra de control que va evolucionando por
los estados del conjunto Q en función del símbolo
leído de la cinta.
• Una cinta, ilimitada por la derecha, con una cabeza
de lectura que inicialmente se sitúa en la casilla más
a la izquierda.
En la cinta se escribe la cadena de caracteres de la que
queremos determinar si pertenece al lenguaje regular que
poseemos. En cada paso el autómata lee un símbolo y
según el estado en el que se encuentre, cambia de estado
y pasa a leer el siguiente símbolo. Así hasta acabar de leer
todos los símbolos de la cadena, en ese momento si el
estado en que está la flecha o cabeza de lectura es un
estado final entonces ACEPTA LA CADENA. Si no es un
estado final entonces RECHAZA LA CADENA, es decir, la
cadena no pertenece a ese lenguaje regular.
Lenguaje Regular Desde la expresión regular planteada para el ejercicio se
realizó el planteamiento del lenguaje regular:
LR: {a*, {cd}.{ab}*.{b}}
Validación de cadenas
Aceptadas Rechazadas
cdababb aaacdabababb
aaaaa caadababb
cdabb cdababbaaa
cdb aaaaacdabababb
cdabababababb cdaaaababb
Prueba con el simulador JFLAP
Practicar y verificar lo - Muestre en el simulador JFLAP (Anexo 1 - JFLAP) o VAS
aprendido (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)
Recorrido de una cadena valida
Lo primero que hace es ubicarse en el estado inicial el cual
es q5, desde allí empezare a realizar el recorrido con cada
uno de los símbolos ingresados en la cadena.
El primer símbolo de la cadena es “c” al leer este símbolo
pasa del estado inicial a el estado q0, allí espera el siguiente
símbolo.
El siguiente símbolo es “d” al leer este símbolo el autómata
pasa del estado q0 donde se encuentra al q2, en caso de que
recibiera cualquier otro símbolo en lugar de “d” el autómata
rechazaría la cadena en este punto ya que solo es válido ese
símbolo desde el estado q0 para pasar al q2.
Al leer el símbolo siguiente que es “a” pasa del estado q2 al
q1 y allí se queda esperando el siguiente símbolo.
Al leer el símbolo “b” pasa del estado q1 al estado q2, con
esto podemos ver que desde q2 puede recibir la cadena “ab”
de manera infinita y volver a q1, por lo cual esta se
representa con una estrella de Kleene.
Se repite una vez más el símbolo “a” seguido del “b” y se
ubica en el estado q2.
Por último, desde q2 se lee el ultimo símbolo de la cadena el
cual es “b”, con este símbolo llegamos a q3 que es uno de
los estados de la aceptación por lo cual esta cadena ha sido
aceptada por nuestro autómata.
REFERENCIAS BIBLIOGRÁFICAS
Carrasco, R. C., Calera Rubio, J., & Forcada Zubizarreta, M. L. (2000). Teoría de lenguajes,
gramáticas y autómatas para informáticos. Digitalia. (pp. 127 - 142). Recuperado de
[Link]
[Link]/[Link]?direct=true&db=nlebk&AN=3180
32&lang=es&site=ehost-live&ebv=EB&ppid=pp_Cover
González, A. [Ángela]. (2017, noviembre 5). Autómatas Finitos. [Archivo de video]. Recuperado
de [Link]
González, A. [Ángela]. (2018, junio 1). Lenguajes Regulares. [Archivo web]. Recuperado de
[Link]
González, A. [Ángela]. (2016, mayo 30). Conversión de AFN a AFD con transiciones vacías.
[Archivo web]. Recuperado de [Link]
