DFA-minimering
DFA-minimering är konstruktionen av en ekvivalent DFA baserad på en deterministisk finit automat (DFA) som har minsta möjliga antal tillstånd.
Minsta DFA
För alla vanliga språk finns det en minimal DFA som accepterar det, det vill säga en DFA med minsta möjliga antal tillstånd. En sådan automat är unik upp till isomorfism.
Algoritmer
Hopcrofts algoritm
Brzozowskis algoritm
Låt - DKA. Beteckna med den inverterade automaten . Beteckna med den deterministiska automat som erhålls från proceduren för att konstruera delmängder. Följande resultat håller [1] :
|
Låt maskinen känna igen språket . Då kan minsta DFA för språket hittas som |
Se även
Anteckningar
- ↑ Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Dela och gå med för att minimera: Brzozowskis algoritm . odefinierad (2002). Hämtad 27 juli 2019. Arkiverad från originalet 27 juli 2019.
Litteratur
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduktion till automatteori, språk och beräkningar, 2:a upplagan // ACM SIGACT News. - 2001-03-01. - T. 32 , nej. 1 . - S. 60 . — ISSN 0163-5700 . doi : 10.1145 / 568438.568455 .
Länkar
- Brzhozovskys algoritm // Wikisummary of ITMO University
- DFA-minimering, Hopcrofts algoritm (komplexitet O(n log n)) // Wikisummary of ITMO University
| Formella språk och formella grammatiker | |
|---|---|
| Allmänna begrepp | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 |
|
| analysera | |