Tarea 2 - Diseño de Autómatas

Tarea 2 – Diseño de Autómatas
Realizado por:
Carlos Mauricio Vargas Ciceri
Cod: 1.117.511.542
Entregado a:
Rafael Pérez Holguín
Autómatas y Lenguajes Formales
Grupo 301405_36
Universidad Nacional Abierta y a Distancia – UNAD
Escuela de ciencias básicas tecnología e ingeniería - ECBTI
Programa de Ingeniería de sistemas
CEAD Florencia, febrero de 2022

Introducción
Con el desarrollo del siguiente trabajo se pretende demostrar que se han adquirido los
conocimientos con respecto a la minimización de los autómatas, y su funcionamiento.
También es importante complementar la solución de los ejercicios de la actividad a
través del uso de herramientas computacionales de simulación, empleando los conceptos
aprendidos en nuestros estudios de las diversas ramas de la ingeniería en nuestra institución
universitaria.
Ejercicio 1
Autómata a Expresión Regular
Ejercicio Por
Trabajar
Caracterización Aplicando la técnica de eliminación de estados, eliminaremos
Del Autómata todos los estados excepto los estados finales y el estado inicial, en
este caso se eliminará los estados q2 y q3.
El primer estado a eliminar será: q2.
Q2 tiene como estados sucesores a: q0, q1, y tiene como estados
predecesores a: q1, q3, por lo tanto:
Para el estado sucesor q0 con el estado predecesor q1:
Q=0
P=1
S=0
R=1
Aplicando la formula R + Q S* P
La nueva etiqueta, para la transformación de q0 a q1 será: 1+01
Q=0
P=1
S=0
R=0
La nueva etiqueta, para la transición de q0 a q3 será: 01
Q=1
P=1
S=0
R=0
Q=1
P=1
S=0
R=0
El siguiente estado a eliminar es: q3
q3 tiene como estados sucesores a: q0, q1, y tiene al estado
predecesor: q1, por lo tanto:
Q = 01
P=1
S=0
R = (1+01)
Aplicando la formula R + Q S*P
La nueva etiqueta, para la transición de q0 a q1 será:
(1+01)+011
Q = 11
P=1
S=0
R = 11
La nueva etiqueta, para la transición de q1 a q1 será: 11+111
Procedimiento De Ahora solo queda estados finales y el estado inicial
Conversión De Ahora, ubicaremos el estado inicial y para cada uno de los estados
Autómata Finto A finales seleccionaremos un estado final a la vez, el resto de estados
Expresión se consideran como no finales y serán eliminados con el mismo
Regular Paso A procedimiento de eliminación de estados. Al final obtendremos una
Paso expresión regular para cada estado final, y la expresión regular
completa será la unión de todas las ER de cada estado final.
En este caso solo existe un estado final el cual es: q1, aplicaremos
el procedimiento para calcular la expresión regular final.
En este caso el autómata se reduce a dos estados, donde:
R=0
S = (1+01)+011
U = 11+111
T=0
Aplicando la formula (R + S U* T)* S U*
La ER es: ((1+01)+011)(11+111)*
Ahora construiremos la ER regular final.

ER construidas hasta el momento:
ER del estado final q1 = ((1+01)+011)(11+111)*
Autómata Final
Convertido
Lenguaje Regular ((1+01)+011)(11+111)*
(1+01+011)(11+111)*
Ejercicio 2
Conversión de autómatas finitos Deterministas a autómatas finitos no deterministas
(AFD a AFND) y viceversa.
Ejercicio por
trabajar
Caracterizaci En el primer paso es obtener el conjunto potencia de los estados la
ón del autónoma. El conjunto potencia de un conjunto dado es otro conjunto
autómata formado por todos los subconjuntos del conjunto dado. Por ejemplo,
dado el conjunto:
Estados = {q0, q1, q2}
El conjunto potencia es:
P(Estados) ={0,{q0},{q1},{q2},{q0,q1},{q1,q2},{q0,q2},{q0,q1,q2}
Observa que el subconjunto 0 es incluido llamado conjunto vacío.
Por tanto, debemos construir una tabla de estados, que considere el
conjunto potencia de los estados del AFN original.

El siguiente paso será calcular las transiciones del AFD que estamos
calculando.
Procedimient CONVERTIR A AFD
o de Para calcular las transiciones D(S,A) nos fijamos en todos los estados P
conversión de S, vemos que estados de N pasan a P con la entrada A, y calculamos
paso a paso la unión de todos estos estados.

Se observa que el estado 0 funciona como un estado basura, todas sus
transiciones son a sí mismo, e igualmente cuando una transición D(S,A)
sea vacío, es decir la unión U de todos los trancones de P sean vacías, la
transición D(S,A) apuntará al estado 0.
Una vez calculada la tabla de transiciones del AFD, el siguiente paso es
definir el estado inicial y los estados finales.
En este caso el estado inicial original es q0, por tanto, el estado inicial
será {q0}.
En este caso el estado final original es: q1 por lo tanto los estados
finales del AFD son:
{q1},{q0,q1},{q1,q2},{q0,q1,q2},{q1,q3},{q0,q1,q3},{q1,q2,q3},{q0,
q1,q2,q3}
El proceso ha finalizado, adicionalmente se puede renombrar los
estados de la forma q0, q1, etc.
Autómata
Final
convertido
Practicar y
verificar lo
aprendido
Ejercicio Grupal
Construir autómata que realice lo siguiente:
ER = (a+bb(ab)*a)(b(ab)*a)*
Deben diligenciar la siguiente información:
Ejercicio Por
Trabajar
Notación formal
del autómata
minimizado.
Caracterización
del autómata
parte teórica
Lenguaje regular
Validación de
cadena
Practica y
verificar lo
aprendido
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). https://bibliotecavirtual.unad.edu.co/login?url=https://search-ebscohost-
com.bibliotecavirtual.unad.edu.co/login.aspx?direct=true&db=nlebk&AN=318032&lang=e
s&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). 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. (2017). Autómatas Finitos. Repositorio Institucional
UNAD. http://hdl.handle.net/10596/10470
González, A. (2018). Lenguajes Regulares. Repositorio Institucional
UNAD. http://hdl.handle.net/10596/18315
González, A. (2020). Lenguajes Regulares. Repositorio Institucional
UNAD. https://campus113.unad.edu.co/ecbti73/mod/hvp/view.php?id=1672

Tarea 2 - Diseño de Autómatas

Cargado por

Copyright:

Formatos disponibles

Tarea 2 - Diseño de Autómatas

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tarea 2 - Diseño de Autómatas

Cargado por

Copyright:

Formatos disponibles

Tarea 2 – Diseño de Autómatas

Carlos Mauricio Vargas Ciceri

Rafael Pérez Holguín

Autómatas y Lenguajes Formales

Universidad Nacional Abierta y a Distancia – UNAD

Escuela de ciencias básicas tecnología e ingeniería - ECBTI

Programa de Ingeniería de sistemas

CEAD Florencia, febrero de 2022

conocimientos con respecto a la minimización de los autómatas, y su funcionamiento.

También es importante complementar la solución de los ejercicios de la actividad a

través del uso de herramientas computacionales de simulación, empleando los conceptos

aprendidos en nuestros estudios de las diversas ramas de la ingeniería en nuestra institución

Autómata a Expresión Regular

Caracterización Aplicando la técnica de eliminación de estados, eliminaremos

este caso se eliminará los estados q2 y q3.

El primer estado a eliminar será: q2.

Q2 tiene como estados sucesores a: q0, q1, y tiene como estados

predecesores a: q1, q3, por lo tanto:

Para el estado sucesor q0 con el estado predecesor q1:

La nueva etiqueta, para la transformación de q0 a q1 será: 1+01

Para el estado sucesor q0 con el estado predecesor q3:

La nueva etiqueta, para la transición de q0 a q3 será: 01

Para el estado sucesor q1 con el estado predecesor q1:

La nueva etiqueta, para la transición de q1 a q1 será: 11

Para el estado sucesor q1 con el estado predecesor q3:

La nueva etiqueta, para la transición de q1 a q3 será: 11

El siguiente estado a eliminar es: q3

q3 tiene como estados sucesores a: q0, q1, y tiene al estado

predecesor: q1, por lo tanto:

Para el estado sucesor q0 con el estado predecesor q1:

Aplicando la formula R + Q S*P

La nueva etiqueta, para la transición de q0 a q1 será:

Para el estado sucesor q1 con el estado predecesor q1:

La nueva etiqueta, para la transición de q1 a q1 será: 11+111

Procedimiento De Ahora solo queda estados finales y el estado inicial

Autómata Finto A finales seleccionaremos un estado final a la vez, el resto de estados

Expresión se consideran como no finales y serán eliminados con el mismo

Regular Paso A procedimiento de eliminación de estados. Al final obtendremos una

Paso expresión regular para cada estado final, y la expresión regular

completa será la unión de todas las ER de cada estado final.

el procedimiento para calcular la expresión regular final.

En este caso el autómata se reduce a dos estados, donde:

Aplicando la formula (R + S U* T)* S U*

Ahora construiremos la ER regular final.

ER del estado final q1 = ((1+01)+011)(11+111)*

Lenguaje Regular ((1+01)+011)(11+111)*

Conversión de autómatas finitos Deterministas a autómatas finitos no deterministas

(AFD a AFND) y viceversa.

Caracterizaci En el primer paso es obtener el conjunto potencia de los estados la

ón del autónoma. El conjunto potencia de un conjunto dado es otro conjunto

Estados = {q0, q1, q2}

El conjunto potencia es:

Observa que el subconjunto 0 es incluido llamado conjunto vacío.

Por tanto, debemos construir una tabla de estados, que considere el

conjunto potencia de los estados del AFN original.

Procedimient CONVERTIR A AFD

conversión de S, vemos que estados de N pasan a P con la entrada A, y calculamos

paso a paso la unión de todos estos estados.