Unidad 1 – Lenguajes Regulares
Tarea 2 – Diseño de Autómatas
ESTUDIANTE:
DEIMAR FABIAN CUCHIMBA RIOS
Código: 1.081.415.767
GRUPO:
301405_57
Tutor:
JAIME JOSE VALDES
Máster en Tecnología de la Información
Universidad Nacional Abierta y a Distancia – UNAD
Escuela Ciencias básicas, tecnología e ingeniería
Programa Ingeniería de Sistemas
10 de Marzo del 2021
AUTÓMATAS Y LENGUAJES FORMALES
EJERCICIOS A DESARROLLAR
A continuación, se definen los ejercicios a desarrollar:
Ejercicios 1: Autómata a Expresión regular
Ejercicio a Trabajar:
(Ejercicio C)
Caracterización del Identificación de la quíntupla del Autómata
Autómata K=({q0 , q1 , q2 }{1 , 0 }, δ ,q 0 {q1 })
K = {q0 , q1 , q2 } hace referencia al conjunto de estados del autómata.
Σ={0,1} hace referencia al alfabeto del autómata
S = q 0 estado inicial en K
S = {q 1} es el conjunto de estados final en K del autómata.
δ :{q0 , q 1 , q 2 }x {1,0 }→ {q 0 , q 1 , q 2 } viene dada por:
δ ( q0 , 1 ) =q 1
δ ( q0 , 0 )=q 2
δ ( q1 , 1 ) =q1
δ ( q1 , 1 ) =q2
δ ( q2 , 0 )=q 0
La tabla de transición de estados se encabeza por los estados y las
columnas encabezados por los símbolos de entrada.
Estado Estado Salida
Actual Siguiente
0 1
Q0 q 2 q 1 1
Q1 Ø q1, q2 1
Q2 q0 Ø 0
En este ejercicio agregamos vacío “Ø” ya que no existe transición
con ese alfabeto.
El autómata es Finito No Determinista AFND, ya que para cada
estado en que se encuentre el autómata existe más de una transición
posible hacia cualquier estado.
Procedimiento de
conversión de
Autómata Finito a
Expresión Regular
paso a paso
Autómata Final ((00)*11*10)*(00)*11*
convertido
Lenguaje regular ((00)*11*10)*(00)*11*
Ejercicios 2: Conversión de Autómatas Finitos Deterministas a Autómatas Finitos No
deterministas (AFD a AFND) y viceversa.
Ejercicio a Trabajar:
(Ejercicio C)
Caracterización del La descripción matemática del autómata finito es la quíntupla
Autómata M =({q 0 ,q 1 ,q 2 ,q 3 }{0,1 }, δ ,q 0 {q1 })
K = {q0 , q1 , q2 , q 3 , } es el conjunto de los estados del autómata
Σ={0,1} hace referencia al alfabeto del autómata
S = q 0 estado inicial en K
S = {q 1} es el conjunto de estados final en K del autómata.
δ :{q0 , q 1 , q 2 , q3 }x {1,0 }→ {q 0 ,q 1 , q 2 , q 3 } viene dada por:
δ ( q0 , 1 ) =q 1
δ ( q0 , 0 )=q 3
δ ( q1 , 1 ) =q2
δ ( q2 , )=q 0
δ ( q3 , 1 ) =q2
Estado Estado
Actual Siguiente
0 1
Q0 q3 q1
Q1 Ø q2
Q2 vacioq 0
Q3 q2
El autómata es Finito Determinista AFD porque cada entrada existe
no más de una transición.
Procedimiento de
conversión de
Autómata Finito a
Expresión Regular
paso a paso
0 1
A={q0} {3} {1}
B={q1} {2}
C={q2} -- --
D={q3} {2}
Autómata Final El autómata finito determinista resultante es
convertido
Practicar y verificar lo Apoyándose en el simulador JFlap JFLAP (Anexo 1 - JFLAP) o VAS (Anexo
aprendido 2- VAS) ejecutar los dos autómatas, el original y el autómata resultado
final de la conversión y validar por lo menos tres cadenas válidas y tres
cadenas rechazadas.
Ilustración 1. Autómata inicial
Bibliografía
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 https://bibliotecavirtual.unad.edu.co/login?url=https://search-
ebscohost-com.bibliotecavirtual.unad.edu.co/login.aspx?
direct=true&db=nlebk&AN=318032&lang=es&site=ehost-
live&ebv=EB&ppid=pp_Cover
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
