DFA-minimointi

DFA-minimointi  on vastaavan DFA:n rakentaminen, joka perustuu deterministiseen äärelliseen automaattiin (DFA), jolla on pienin mahdollinen määrä tiloja.

Minimi DFA

Jokaiselle tavalliselle kielelle on olemassa pienin DFA , joka hyväksyy sen, eli DFA, jossa on mahdollisimman vähän tilaa. Tällainen automaatti on ainutlaatuinen isomorfismiin asti.

Algoritmit

Hopcroftin algoritmi

Brzozowskin algoritmi

Anna  - DKA. Merkitään käänteisellä automaatilla . Merkitään deterministisellä automaatilla, joka saadaan osajoukkojen konstruointimenettelystä. Seuraava tulos pätee [1] :

Katso myös

• valtion kone
• Automaattien minimimuoto
• Suffiksiautomaatti

Muistiinpanot

1. ↑ Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Jaa ja liitä minimointia varten: Brzozowskin  algoritmi . määrittelemätön (2002). Haettu 27. heinäkuuta 2019. Arkistoitu alkuperäisestä 27. heinäkuuta 2019.

Kirjallisuus

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen, 2. painos  // ACM SIGACT News. - 01-03-2001. - T. 32 , no. 1 . - S. 60 . — ISSN 0163-5700 . doi : 10.1145 / 568438.568455 .

Linkit

• Brzhozovskin algoritmi // ITMO-yliopiston Wikiyhteenveto
• DFA-minimointi, Hopcroftin algoritmi (monimutkaisuus O(n log n)) // ITMO-yliopiston wikiyhteenveto