Forma minimă de automat

Un automat minim  este un automat care are cel mai mic număr posibil de stări și implementează o funcție de ieșire dată. Sarcina de a minimiza un automat se reduce la găsirea formei sale minime. Pentru un automat finit arbitrar, se poate construi un automat finit echivalent cu cel mai mic număr de stări [1] .

Principiul construcției

Forma minimă a unui automat S (notat ca Š ) în teoria automatelor este un automat cu ň stări care formează mulțimea {σ 1 ..σ ň } . Automatul minim din S este construit după cum urmează. Funcţiile caracteristice ale automatelor S şi Š se notează cu g s , g z şi respectiv g' s , g' z . Atunci dacă , atunci .

Astfel, atunci când se construiește Š în conformitate cu această condiție, nu apare nicio incertitudine.

Algoritmul pentru găsirea automatului minim a fost propus de Aufenkamp și Hohn. Ei au arătat că pentru a găsi automatul minim este necesar să se găsească partiții succesive P i ale automatului S în clasele 1, 2, ..., k, (k + 1)  - stări echivalente între ele, până la un pas (k + 1 ) nu rezultă că P k = P k+1 . Astfel, partiția P k dă toate clasele de echivalență de stări ale automatului S . Tuturor stărilor S aparținând clasei de echivalență Σ l li se poate atribui o denumire generală, de exemplu, σ l . Astfel, automatul Š este obținut din automatul S prin „combinarea” stărilor etichetate identic într-o singură stare. Modalitățile în care se realizează această unire depind în esență de dacă automatul este definit ca un tabel, un grafic sau o matrice.

Metode de obținere a formei minime

Jump table

Dacă sunt date un tabel de tranziție și o partiție echivalentă Σ 1 ..Σ ň a automatului S , atunci tabelul de tranziție Š poate fi construit după cum urmează:

1. Înlocuiți denumirea fiecărei stări din tabelul S cu denumirea clasei căreia îi aparține această stare.
2. Din fiecare grup de linii cu aceleași denumiri în celulele coloanei principale, tăiați toate liniile, cu excepția uneia.

Tabelul rezultat este tabelul de tranziție Š .

Graficul de tranziție

Având în vedere un grafic de tranziție ( diagrama de stări ) și o partiție echivalentă Σ 1 ..Σ ň a automatului S , atunci graficul de tranziție Š poate fi construit după cum urmează:

1. Înlocuiți denumirea fiecărei stări din graficul de tranziție S cu denumirea clasei căreia îi aparține această stare.
2. Îmbinați toate stările etichetate identic (tratând arcele graficului ca „legături flexibile”) și reprezentați stările îmbinate ca o singură stare cu o etichetă comună.
3. Din fiecare grup de arce care au o stare comună inițială și finală comună, ștergeți toate, cu excepția unuia.

Graficul rezultat va fi graficul Š .

Matricea de tranziție

Având în vedere o matrice de tranziție și o partiție echivalentă Σ 1 ..Σ ň a automatului S , atunci matricea de tranziție Š poate fi construită după cum urmează:

1. Efectuați o permutare simetrică și o partiție simetrică [S] astfel încât rândurile (și coloanele) să fie grupate în funcție de clasele de echivalență S (aceeași matrice poate fi obținută folosind metoda partiției echivalente a matricei).
2. Înlocuiți toate denumirile rândurilor (și coloanelor) ale fiecărui grup care reprezintă o clasă de echivalență cu o singură desemnare a acelei clase.
3. Înlocuiți fiecare submatrice din matricea divizată cu o singură celulă care conține toate perechile intrare-ieșire care se află în orice rând al acestei submatrici (toate rândurile din orice astfel de submatrice conțin același set de perechi intrare-ieșire).

Matricea rezultată este matricea de tranziție Š .

Proprietăți minime ale formularului

Dacă Š este forma minimă a automatului S , atunci:

1. Š este singura formă minimă până la notarea stărilor
2. Š=S
3. Nu există două stări Š echivalente
4. Nu există un automat echivalent cu S și mai mic (cu mai puține stări) decât Š .

Note

1. ↑ Matematică discretă, 2006 , p. 534.

Literatură

• Gill A. Introducere în teoria automatelor finite. M.: Nauka, 1966. - 272 p.
• Belousov A. I., Tkachev S. B. Matematică discretă. - M. : MGTU, 2006. - 744 p. — ISBN 5-7038-2886-4 .