Az automata minimális formája

A minimális automata  olyan automata, amelynek a lehető legkevesebb állapota van, és egy adott kimeneti függvényt valósít meg. Az automata minimalizálásának feladata a minimális formájának megtalálására redukálódik. Egy tetszőleges véges automatához egy ekvivalens véges, a legkisebb állapotú automata is felépíthető [1] .

Felépítési elv

Az S automata minimális alakja (jelezve Š ) az automataelméletben egy ň állapotú automata, amely a {σ 1 ..σ ň } halmazt alkotja . Az S - ből származó minimális automata a következőképpen épül fel. Az S és Š automaták karakterisztikus függvényeit rendre g s , g z és g' s , g' z jelöli. Aztán ha , akkor .

Így az Š ezen feltétel szerinti megkonstruálásakor nem merül fel bizonytalanság.

A minimális automata megtalálásának algoritmusát Aufenkamp és Hohn javasolta. Megmutatták, hogy a minimális automata megtalálásához meg kell találni az S automata P i partícióit 1, 2, ..., k, (k + 1) osztályokba  - egymással ekvivalens állapotokba, amíg a néhány (k + 1 ) lépésből nem derül ki, hogy P k = P k+1 . Így a P k partíció megadja az S automata állapotainak összes ekvivalenciaosztályát . A Σ l ekvivalenciaosztályba tartozó összes S állapothoz hozzárendelhetünk általános jelölést, például σ l . Így az Š automatát az S automatából úgy kapjuk meg, hogy az azonosan jelölt állapotokat egy állapotba "kombináljuk". Az unió végrehajtásának módjai alapvetően attól függnek, hogy az automatát táblázatként, grafikonként vagy mátrixként definiáljuk.

A minimális űrlap megszerzésének módszerei

Jump table

Ha az S automatának egy átmeneti táblája és egy ekvivalens Σ 1 ..Σ ň partíciója adott, akkor az Š átmeneti tábla a következőképpen szerkeszthető:

1. Cserélje ki az S táblában az egyes állapotok jelölését annak az osztálynak a jelölésével, amelyhez ez az állapot tartozik.
2. A főoszlop celláiban található minden azonos jelölésű sorcsoportból egy kivételével húzza ki az összes sort.

Az eredményül kapott táblázat a Š átmeneti tábla .

Átmeneti gráf

Adott az S automatának egy átmeneti gráf ( állapotdiagram ) és egy ekvivalens Σ 1 ..Σ ň partíció , akkor az Š átmeneti gráf a következőképpen szerkeszthető:

1. Cserélje le az S átmeneti gráf minden állapotának jelölését annak az osztálynak a jelölésével, amelyhez ez az állapot tartozik.
2. Egyesítse az összes azonos címkével ellátott állapotot (a grafikoníveket "rugalmas linkekként" kezelje), és az egyesített állapotokat egyetlen állapotként jelenítse meg, közös címkével.
3. Minden ívcsoportból, amelynek közös kezdeti és közös végső állapota van, egy kivételével törölje az összeset.

Az eredményül kapott gráf az Š gráf lesz .

Átmeneti mátrix

Adott az S automatának egy átmeneti mátrixa és egy Σ 1 ..Σ ň ekvivalens partíciója , akkor az Š átmeneti mátrix a következőképpen szerkeszthető:

1. Végezzen szimmetrikus permutációt és szimmetrikus partíciót [S] úgy, hogy a sorok (és oszlopok) az S ekvivalencia osztályok szerint legyenek csoportosítva (ugyanaz a mátrix a mátrix-ekvivalens felosztás módszerével is előállítható).
2. Cserélje le az ekvivalenciaosztályt képviselő csoportok sor- és oszlopjelöléseit az adott osztály egyetlen jelölésére.
3. Cserélje le az osztott mátrix minden egyes almátrixát egyetlen cellára, amely tartalmazza az összes bemeneti-kimeneti párt, amely az almátrix bármely sorában található (az ilyen almátrixok minden sora ugyanazt a bemeneti-kimeneti párokat tartalmazza).

Az eredményül kapott mátrix a Š átmeneti mátrix .

Minimális űrlaptulajdonságok

Ha Š az S automata minimális alakja , akkor:

1. Az Š az egyetlen minimális forma az állapotok jelöléséig
2. Š=S
3. Nincs két egyenértékű Š állapot
4. Nincs S -nek megfelelő és Š -nél kisebb (kevesebb állapotú) automata .

Jegyzetek

1. ↑ Discrete Mathematics, 2006 , p. 534.

Irodalom

• Gill A. Bevezetés a véges automaták elméletébe. M.: Nauka, 1966. - 272 p.
• Belousov A. I., Tkachev S. B. Diszkrét matematika. - M. : MGTU, 2006. - 744 p. — ISBN 5-7038-2886-4 .