Actividad 01 Autómatas Finitos 1 - Nah AD

Vista previa del material en texto

Universidad del Valle de México 
 
Traductores 
 
Profesor: Villa Gonzales Gerson 
 
“Actividad 01 Autómatas Finitos” 
 
 
 
Alumno 
 
 Arias Díaz Ian | 080042508 
 
 
 
 
 
 
 
Fecha de entrega: 24/10/2021 
Introducción 
 
Un autómata determinista (DFA) es una maquina de estados finitos que 
acepta o rechaza cadenas finitas de caracteres o símbolos y produce el 
mismo calculo único para cada entrada (cadenas de entrada). 
 
Consiste en un conjunto finito de estados y un conjunto de transiciones 
entre esos estados, que dependen de los símbolos de la cadena de entrada. 
 
El DFA se detendrá para cualquier cadena de entrada y aceptará o 
rechazará dicha cadena, El autómata finito acepta una cadena x si la 
secuencia de transiciones correspondientes a los símbolos de x conduce 
desde el estado inicial a un estado final, se dice que un DFA M reconoce un 
lenguaje L(M), que es el conjunto de todas las cadenas que M acepta. 
 
Desarrollo 
 
Autómata desarrollado en clase 1 
 
 
 
 
Autómata desarrollado en clase 2 
 
 
 
Autómata desarrollado en clase 3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Conclusión 
 
Un DFA es una máquina que consiste en un conjunto de estados y de 
transiciones entre esos estados, que, dependiendo de las cadenas de 
entrada y sus símbolos, la aceptara o rechazara si dicha cadena no llega a 
un estado final. 
 
Utilizando la herramienta JFLAP realizamos varios y diferentes DFA, para 
después aplicarles o insertar varias cadenas de entradas para ver el 
comportamiento o secuencia que realizan los autómatas para aceptar o 
rechazar las cadenas insertadas. 
 
Lo que observe con esta herramienta fue lo siguiente: 
 
• Un DFA solo puede tener un estado inicial. 
• Un DFA puede tener varios estados finales. 
• Se pueden realizar secuencias o transiciones desde un mismo 
estado. 
• El DFA rechazara la cadena si no finaliza en un estado final 
dependiendo de la secuencia de los símbolos. 
 
Referencias 
 
Users.exa.unicen.edu.ar. 2009. CIENCIAS DE LA COMPUTACION I. [online] Disponible en: 
<https://users.exa.unicen.edu.ar/catedras/ccomp1/ApunteAutomatasFinitos.pdf> [Revisado 
el 18 de Octubre del 2021].