Automaattien minimimuoto

Minimaaliautomaatti  on automaatti, jolla on mahdollisimman vähän tiloja ja joka toteuttaa tietyn lähtöfunktion. Automaattien minimointitehtävä rajoittuu sen minimimuodon löytämiseen. Mielivaltaiselle äärelliselle automaatille voidaan rakentaa vastaava äärellinen automaatti, jolla on pienin määrä tiloja [1] .

Rakennusperiaate

Automaattiteoriassa automaatin S minimimuoto (merkitty Š ) on automaatti, jonka ň - tilat muodostavat joukon {σ 1 ..σ ň } . Minimaaliautomaatti S :stä on rakennettu seuraavasti. Automaattien S ja Š ominaisfunktiot on merkitty g s , g z ja g' s , g' z vastaavasti. Sitten jos , niin .

Näin ollen kun rakennetaan Š tämän ehdon mukaan, ei synny epävarmuutta.

Algoritmia minimiautomaatin löytämiseksi ehdottivat Aufenkamp ja Hohn. He osoittivat, että minimiautomaatin löytämiseksi on tarpeen löytää automaatin S peräkkäiset osiot P i luokkiin 1, 2, ..., k, (k + 1)  - toisiaan vastaaviin tiloihin, kunnes klo. jostain (k + 1 ) askeleesta ei käy ilmi, että P k = P k+1 . Siten osio P k antaa kaikki automaatin S tilojen ekvivalenssiluokat . Kaikille ekvivalenssiluokkaan Σ l kuuluville tiloille S voidaan antaa yleinen nimitys, esimerkiksi σ l . Automaatti Š saadaan siis automaatista S "yhdistämällä" identtisesti merkittyjä tiloja yhdeksi tilaan. Tapa, jolla tämä yhdistäminen suoritetaan, riippuu olennaisesti siitä, onko automaatti määritelty taulukoksi, kaavioksi vai matriisiksi.

Menetelmät vähimmäislomakkeen saamiseksi

Hyppypöytä

Jos on annettu automaatin S siirtymätaulukko ja vastaava osio Σ 1 ..Σ ň , niin siirtymätaulukko Š voidaan muodostaa seuraavasti:

1. Korvaa kunkin tilan nimitys taulukossa S sen luokan tunnuksella, johon tämä tila kuuluu.
2. Jokaisesta pääsarakkeen solujen riviryhmästä, jolla on sama nimitys, ylitä kaikki rivit yhtä lukuun ottamatta.

Tuloksena oleva taulukko on siirtymätaulukko Š .

Siirtymäkaavio

Kun on annettu automaatin S siirtymägraafi ( tilakaavio ) ja vastaava osio Σ 1 ..Σ ň , niin siirtymägraafi Š voidaan muodostaa seuraavasti:

1. Korvaa kunkin tilan nimi siirtymägraafissa S sen luokan tunnuksella, johon tämä tila kuuluu.
2. Yhdistä kaikki samalla tavalla merkityt tilat (käsittele kaavion kaaria "joustavina linkkeinä") ja edusta yhdistetyt tilat yhtenä tilana, jolla on yhteinen nimiö.
3. Poista jokaisesta kaariryhmästä, jolla on yhteinen alku- ja yhteinen lopputila, kaikki yhtä lukuun ottamatta.

Tuloksena oleva graafi on Š -kuvaaja .

Siirtymämatriisi

Kun on annettu automaatin S siirtymämatriisi ja vastaava osio Σ 1 ..Σ ň , niin siirtymämatriisi Š voidaan muodostaa seuraavasti:

1. Suorita symmetrinen permutaatio ja symmetrinen osio [S] siten, että rivit (ja sarakkeet) ryhmitellään ekvivalenssiluokkien S mukaan (sama matriisi voidaan saada matriisiekvivalenttiosiomenetelmällä).
2. Korvaa jokaisen vastaavuusluokkaa edustavan ryhmän rivien (ja sarakkeen) nimet yhdellä kyseisen luokan tunnuksella.
3. Korvaa jokainen jaetun matriisin alimatriisi yhdellä solulla, joka sisältää kaikki tulo-lähtö-parit, jotka ovat tämän alimatriisin millä tahansa rivillä (kaikki rivit missä tahansa tällaisessa alimatriisissa sisältävät saman joukon tulo-lähtöpareja).

Tuloksena oleva matriisi on siirtymämatriisi Š .

Vähimmäislomakkeen ominaisuudet

Jos Š on automaattin S minimimuoto , niin:

1. Š on ainoa minimaalinen muoto tilojen merkintään asti
2. Š=S
3. Ei kahta yhtäläistä tilaa Š
4. Ei ole olemassa S :tä vastaavaa ja pienempiä (vähemmän tiloja) kuin Š :tä .

Muistiinpanot

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

Kirjallisuus

• Gill A. Johdatus äärellisten automaattien teoriaan. M.: Nauka, 1966. - 272 s.
• Belousov A. I., Tkachev S. B. Diskreetti matematiikka. - M .: MGTU, 2006. - 744 s. — ISBN 5-7038-2886-4 .