AUTÓMATAS Y LENGUAJES FORMALES
KELLY JOHANA SIERRA ANDRADE
COD. 1065137869
GRUPO # 2
UNIDAD 1
TAREA 2 DISEÑO DE AUTÓMATAS
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
CEAD – VALLEDUPAR
SEPTIEMBRE 2021
TAREA 2
DISEÑO DE AUTÓMATAS
Elección de ejercicios.
Ejercicios: El estudiante desarrolla los ejercicios b en todos los tres tipos propuestos.
Rol: Evaluador.
Ejercicios a Desarrollar.
Ejercicio 1: Autómata a expresión regular.
EJERCICIO A
TRABAJAR
Caracterización del En este espacio se realiza:
autómata - Identificación de la quíntupla del autómata
M= ({q0, q1, q2}, {a, b}, δ q0, {q1})
K= {q0, q1, q2}
∑= {a, b}
S= q0
F= q1
- Plasme la tabla de transición
a b
q0 q2 q1
# q1 … …
q2 q2 q0, q1
- Identificación del Autómata Finito Determinista o Autómata Finito No
Determinista
Podemos identificar que el autómata de la imagen es un autómata no
determinista.
- Explicar las características del tipo de autómata
Las características para definir el autómata como no determinista es que cada
combinación o símbolo de entrada puede estar en varios estados de manera
simultánea, como es el caso el estado q2 se dirige con b a los estados q1 y q0.
Procedimiento de Realice de manera detallada el procedimiento paso a paso de la conversión del
conversión de autómata a expresión regular y según ejemplo revisado.
Autómata Finito a
Expresión Regular conversión a AFD para hallar expresión regular.
paso a paso
- Paso 1. Se elimina estado q3
- Paso 2. Se elimina estado q2
Autómata Final En este espacio se presenta la expresión correspondiente al
convertido autómata trabajado.
Lenguaje En este espacio agrega el lenguaje regular correspondiente a
regular la expresión regular.
(aa*b)*b+aa*b)
Ejercicios 2: Conversión de Autómatas Finitos Deterministas a Autómatas Finitos No deterministas (AFD a
AFND) y viceversa.
EJERCICIO A
TRABAJAR
Caracterización En este espacio se realiza:
del autómata - Identificación de la quíntupla del autómata
M= ({q0, q1, q2}, {a, b}, δ q0, {q2})
K= {q0, q1, q2}
∑= {a, b, c, y}
S= q0
F= q2
- Plasme la tabla de transición
a b c y
q0 q0, q1 q2 … …
# q2 … … … q0
q1 … … q1, q2 …
- Identificación del Autómata Finito Determinista o Autómata Finito No
Determinista
Podemos identificar que el autómata de la imagen es un autómata no
determinista.
- Explicar las características del tipo de autómata
Las características para definir el autómata como no determinista es que cada
combinación o símbolo de entrada puede estar en varios estados de manera
simultánea.
Procedimiento de Realice de manera detallada el procedimiento paso a paso de la conversión del
conversión paso autómata según corresponda y según ejemplo revisado.
a paso
Conversión de Autónoma Finito No Determinista a Autónoma Finito Determinista.
Paso a paso.
a b c y
q0 q0, q1 q2 … …
q2 … … … q0
q1 … … q1, q2 …
a b c y
q,q
0 1
q 1
q2
q2
…
q1, q2 … … q1 …
q2 … … … q0
q0 q0, q1 q2 … …
Se convierte a AFD.
(a*(b+ac*c)y)*a*(b+ac*c)
Autómata Final En este espacio se presenta el autómata final
convertido
Practicar y Apoyándose en el simulador JFlap JFLAP (Anexo 1 - JFLAP) o VAS (Anexo 2-
verificar lo VAS) ejecutar los dos autómatas, el original y el autómata resultado final de la
aprendido conversión y validar por lo menos tres cadenas válidas y tres cadenas rechazadas.
En este espacio agregar las imágenes tomadas del simulador utilizado.
Ejercicio Grupal: Construir autómata Construir un autómata que realice lo siguiente:
ER = (ab*c(cc)*b)
Deben diligenciar la siguiente información:
EJERCICIO A Registre aquí el Autómata realizado. Por favor
TRABAJAR agregue la imagen
Notación En este espacio agrega la notación formal del
formal del autómata. Identifique la quíntupla del autómata
autómata creado.
minimizado M= ({q0, q1, q2}, {a, b}, δ q0, {q2})
K= {q0, q1, q2}
∑= {a, b, c}
S= q0
F= q2
Caracterización Identifique los elementos (tupla, estado final, inicial,
del autómata alfabeto, etc.). Debe explicar y describir cada
parte teórica elemento y la función y significado en el autómata.
Conceptos y definiciones adicionales.
Tupla: En este caso es una lista o secuencia ordenadamente por n elementos.
Estado final: Es la salida del modelo conformado por estados de forma automática.
Estado inicial: La entrada de una cadena que se va leyendo a medida que se generan
estados uno a otros.
Alfabeto: Conjunto de símbolos finitos y no finitos, ya sea con símbolos o letras, ∑=
{0,1}, el alfabeto binario
Ø ∑= {a, b, ……. z}, es el conjunto de todas las letras minúsculas.
Cadenas: es la secuencia finita de símbolos ya sea si ∑= {0,1}, entonces ∑1= {0,1},
∑2= {00, 01, 10, 11}, ∑3= {000, 001, 010, 011, 100, 101, 110, 111}.
Lenguaje En este espacio agrega el lenguaje regular del
Regular autómata.
Validación de Identifique 5 cadenas aceptadas y cinco cadenas
cadenas Rechazadas
Practicar y Muestre en el simulador JFLAP (Anexo 1 - JFLAP)
verificar lo o VAS (Anexo 2- VAS) (gráficamente) como
aprendido 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)
En esta cadena valida, se generan 4 recorridos, primero del estado inicial al estado q1
del estado indicado anteriormente nuevamente recorre al estado q1 de la secuencia
sigue al estado final q2 .
REFERENCIAS
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=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
[Link]
direct=true&db=edsbas&AN=edsbas.62161440&lang=es&site=eds-live&scope=site
