Minimalizace DFA
Minimalizace DFA je konstrukce ekvivalentního DFA založeného na deterministickém konečném automatu (DFA), který má nejmenší možný počet stavů.
Minimální DFA
Pro každý běžný jazyk existuje minimální DFA , která jej přijímá, tj. DFA s co nejmenším počtem stavů. Takový automat je jedinečný až do izomorfismu.
Algoritmy
Hopcroftův algoritmus
Brzozowskiho algoritmus
Nechat - DKA. Označujeme obráceným automatem . Označme deterministickým automatem získaným postupem pro konstrukci podmnožin. Platí následující výsledek [1] :
|
Nechte stroj rozpoznat jazyk . Poté lze minimální DFA pro daný jazyk nalézt jako |
Viz také
Poznámky
- ↑ Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Rozdělit a spojit pro minimalizaci: Brzozowskiho algoritmus . nedefinováno (2002). Získáno 27. července 2019. Archivováno z originálu dne 27. července 2019.
Literatura
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Úvod do teorie automatů, jazyků a počítání, 2. vydání // ACM SIGACT News. - 2001-03-01. - T. 32 , č.p. 1 . - S. 60 . — ISSN 0163-5700 . doi : 10.1145 / 568438.568455 .
Odkazy
- Brzhozovského algoritmus // Wikisummary of ITMO University
- Minimalizace DFA, Hopcroftův algoritmus (složitost O(n log n)) // Wikisummary of ITMO University
| Formální jazyky a formální gramatiky | |
|---|---|
| Obecné pojmy | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 | |
| rozebrat | |