LENGUAJES Y AUTOMATAS 1

Autómatas finitos deterministas

Profesora:
Graciela García Morales

Nombre de Alumno: No. Control

Angel Ramirez Castro 21321162

Horario:
13:00 a 14:00

Acapulco Gro. a 22 de abril de 2024

 Introducción
Los autómatas finitos deterministas (AFD) son una herramienta fundamental en el mundo
de la informática y la teoría de la computación. Estos dispositivos, utilizados para modelar y
resolver problemas, tienen múltiples aplicaciones en áreas como la inteligencia artificial, la
lingüística computacional y el diseño de algoritmos.
Los autómatas finitos deterministas tienen diversas aplicaciones en el campo de la
informática y la electrónica. Algunas de las aplicaciones más comunes son el análisis léxico,
diseño de circuitos, protocolos de comunicación, sistemas de control y muchas otras
aplicaciones.

En el presente trabajo vamos a definir lo que es un autómata finito determinista, al igual

que conoceremos la simbología que compone a este tipo de autómatas y la explicación de
cada uno de los símbolos, por ultimo veremos algunos ejemplos en donde son utilizados los
autómatas finitos deterministas.
 Desarrollo
 ¿Qué es un autómata finito determinista?
Un autómata finito determinista es un modelo matemático utilizado para representar
sistemas de control o procesos que siguen una serie de reglas predefinidas. Está
compuesto por un conjunto finito de estados, un alfabeto de entrada, una función de
transición y un estado inicial y uno o varios estados de aceptación.
La característica determinista del AFD significa que, para cada par de estado y símbolo
de entrada, solo hay una transición definida. En otras palabras, dada una configuración
específica del autómata (estado actual y símbolo de entrada), el próximo estado al que
transiciona está completamente determinado. Esto contrasta con los autómatas finitos
no deterministas (AFND), donde para una configuración dada, podría haber múltiples
transiciones posibles.
El funcionamiento de un autómata finito determinista se basa en su capacidad para leer
una cadena de símbolos de entrada y cambiar de estado de acuerdo con la función de
transición. El autómata inicia en el estado inicial y, a medida que lee los símbolos de
entrada, se mueve de un estado a otro según la función de transición.

La función de transición es una tabla que específica para cada estado y cada símbolo de
entrada, el estado al que se debe mover el autómata. Esto permite al autómata
reconocer y aceptar o rechazar cadenas de símbolos según las reglas establecidas.

 Simbología utilizada quíntupla

La quíntupla de un autómata finito determinista (AFD) describe formalmente su
estructura y comportamiento. Consiste en cinco elementos principales los cuales son:
(Q, Σ, δ, q0, F).

 Un AFD consta de un conjunto finito de estados, donde cada estado representa

una configuración particular del sistema en un momento dado. Estos estados
pueden ser representados por símbolos o letras, y se denotan con letras
mayúsculas como Q. Los estados se suelen representar mediante nombres o
símbolos, por ejemplo:
Q= {𝑞0, 𝑞1, 𝑞2, …}

 El alfabeto es el conjunto de símbolos o letras que el AFD utiliza para leer la

entrada. Puede ser cualquier conjunto finito de símbolos, como letras, números
o caracteres especiales. El alfabeto se denota con la letra griega sigma (Σ). El
alfabeto de entrada se representa como un conjunto de símbolos, por ejemplo:
Σ = {a, 𝑏, 𝑐, …}
  La función de transición es una función matemática que define cómo el AFD
cambia de un estado a otro en respuesta a una entrada dada. Se representa
mediante una tabla o un diagrama de transición, y se denota con la letra delta
(δ). Por ejemplo:
δ (q0, a) = q1 indica que si el AFD está en el estado q0 y recibe el símbolo a,
transicionará al estado 𝑞1.

 El estado inicial es el estado en el que se encuentra el AFD al comienzo de su

ejecución. Es el punto de partida desde el cual el AFD comienza a procesar la
entrada. Se denota con la letra q0.

 El conjunto de estados finales es un subconjunto de los estados del AFD que

indica cuándo se ha alcanzado un estado de aceptación. Cuando el AFD llega a
un estado final, se considera que ha reconocido una cadena de entrada válida.
Este conjunto se denota con F. Por ejemplo:
𝐹 = {𝑞1, 𝑞2} indica que los estados 𝑞1 y q2 son estados de aceptación.

En conjunto, esta quíntupla describe completamente la estructura y el comportamiento de

un autómata finito determinista.

 Ejemplos de autómatas finitos deterministas

Los autómatas finitos deterministas están presentes en nuestra vida cotidiana,

algunos ejemplos en donde los podemos encontrar son:

Cajero Automático

1. Conjunto de estados (𝑄Q): 𝑄= {𝑞inicio, 𝑞espera, 𝑞pin, 𝑞opciones, 𝑞retiro, 𝑞saldo}

𝑞inicio: Estado inicial, donde el cajero automático espera una tarjeta para comenzar
la transacción.
𝑞selección: Estado en el que se espera que el usuario
seleccione una operación (por ejemplo, retirar efectivo,
consultar saldo, etc.).
𝑞pago: Estado en el que se espera que el usuario
introduzca la cantidad de dinero a retirar o realice otra
acción, como el pago de facturas.
𝑞entrega: Estado en el que el cajero automático entrega
el dinero solicitado y cualquier recibo correspondiente.
 𝑞fin: Estado final, donde se completa la transacción y se devuelve la tarjeta al
usuario.

2. Alfabeto de entrada(ΣΣ): Σ= {tarjeta, PIN, opciones, retiro, saldo}

El usuario introduce monedas en el cajero automático para realizar la transacción,
y selecciona la operación deseada.

3. Función de transición (𝛿δ): {

 𝛿 (𝑞inicio, tarjeta) =𝑞pin
 𝛿 (𝑞pin, PIN) = 𝑞opciones
 𝛿 (𝑞opciones, opciones) =𝑞espera
 𝛿 (𝑞opciones, retiro) = 𝑞retiro
 𝛿 (𝑞opciones, saldo) =𝑞saldo
 𝛿 (𝑞retiro, espera) =𝑞espera
 𝛿 (𝑞saldo, espera) =𝑞espera
}
Las transiciones entre estados se definen en función de las acciones del usuario y el
estado actual del cajero automático.
Por ejemplo, al insertar una moneda en el estado 𝑞inicio, el cajero automático
transiciona al estado 𝑞selección, donde el usuario puede seleccionar la operación
deseada.
Si el usuario selecciona una operación en 𝑞selección el cajero automático transiciona
al estado 𝑞pago para solicitar más información o confirmación del usuario.
Una vez que se completa la transacción y se entrega el dinero en el estado 𝑞entrega,
el cajero automático regresa al estado 𝑞inicio para esperar la próxima transacción.

4. Estado inicial (𝑞0): 𝑞0=𝑞inicio

El estado inicial es 𝑞inicio donde el cajero automático espera que se inserte una
tarjeta para iniciar la transacción.

5. Estados de aceptación (𝐹F): 𝐹= {𝑞espera, 𝑞pin, 𝑞opciones, 𝑞retiro, 𝑞saldo}

En este caso, el estado de aceptación es 𝑞fin, que representa la finalización exitosa
de una transacción y la devolución de la tarjeta al usuario.

Sistema de alarma residencial

1. Conjunto de estados (Q): 𝑄= {𝑞inactivo, 𝑞activado, 𝑞alarma}

𝑞inactivo: Estado inicial, donde el sistema de alarma está desactivado.
 𝑞activado: Estado en el que el sistema de alarma está activado y listo para detectar
intrusos.
𝑞alarma: Estado que se activa cuando se detecta una intrusión.

2. Alfabeto de entrada (Σ): Σ= {apagar, activar, intrusión}

El sistema recibe como entrada comandos para apagar o activar la alarma, así como
señales de intrusión.

3. Función de transición (𝛿δ): {

 𝛿 (𝑞inactivo, activar) =𝑞activado
 𝛿 (𝑞activado, intrusión) =𝑞alarma
 𝛿 (𝑞alarma, apagar) = 𝑞inactivo
 }
Si el sistema está en el estado 𝑞inactivo y recibe el comando de activación (activar),
transiciona al estado 𝑞activado.
Si el sistema está en el estado 𝑞activado y se detecta una intrusión (intrusión),
transiciona al estado 𝑞alarma.
Si el sistema está en el estado 𝑞alarma y recibe el comando de apagado (apagar),
transiciona al estado 𝑞inactivo.

4. Estado inicial (𝑞0): 𝑞0= 𝑞inactivo

El estado inicial es 𝑞inactivo, lo que indica que el sistema de alarma está desactivado
al principio.

5. Estados de aceptación (F): 𝐹={𝑞alarma}

En este caso, el estado de alarma 𝑞alarma no es un estado de aceptación. Los
estados de aceptación pueden no ser relevantes en este contexto, ya que el objetivo
no es necesariamente llegar a un estado de aceptación, sino más bien responder
apropiadamente a los eventos de entrada.
 Conclusión
Después de realizar la investigación anterior puedo concluir que los autómatas
finitos deterministas son modelos matemáticos utilizados para representar sistemas
de control o procesos que siguen reglas predefinidas. Estos autómatas están
compuestos por cinco elementos principales: un conjunto finito de estados, un
alfabeto de entrada, una función de transición, un estado inicial y uno o varios
estados de aceptación.
Logré comprender que la característica determinista del AFD implica que, para cada
par de estado y símbolo de entrada, solo hay una transición definida. Esto significa
que, dado un estado y un símbolo de entrada específicos, el próximo estado al que
se transicionará está completamente determinado.
Además, logré identificar la quíntupla de un AFD, la cual consta de los conjuntos de
estados (Q), el alfabeto de entrada (Σ), la función de transición (𝛿), el estado inicial
(q0) y los estados de aceptación (𝐹), describe formalmente la estructura y el
comportamiento del AFD.
Por último, en los ejemplos que logré encontrar, como el cajero automático y el
sistema de alarma residencial, comprendí cómo los AFD se aplican en situaciones
cotidianas para modelar y controlar sistemas complejos.

Bibliografía
Santos, M. D. (2023a, noviembre 14). Automata Finito Determinista: Todo lo que debes

saber - Polaridad.es. Polaridad.es. https://polaridad.es/automata-finito-determinista/

Hopcroft J. E., Ullman J.D. (2007). “Introducción a la teoría de autómatas, lenguajes y

computación”. 3ª ed. Edit. Pearson Educación, Madrid.

colaboradores de Wikipedia. (2019b, julio 12). Autómata finito determinista. Wikipedia, la

Enciclopedia Libre.

https://es.wikipedia.org/wiki/Aut%C3%B3mata_finito_determinista