Minimización de DFA
La minimización de DFA es la construcción de un DFA equivalente basado en un autómata finito determinista (DFA) que tiene el menor número posible de estados.
Mínimo DFA
Para cualquier lenguaje regular, existe un DFA mínimo que lo acepta, es decir, un DFA con el menor número posible de estados. Tal autómata es único hasta el isomorfismo.
Algoritmos
Algoritmo de Hopcroft
Algoritmo de Brzozowski
Vamos - CAD. Denote por el autómata invertido . Denote por el autómata determinista obtenido del procedimiento para construir subconjuntos. El siguiente resultado tiene [1] :
|
Deje que la máquina reconozca el idioma . Luego, el DFA mínimo para el idioma se puede encontrar como |
Véase también
Notas
- ↑ Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Dividir y unir para minimizar: algoritmo de Brzozowski . indefinido (2002). Consultado el 27 de julio de 2019. Archivado desde el original el 27 de julio de 2019.
Literatura
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación, 2ª edición // ACM SIGACT News. - 2001-03-01. - T. 32 , n. 1 . - S. 60 . — ISSN 0163-5700 . doi : 10.1145 / 568438.568455 .
Enlaces
- Algoritmo de Brzhozovsky // Wikisummary de la Universidad ITMO
- Minimización de DFA, algoritmo de Hopcroft (complejidad O(n log n)) // Wikisummary de la Universidad ITMO
| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| tipo 3 |
|
| analizando | |