Minimal form for automat

En minimal automat  er en automat, der har det mindst mulige antal tilstande og implementerer en given outputfunktion. Opgaven med at minimere en automat er reduceret til at finde dens minimumsform. For en vilkårlig finit automat kan der bygges en ækvivalent finit automat med det mindste antal tilstande [1] .

Konstruktionsprincip

Den minimale form af en automat S (betegnet som Š ) i automatteori er en automat med ň tilstande, der danner mængden {σ 1 ..σ ň } . Den minimale automat fra S er konstrueret som følger. De karakteristiske funktioner for automaterne S og Š er angivet med henholdsvis g s , g z og g' s , g' z . Så hvis , så .

Når man konstruerer Š efter denne betingelse, opstår der således ingen usikkerhed.

Algoritmen til at finde minimumsautomaten blev foreslået af Aufenkamp og Hohn. De viste, at for at finde den minimale automat, er det nødvendigt at finde successive partitioner Pi af automaten S i klasserne 1, 2, ..., k, (k + 1)  - tilstande svarende til hinanden, indtil kl. nogle (k + 1) trin viser sig ikke, at Pk = Pk +1 . Således giver partitionen Pk alle ækvivalensklasser af tilstande af automaten S. Alle tilstande S , der tilhører ækvivalensklassen Σ l , kan tildeles en generel betegnelse, for eksempel σ l . Således opnås automaten Š fra automaten S ved at "kombinere" identisk mærkede tilstande til en tilstand. Måden, hvorpå denne forening udføres, afhænger i det væsentlige af, om automaten er defineret som en tabel, en graf eller en matrix.

Metoder til at opnå minimumsformularen

Spring tabel

Hvis der er givet en overgangstabel og en ækvivalent partition Σ 1 ..Σ ň for automaten S , kan overgangstabellen Š konstrueres som følger:

1. Erstat betegnelsen for hver tilstand i tabellen S med betegnelsen for den klasse, som denne tilstand tilhører.
2. Fra hver gruppe af linjer med de samme betegnelser i cellerne i hovedsøjlen krydses alle linjer ud på nær én.

Den resulterende tabel er overgangstabellen Š .

Overgangsgraf

Givet en overgangsgraf ( tilstandsdiagram ) og en ækvivalent partition Σ 1 ..Σ ň af automaten S , så kan overgangsgrafen Š konstrueres som følger:

1. Erstat betegnelsen for hver tilstand i overgangsgrafen S med betegnelsen for den klasse, som denne tilstand tilhører.
2. Flet alle identisk mærkede tilstande (behandl grafbuerne som "fleksible links") og repræsentere de flettede tilstande som en enkelt tilstand med en fælles etiket.
3. Fra hver gruppe af buer, der har en fælles indledende og fælles sluttilstand, skal du slette alle undtagen én.

Den resulterende graf vil være Š- grafen .

Overgangsmatrix

Givet en overgangsmatrix og en ækvivalent partition Σ 1 ..Σ ň af automaten S , så kan overgangsmatrixen Š konstrueres som følger:

1. Udfør en symmetrisk permutation og en symmetrisk partition [S] , således at rækkerne (og kolonnerne) er grupperet efter ækvivalensklasserne S (den samme matrix kan opnås ved hjælp af matrixækvivalent partitionsmetoden).
2. Erstat alle række- (og kolonne-)betegnelser for hver gruppe, der repræsenterer en ækvivalensklasse, med en enkelt betegnelse for den pågældende klasse.
3. Erstat hver submatrix i den opdelte matrix med en enkelt celle, der indeholder alle input-output-par, der er i en række af denne submatrix (alle rækker i en sådan submatrix indeholder det samme sæt input-output-par).

Den resulterende matrix er overgangsmatrixen Š .

Minimum Form Properties

Hvis Š er den minimale form af automaten S , så:

1. Š er den eneste minimale form op til notationen af ​​staterne
2. Š=S
3. Ikke to tilstande Š er ækvivalente
4. Der er ingen automat, der svarer til S og mindre (med færre tilstande) end Š .

Noter

1. ↑ Diskret matematik, 2006 , s. 534.

Litteratur

• Gill A. Introduktion til teorien om finite automater. M.: Nauka, 1966. - 272 s.
• Belousov A. I., Tkachev S. B. Diskret matematik. - M. : MGTU, 2006. - 744 s. — ISBN 5-7038-2886-4 .