Minimální forma automatu

Minimální automat  je automat, který má co nejmenší počet stavů a ​​implementuje danou výstupní funkci. Úkol minimalizace automatu se redukuje na nalezení jeho minimální podoby. Pro libovolný konečný automat lze sestavit ekvivalentní konečný automat s nejmenším počtem stavů [1] .

Princip konstrukce

Minimální formou automatu S (označovaného v teorii automatů Š ) je automat s ň stavy tvořícími množinu {σ 1 ..σ ň } . Minimální automat z S je konstruován následovně. Charakteristické funkce automatů S a Š se označují g s , g z resp . g' s , g' z . Pak když , tak .

Při konstrukci Š podle této podmínky tedy nevzniká žádná nejistota.

Algoritmus pro nalezení minimálního automatu navrhli Aufenkamp a Hohn. Ukázali, že pro nalezení minimálního automatu je nutné najít po sobě následující oddíly P i automatu S do tříd 1, 2, ..., k, (k + 1)  - stavy navzájem ekvivalentní, dokud v nějaký (k + 1 ) krok neukáže, že P k = P k+1 . Rozdělení P k tedy dává všechny třídy ekvivalence stavů automatu S . Všem stavům S patřícím do třídy ekvivalence Σ l lze přiřadit obecné označení, například σ l . Automat Š se tedy získá z automatu S „sloučením“ shodně označených stavů do jednoho stavu. Způsoby, kterými se toto sjednocení provádí, závisí v podstatě na tom, zda je automat definován jako tabulka, graf nebo matice.

Metody pro získání minimálního formuláře

Tabulka skoků

Pokud je dána přechodová tabulka a ekvivalentní oddíl Σ 1 ..Σ ň automatu S , pak přechodovou tabulku Š lze sestavit následovně:

1. Označení každého státu v tabulce S nahraďte označením třídy, do které tento stav patří.
2. Z každé skupiny řádků se stejným označením v buňkách hlavního sloupce škrtněte všechny řádky kromě jednoho.

Výsledná tabulka je přechodová tabulka Š .

Přechodový graf

Je -li dán přechodový graf ( stavový diagram ) a ekvivalentní rozdělení Σ 1 ..Σ ň automatu S , pak lze přechodový graf Š sestavit takto:

1. Označení každého stavu v přechodovém grafu S nahraďte označením třídy, do které tento stav patří.
2. Sloučit všechny identicky označené stavy (oblouky grafu považovat za „flexibilní odkazy“) a reprezentovat sloučené stavy jako jeden stav se společným štítkem.
3. Z každé skupiny oblouků, které mají společný počáteční a společný konečný stav, odstraňte všechny kromě jednoho.

Výsledným grafem bude Š graf .

Přechodová matice

Pokud je dána přechodová matice a ekvivalentní rozdělení Σ 1 ..Σ ň automatu S , pak lze přechodovou matici Š sestavit následovně:

1. Proveďte symetrickou permutaci a symetrické rozdělení [S] tak, aby řádky (a sloupce) byly seskupeny podle tříd ekvivalence S (stejnou matici lze získat metodou maticového ekvivalentního rozdělení).
2. Nahraďte všechna označení řádků (a sloupců) každé skupiny představující třídu ekvivalence jediným označením této třídy.
3. Nahraďte každou podmatici v dělené matici jednou buňkou obsahující všechny vstupně-výstupní páry, které jsou v libovolném řádku této podmatice (všechny řádky v jakékoli takové podmatici obsahují stejnou sadu vstupně-výstupních párů).

Výsledná matice je přechodová matice Š .

Minimální vlastnosti formuláře

Pokud je Š minimální forma automatu S , pak:

1. Š je jedinou minimální formou až do zápisu stavů
2. Š=S
3. Žádné dva stavy Š nejsou rovnocenné
4. Neexistuje žádný automat ekvivalentní S a menší (s méně stavy) než Š .

Poznámky

1. ↑ Diskrétní matematika, 2006 , str. 534.

Literatura

• Gill A. Úvod do teorie konečných automatů. M.: Nauka, 1966. - 272 s.
• Belousov A. I., Tkachev S. B. Diskrétní matematika. - M. : MGTU, 2006. - 744 s. — ISBN 5-7038-2886-4 .