DFA minimering
DFA-minimering er konstruktionen af en ækvivalent DFA baseret på en deterministisk endelig automat (DFA), der har det mindst mulige antal tilstande.
Minimum DFA
For ethvert almindeligt sprog er der en minimal DFA , der accepterer det, det vil sige en DFA med det færrest mulige antal stater. En sådan automat er unik op til isomorfi.
Algoritmer
Hopcrofts algoritme
Brzozowskis algoritme
Lad - DKA. Betegnes med den omvendte automat . Betegn ved den deterministiske automat opnået fra proceduren til konstruktion af delmængder. Følgende resultat holder [1] :
|
Lad maskinen genkende sproget . Så kan minimum DFA for sproget findes som |
Se også
Noter
- ↑ Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Split og join for at minimere: Brzozowskis algoritme . udefineret (2002). Hentet 27. juli 2019. Arkiveret fra originalen 27. juli 2019.
Litteratur
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduktion til automatteori, sprog og beregninger, 2. udgave // ACM SIGACT News. - 2001-03-01. - T. 32 , no. 1 . - S. 60 . — ISSN 0163-5700 . doi : 10.1145 / 568438.568455 .
Links
- Brzhozovskys algoritme // Wikisummary of ITMO University
- DFA-minimering, Hopcrofts algoritme (kompleksitet O(n log n)) // Wikisummary of ITMO University
| Formelle sprog og formelle grammatikker | |
|---|---|
| Generelle begreber | |
| Type 0 | |
| Type 1 |
|
| Type 2 | |
| Type 3 |
|
| parsing | |