Teória automatov, konečné automaty
Štruktúra, dizajn, princíp činnosti rôznych strojov sú do značnej miery určené ich funkčným účelom. Rozlišujte stroje technologické, dopravné, výpočtové, vojenské a iné. Celé automatické komplexy určené na vykonávanie zložitých technologických procesov sú široko zavedené v rôznych priemyselných odvetviach. Sú navrhnuté a skonštruované automaty, ktoré vykonávajú rôzne logické funkcie (logické stroje).
Teória automatov — kybernetická sekcia, ktoré vznikli pod vplyvom požiadaviek techniky číslicových počítačov a riadiacich strojov. Diskrétne automaty študované v teórii automatov sú abstraktné modely reálnych systémov (technických aj biologických), ktoré spracúvajú diskrétne (digitálne) informácie v diskrétnych časových krokoch.
Teória automatov je založená na presných matematických konceptoch, ktoré formalizujú intuitívne predstavy o fungovaní (správaní) automatu a o jeho štruktúre (vnútornej štruktúre).
Informačná transformácia sa v tomto prípade vždy chápe ako operácia, ktorá transformuje vstupné sekvencie zložené z písmen zo vstupnej abecedy na výstupné sekvencie zložené z písmen výstupnej abecedy.
Široko používaný je aparát matematickej logiky, algebry, teórie pravdepodobnosti, kombinatoriky a teórie grafov.
Narastal problém s teóriou automatov v niektorých jej častiach (štrukturálna teória automatov). z teórie relé-kontaktných obvodov, ktorá sa začala formovať koncom 30. rokov 20. storočia. vrátane metódy logickej algebry.
V štrukturálnej teórii automatov sa študujú rôzne typy schém, ktoré majú opísať, ako sa vytvára zložitý automat z jednoduchších komponentov (prvkov) správne zapojených v systéme.
Iný smer, nazývaný abstraktná teória automatov, študuje správanie automatov (teda povahu nimi vykonávanej transformácie informácií), pričom abstrahuje od špecifík ich vnútornej štruktúry, a vznikol v 50. rokoch 20. storočia.
V rámci abstraktnej teórie automatov je obsah pojmov „automat“ a „stroj“ v podstate vyčerpaný štandardným popisom transformácie informácie, ktorú vykonáva automat. Takáto transformácia môže byť deterministická, ale môže mať aj pravdepodobnostný charakter.
Najviac študované sú deterministické stroje (automaty), medzi ktoré patria konečné automaty — hlavný predmet štúdia v teórii automatov.
Konečný automat je charakterizovaný obmedzeným množstvom pamäte (počet vnútorných stavov) a je definovaný pomocou prechodovej funkcie.S trochou rozumnej idealizácie možno všetky moderné matematické stroje a dokonca aj mozog z hľadiska ich fungovania považovať za konečné automaty.
Pojmy "sekvenčný stroj", "Millyho automat", "Mooreov automat" sa v literatúre používajú (a nie jednotne všetkými autormi) ako synonymá pojmu "konečný automat" alebo na zdôraznenie určitých znakov v prechodových funkciách konečného automatu. automat.
Automat s neobmedzenou pamäťou je Turingov stroj schopný vykonávať (potenciálne) akúkoľvek efektívnu transformáciu informácií. Pojem „Turingov stroj“ vznikol skôr ako pojem „konečného stroja“ a študuje sa hlavne v teórii algoritmov.
Teória abstraktných automatov úzko súvisí so známymi algebraickými teóriami, napríklad teóriou pologrup. Z aplikovaného hľadiska sú zaujímavé výsledky charakterizujúce transformáciu informácií v automate z hľadiska veľkosti pamäte.
Ide napríklad o problémy s experimentmi na automatoch (práce E.F. Moora a pod.), kde sa z výsledkov tzv. experimenty.
Ďalšou úlohou je vypočítať periódy výstupných sekvencií, na základe dostupných informácií o veľkosti pamäte automatu a periódy vstupných sekvencií.
Veľký význam má vývoj metód na minimalizáciu pamäte konečných automatov a štúdium ich správania v náhodných prostrediach.
V teórii abstraktných automatov je problém syntézy nasledujúci.V zmysle nejakého jasne formalizovaného jazyka sú podmienky napísané pre správanie sa navrhnutého automatu (pre udalosť reprezentovanú v automate). V tomto prípade je potrebné vyvinúť metódy, ktoré podľa každej písomnej podmienky:
1) zistiť, či existuje taký stavový automat, že ním transformované informácie spĺňajú túto podmienku;
2) ak áno, potom sa skonštruujú prechodové funkcie takéhoto konečného automatu alebo sa odhadne veľkosť jeho pamäte.
Riešenie úlohy syntézy v takejto formulácii predpokladá predbežné vytvorenie vhodného jazyka na zaznamenávanie prevádzkových podmienok automatu s vhodnými algoritmami na prechod zo záznamu na tranzitívne funkcie.
V štruktúrnej teórii automatov problém syntézy spočíva v zostrojení reťazca prvkov daného typu, ktorý realizuje konečný automat daný jeho prechodovými funkciami. V tomto prípade zvyčajne uvádzajú nejaké kritérium optimality (napríklad minimálny počet prvkov) a snažia sa získať optimálnu schému.
Ako sa neskôr ukázalo, znamená to, že niektoré metódy a koncepty vyvinuté skôr v súvislosti s reléovými kontaktnými obvodmi sú použiteľné pre obvody iného typu.
V súvislosti s rozvojom elektronických technológií sú najrozšírenejšie schémy funkčných prvkov (logické siete). Špeciálnym prípadom logických sietí sú abstraktné neurónové siete, ktorých prvky sa nazývajú neuróny.
Bolo vyvinutých mnoho metód syntézy v závislosti od typu obvodov a transformácie informácií, pre ktoré sú určené (Syntéza reléových zariadení).
Pozri -Minimalizácia kombinačných obvodov, Carnotove mapy, syntéza obvodov
Konečný automat — matematický model riadiaceho systému s pevnou veľkosťou pamäte (ktorá sa počas prevádzky nedá zväčšiť).
Koncept konečného automatu je matematická abstrakcia, ktorá charakterizuje všeobecné charakteristiky súboru riadiacich systémov (napríklad viacslučkové reléové zariadenie). Všetky takéto systémy majú spoločné črty, ktoré je prirodzené akceptovať ako definíciu konečného automatu.
Každý dokončený automat má vstup vystavený vonkajším vplyvom a vnútorným prvkom. Pre vstupné aj vnútorné prvky existuje pevný počet diskrétnych stavov, ktoré môžu prijať.
Zmena stavov vstupných a vnútorných prvkov nastáva v diskrétnych časových okamihoch, pričom intervaly medzi nimi sa nazývajú kliešte. Vnútorný stav (stav vnútorných častí) na konci pásky je určený výlučne vnútorným stavom a stavom vstupu na začiatku pásky.
Všetky ostatné definície konečného automatu možno zredukovať na túto charakteristiku, najmä definície, ktoré predpokladajú, že konečný automat má výstup, ktorý závisí od vnútorného stavu automatu v danom čase.
Z hľadiska takejto charakteristiky je charakter jeho vstupov a vnútorných stavov pre popis úplného automatu irelevantný. Namiesto vstupov a stavov sa stačí pozrieť na ich čísla v náhodnom číslovaní.
Stavový automat sa nastaví, ak je špecifikovaná závislosť jeho čísla vnútorného stavu od predchádzajúceho čísla vnútorného stavu a predchádzajúceho čísla stavu vstupu. Takáto úloha môže byť vo forme finálového stola.
Ďalším bežným spôsobom, ako definovať úplný automat, je konštrukcia tzv prechodové diagramy. Vstupné stavy sa často nazývajú jednoducho vstupy a vnútorné stavy sú jednoducho stavy.
Konečný automat môže byť modelom technických zariadení aj niektorých biologických systémov. Automaty prvého typu sú napríklad reléové zariadenia a rôzne elektronické počítače vr. programovateľné logické ovládače.
V prípade reléového zariadenia zohrávajú úlohu vstupných stavov kombinácie stavov citlivých prvkov reléového zariadenia (každá kombinácia takýchto stavov je «komplexný stav», charakterizovaný indikáciou všetkých citlivých prvkov reléového zariadenia). tieto diskrétne stavy, ktoré majú v danom momente). Podobne ako vnútorné stavy pôsobia kombinácie stavov medzičlánkov reléového zariadenia.
Programovateľný logický radič (PLC) je príkladom reléového akčného zariadenia, ktoré možno nazvať samostatným stavovým automatom.
V skutočnosti, keď už bol program zadaný do PLC a regulátor začal počítať, nie je vystavený vonkajším vplyvom a každý nasledujúci stav je úplne určený jeho predchádzajúcim stavom. Môžeme predpokladať, že vstup má rovnaký stav v každom hodinovom cykle.
Naopak, každý konečný automat, ktorý má jediný možný vstupný stav, sa prirodzene nazýva autonómny, pretože v tomto prípade vonkajšie prostredie nenesie žiadne informácie, ktoré by riadili jeho správanie.
Pozri tiež:
Využitie mikroprocesorových systémov v elektrotechnike na príklade využitia PLC