Minimizacija determinističnega končnega avtomata

Teorija

Postopek

0. korak

• nardimo spodnjo trikotno tabelo. Vodoravno spodaj napišemo stanja, brez zadnjega. Navpično pa napišemo stanja brez prvega

1. korak

• izločimo nedosegljiva/odvečna stanja

2. korak

• z 0 označimo polje, katerih pari so v kombinaciji končno-nekončno stanje

3. korak

• za vsa prazna polja preverimo v kolikih korakih pridemo v kombinacijo končno-nekončno stanje; vedno gledamo prekode po istem vhodu

4. korak

• vsak polja, ki so ostala prazna lahko združimo

Glej tudi

• Izrek Myhill-Nerode

Zunanje povezave

• http://www.cs.ucr.edu/~marek/TEACHING/CS150_W06/NOTES/MINIMIZE_DFA/minimize_dfa.pdf
• http://www.informatik.uni-bremen.de/agbs/lehre/ss05/pi2/hintergrund/minimize_dfa.pdf