¿Qué son los autómatas finitos deterministas?
Los autómatas finitos deterministas (o DFA) son máquinas de estados finitos que aceptan o rechazan cadenas de caracteres analizándolas a través de una secuencia que está determinada de forma única por cada cadena.
El término «determinista» se refiere al hecho de que cada cadena, y por tanto cada secuencia de estado, es única. En un DFA, una cadena de símbolos se analiza a través de un autómata DFA, y cada símbolo de entrada se moverá al siguiente estado que se pueda determinar.
Estas máquinas se llaman finitas porque hay un número limitado de estados posibles que se pueden alcanzar. Un autómata finito sólo se llama determinista si puede cumplir ambas condiciones. Los DFAs se diferencian de los autómatas no deterministas en que estos últimos son capaces de transitar a más de un estado a la vez y estar activos en múltiples estados a la vez.
En la práctica, los DFAs están formados por cinco componentes (y a menudo se denotan con un conjunto de cinco símbolos conocido como 5-tupla). Estos componentes incluyen:
- Un número finito de estados
- Un conjunto de símbolos conocido como alfabeto, también de número finito
- Una función que opera la transición entre estados para cada símbolo
- Un estado inicial de arranque donde se da o procesa la primera entrada
- Un estado o estados finales, conocidos como estados de aceptación.
Vea Sisense en acción:
Explore el tablero de control
¿Cómo puedo utilizar los autómatas finitos deterministas?
Aunque originalmente fueron creados como modelos matemáticos abstractos, los DFAs hoy en día se han generalizado tanto en la informática como en la ciencia de los datos. Los autómatas finitos son utilizados por la mayoría de los compiladores de lenguaje informático para ayudar a analizar y preparar el código para su uso real. Además, se utilizan ampliamente en los sistemas de procesamiento del lenguaje, incluso en el procesamiento del lenguaje natural, para ayudar a los programas a entender cómo responder a entradas únicas y variadas.
Los AFD, debido a su incapacidad para habitar activamente en múltiples estados a la vez, también son esenciales en todo, desde los algoritmos de reconocimiento de contraseñas (para determinar si la entrada de un usuario es correcta o incorrecta) hasta los algoritmos de filtrado e incluso en las aplicaciones de procesamiento de texto. En la ciencia de los datos, los autómatas finitos deterministas básicos pueden utilizarse como herramientas de clasificación al construir almacenes de datos y otros sistemas de almacenamiento.
Al analizar los datos a medida que llegan y determinar su ubicación adecuada, un DFA puede automatizar una gran parte de la clasificación y hacerlo significativamente más rápido que la realización manual de la tarea. Cuando se combina con un autómata finito no determinista (o NFA), los almacenes de datos también pueden determinar si los datos pertenecen a más de una ubicación. El DFA y el NFA pueden utilizarse por separado para crear una solución mucho más amplia y eficaz.
Ver Sisense en acciónVolver al Glosario