Guía de actividades y rúbrica de evaluación –
Tarea 2 Diseño de Autómatas
Curso: Autómatas y lenguajes formales
Código: 301405
Michael Stuar Cano Hernández
Código: 1097396568
TUTOR:
ANYELO GERLEY QUINTERO
GRUPO: 301405_108
Universidad Nacional Abierta y a Distancia
Vicerrectoría Académica y de Investigación
Leticia 11 de septiembre 2022
EJERCICIOS PARA DESARROLLAR
Tarea 2 - Diseño de Autómatas
A continuación, se definen los ejercicios a desarrollar:
Tener en cuenta que:
Estado Inicial
# Estado Final
Ejercicios 1: Autómata a Expresión regular
Con el ejercicio seleccionado debe diligenciar la siguiente tabla:
EJERCICIO A
TRABAJAR
Caracterización Identificación de la quíntupla
del autómata
𝑸 = {𝒒𝟎, 𝒒𝟏, 𝒒𝟐}
∑ = {𝒂, 𝒃}
𝒔 = 𝒒𝟎
𝑭 = 𝒒𝟐
𝛿 = {𝑇𝑎𝑏𝑙𝑎 𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖ó𝑛}
𝛿(𝑞0, 𝑎) = 𝑞1
𝛿(𝑞1, 𝑏) = 𝑞0
𝛿(𝑞1, 𝑏) = 𝑞0
𝛿(𝑞1, 𝑏) = 𝑞2
𝛿(𝑞2, 𝑏) = 𝑞1
AUTOMATA FINITO NO DETERMINISTA
Es autómata determinista tiene 3 estado (𝑞0, 𝑞1, 𝑞2)
Con un estado inicial en (𝑞0) y un estado final en (𝑞2) y 4
transiciones, se considera no autómata no determinista ya
tiene una salida hacia otro estado.
Procedimiento
de conversión
de Autómata
Finito a
Se elimina el estado de transición 𝑞1
𝑞0 → 𝑞0 = 𝑏𝑎
𝑞0 → 𝑞2 = 𝑏𝑎
Expresión
Regular paso a
paso
Concatenación (𝑞0, 𝑞2)
𝑬𝑹 = 𝑏𝑎
Expresión 𝑬𝑹 = 𝑏𝑎
regular
Lenguaje 𝑳𝑹[… ] = [… , 𝒂 … , 𝒃, … ]
regular
Ejercicios 2: Conversión de Autómatas Finitos Deterministas a
Autómatas Finitos No deterministas (AFD a AFND) y viceversa
a. b. c.
Estados: q0, q1, q2, q3 Estados: q0, q1, q2, q3, q4 Estados: q0, q1, q2, q3, q4
Alfabeto: {0, 1} Alfabeto: {a, b} Alfabeto: {0, 1}
Estado inicial: q0 Estado inicial: q0 Estado inicial: q0
Estado final: q2 Estado final: q4 Estado final: q4
Transiciones: Transiciones: Transiciones:
• q0, 0 -> q1 • q0, a -> q1 • q0, 0 -> q1
• q0, ε -> q2 • q0, ε -> q2 • q0, ε -> q2
• q1, 1 -> q2 • q2, 0 • q1, ε -> q3 • q1, 1 -> q2
-> q3 • q2, b -> q3 • q2, ε -> q3
• q3, 1 -> q2 • q3, a -> q4 • q3, 0 -> q4
d. e.
Estados: q0, q1, q2, q3 Estados: q0, q1, q2, q3
Alfabeto: {0, 1} Alfabeto: {a, b}
Estado inicial: q0 Estado inicial: q0
Estados finales: q3 Estados finales: q2, q3
Transiciones: Transiciones:
• q0, 0 -> {q1} • q0, a -> {q1}
• q0, 1 -> {q0, q2} • q0, b -> {q0, q2}
• q1, 0 -> {q3} • q1, 1 • q1, a -> {q3}
-> {q2} • q1, b -> {q1, q2}
• q2, 1 -> {q3} • q2, a -> {q2}
• q2, b -> {q3}
• q3, a -> {q3}
• q3, b -> {q0, q1}
Con el ejercicio seleccionado debe diligenciar la siguiente tabla:
EJERCICIO A Registre aquí el Ejercicio a trabajar. Por favor
TRABAJAR agregue la imagen
Caracterización En este espacio se realiza:
del autómata - Plasme la tabla de transición
- Identificación del Autómata Finito Determinista o
Autómata Finito No Determinista
- Explicar las características del tipo de autómata
Procedimiento Realice de manera detallada el procedimiento paso
de conversión a paso de la conversión del autómata según
paso a paso corresponda y según ejemplo revisado.
- Paso 1…
- Paso 2…
- Paso 3…
Autómata Final En este espacio se presenta el autómata final
convertido
Practicar y Apoyándose en el simulador JFlap JFLAP (Anexo 1 -
verificar lo JFLAP) o VAS (Anexo 2- VAS) ejecutar los dos
aprendido 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.
En este espacio agregar las imágenes tomadas del
simulador utilizado.
Ejercicio Grupal: Construir autómata
Elabore el autómata para el siguiente lenguaje sobre el alfabeto {a,b}:
L = {a, b, ba, aaa, bbb, baaba } sobre {a,b} Rechaza cadenas como:
ababab, bababa, abbbbb, bbabbb, bab, abab Deben diligenciar la
siguiente información:
EJERCICIO A Registre aquí el Autómata realizado. Por favor
TRABAJAR agregue la imagen
Caracterización En este espacio se realiza:
del autómata - Identificación de la quintupla
- Plasme la tabla de transición
- Identificación del Autómata Finito Determinista o
Autómata Finito No Determinista
- Explicar las características del tipo de autómata
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.
Lenguaje En este espacio agrega el lenguaje regular del
Regular autómata.
Validación de - Identifique 5 cadenas aceptadas y cinco cadenas
cadenas rechazadas a parte de las dadas
Practicar y - Muestre en el simulador JFLAP (Anexo 1 - JFLAP) o
verificar lo 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)
