minimización de DFA

En la teoría de autómatas (una rama de la informática teórica ), la minimización de DFA es la tarea de transformar un autómata finito determinista (DFA) dado en un DFA equivalente que tiene un número mínimo de estados. Aquí, dos DFA se denominan equivalentes si reconocen el mismo lenguaje regular . Se conocen y describen varios algoritmos diferentes que realizan esta tarea en libros de texto estándar sobre teoría de autómatas. ^[1]

Para cada lenguaje regular, también existe un autómata mínimo que lo acepta, es decir, un DFA con un número mínimo de estados y este DFA es único (excepto que a los estados se les puede dar nombres diferentes). ^{[2] [3]} El DFA mínimo garantiza un costo computacional mínimo para tareas como la coincidencia de patrones .

Hay dos clases de estados que se pueden eliminar o combinar del DFA original sin afectar el idioma que acepta.

El estado de un autómata finito determinista es inalcanzable si no existe ninguna cadena para la cual . En esta definición, es el conjunto de estados, es el conjunto de símbolos de entrada, es la función de transición (asignación de un estado y un símbolo de entrada a un conjunto de estados), es su extensión a cadenas (también conocida como función de transición extendida), es el estado inicial, y es el conjunto de estados de aceptación (también conocidos como finales). Los estados alcanzables se pueden obtener con el siguiente algoritmo:${\ estilo de visualización p}$${\ estilo de visualización M = (Q, \ Sigma, \ delta, q_{0}, F)}$${\ estilo de visualización w}$${\ estilo de visualización \ Sigma ^ {*}}$${\displaystyle p=\delta^{*}(q_{0},w)}$${\ estilo de visualización Q}$${\ estilo de visualización \ Sigma}$${\ estilo de visualización \ delta}$${\ estilo de visualización \ delta ^ {*}}$${\ estilo de visualización q_ {0}}$${\ estilo de visualización F}$

Suponiendo una implementación eficiente de los conjuntos (por ejemplo, new_states) y operaciones sobre ellos (como agregar un estado o verificar si está presente), este algoritmo se puede implementar con complejidad de tiempo , donde es el número de estados y es el número de transiciones de el autómata de entrada.${\ estilo de visualización O (n + m)}$${\ estilo de visualización n}$${\ estilo de visualización m}$

Ejemplo DFA. Si está en estado , muestra el mismo comportamiento para cada cadena de entrada que en estado o en estado . Del mismo modo, los estados y no son distinguibles. El DFA no tiene estados inalcanzables.${\ estilo de visualización c}$${\ estilo de visualización d}$${\ estilo de visualización e}$${\ estilo de visualización a}$${\ estilo de visualización b}$

DFA mínimo equivalente. Los estados no distinguibles se han fusionado en uno solo.