Automaták elmélete, véges automaták
A különféle gépek felépítését, kialakítását, működési elvét nagyban meghatározza a funkcionális rendeltetése. Tegyen különbséget technológiai, közlekedési, számítástechnikai, katonai és egyéb gépek között. A komplex technológiai folyamatok végrehajtására tervezett teljes automata komplexumokat széles körben bevezetik a különböző iparágakban. Olyan automatákat terveznek és építenek, amelyek különféle logikai funkciókat látnak el (logikai gépek).
Az automaták elmélete — kibernetikai részleg, amely a digitális számítógépek és vezérlőgépek technológiájának követelményei hatására keletkezett. Az automataelméletben vizsgált diszkrét automaták valós rendszerek (műszaki és biológiai) elvont modelljei, amelyek diszkrét (digitális) információkat dolgoznak fel diszkrét időlépésekben.
Az automataelmélet precíz matematikai fogalmakon alapul, amelyek formalizálják az automata működésével (viselkedésével) és szerkezetével (belső szerkezetével) kapcsolatos intuitív elképzeléseket.
Ebben az esetben az információtranszformáció mindig olyan művelet alatt értendő, amely a bemeneti ábécé betűiből álló bemeneti sorozatokat a kimeneti ábécé betűiből álló kimeneti sorozatokká alakítja.
A matematikai logika, az algebra, a valószínűségszámítás, a kombinatorika és a gráfelmélet apparátusát széles körben használják.
Az automaták elméletével kapcsolatos probléma egyes részeiben (az automaták szerkezeti elmélete) egyre nőtt a reléérintkezős áramkörök elméletéből, amely az 1930-as évek végén kezdett formát ölteni. inkluzív a logikai algebra módszerei.
Az automaták szerkezetelméletében különböző típusú sémákat tanulmányoznak, amelyek célja, hogy leírják, hogyan jön létre egy összetett automata a rendszerben megfelelően összekapcsolt egyszerűbb komponensekből (elemekből).
Egy másik irány, amelyet az automaták elvont elméletének neveznek, az automaták viselkedését (vagyis az általuk végrehajtott információtranszformáció természetét) vizsgálja, miközben elvonatkoztat belső szerkezetük sajátosságaitól, és az 1950-es években keletkezett.
Az automaták elvont elméletének keretein belül az „automata” és a „gép” fogalmak tartalmát lényegében kimeríti az automata által végrehajtott információ-átalakítás standard leírása. Egy ilyen transzformáció lehet determinisztikus, de lehet valószínűségi jellegű is.
A legtöbbet tanulmányozott determinisztikus gépek (automaták), amelyek véges automatákat tartalmaznak, amelyek az automaták elméletének fő vizsgálati tárgyai.
Egy véges állapotú gépet korlátozott mennyiségű memória (a belső állapotok száma) jellemez, és egy átmeneti függvény segítségével határozzák meg.Némi ésszerű idealizálással minden modern matematikai gép, sőt működésük szempontjából az agy is véges automatának tekinthető.
A "szekvenciális gép", "Milly automata", "Moore automata" kifejezéseket a szakirodalom (és nem minden szerző egyöntetűen) a "véges automata" kifejezés szinonimájaként vagy a véges átmeneti függvényeinek bizonyos jellemzőinek hangsúlyozására használja. automata.
A korlátlan memóriával rendelkező automata egy olyan Turing-gép, amely (potenciálisan) bármilyen hatékony információtranszformációt képes végrehajtani. A "Turing-gép" fogalma korábban jelent meg, mint a "véges állapotú gép", és főként az algoritmusok elméletében tanulmányozzák.
Az absztrakt automata elmélet szorosan kapcsolódik a jól ismert algebrai elméletekhez, például a félcsoportelmélethez. Alkalmazotti szempontból érdekesek azok az eredmények, amelyek az automata információ-transzformációját a memória méretével jellemzik.
Ez a helyzet például az automatákon végzett kísérleteknél (E.F. Moore munkái stb.), ahol az automata átmeneti funkcióiról vagy a memóriájának kapacitásáról az automata eredményeiből nyerünk bizonyos információkat. kísérletek.
További feladat a kimeneti sorozatok periódusainak kiszámítása az automata memóriaméretéről és a bemeneti sorozatok periódusairól rendelkezésre álló információk alapján.
Nagyon fontos a véges állapotú gépek memóriájának minimalizálására és véletlenszerű környezetben való viselkedésük tanulmányozására szolgáló módszerek kidolgozása.
Az absztrakt automata elméletben a szintézis probléma a következő.Valamilyen egyértelműen formalizált nyelv tekintetében a feltételek a tervezett automata viselkedésére (az automatában ábrázolt eseményre) vannak írva. Ebben az esetben olyan módszereket kell kidolgozni, amelyek minden írott feltételnek megfelelően:
1) derítse ki, hogy létezik-e olyan állapotgép, amelyre az általa átalakított információ megfelel ennek a feltételnek;
2) ha igen, akkor egy ilyen véges állapotú gép átmeneti függvényeit megszerkesztjük, vagy megbecsüljük a memória méretét.
A szintézis feladat megoldása egy ilyen megfogalmazásban feltételezi egy kényelmes nyelv előzetes megalkotását az automata működési feltételeinek rögzítésére, kényelmes algoritmusokkal a rögzítésről a tranzitív függvényekre való átmenethez.
Az automaták szerkezetelméletében a szintézisprobléma abból áll, hogy egy adott típusú elemláncot hozunk létre, amely az átmeneti függvényei által adott véges automatát valósítja meg. Ilyenkor általában valamilyen optimalitási kritériumot (például minimális elemszámot) adnak meg, és egy optimális sémát keresnek.
Mint később kiderült, ez azt jelenti, hogy a reléérintkezős áramkörökkel kapcsolatban korábban kidolgozott módszerek és koncepciók egy része más típusú áramkörökre is alkalmazható.
Az elektronikai technológiák fejlődésével kapcsolatban a legelterjedtebbek a sémák funkcionális elemek (logikai hálózatok). A logikai hálózatok speciális esetei az absztrakt neurális hálózatok, amelyek elemeit neuronoknak nevezzük.
Számos szintézismódszert fejlesztettek ki, az áramkörök típusától és az információk átalakításától függően, amelyekre szánták (Reléeszközök szintézise).
Néz -Kombinációs áramkörök minimalizálása, Carnot térképek, áramkör szintézis
Véges állapotú gép — egy vezérlőrendszer matematikai modellje rögzített (üzem közben nem tud növekedni) memóriamérettel.
A véges állapotú gép fogalma egy matematikai absztrakció, amely a vezérlőrendszerek halmazának (például egy többhurkos reléeszköz) általános jellemzőit jellemzi. Minden ilyen rendszernek vannak közös jellemzői, amelyeket természetes, hogy elfogadunk a véges automata definíciójaként.
Minden elkészült automatának van külső behatásoknak és belső elemeknek kitett bejárata. Mind a bemeneti, mind a belső elemek esetében meghatározott számú diszkrét állapot áll rendelkezésre.
A bemeneti és belső elemek állapotának változása diszkrét időpillanatokban megy végbe, az ezek közötti intervallumokat ticknek nevezzük. A belső állapotot (a belsők állapotát) a szalag végén teljes mértékben a belső állapot és a szalag elején lévő bemenet állapota határozza meg.
A véges automata összes többi definíciója erre a jellemzőre redukálható, különösen azok a definíciók, amelyek azt feltételezik, hogy egy véges automatának olyan kimenete van, amely az automata adott időpontban fennálló belső állapotától függ.
Egy ilyen jellemző szempontjából a bemeneteinek és belső állapotainak természete irreleváns a teljes automata leírása szempontjából. A bemenetek és állapotok helyett egyszerűen megtekintheti a számukat véletlenszerű számozással.
Az állapotgép akkor lesz beállítva, ha belső állapotszámának az előző belső állapotszámtól és az előző bemeneti állapotszámtól való függése meg van adva. Egy ilyen feladat lehet döntő asztal formájában.
A komplett automata meghatározásának másik elterjedt módja az ún átmenet diagramok. A bemeneti állapotokat gyakran egyszerűen bemeneteknek, a belső állapotokat pedig egyszerűen állapotoknak nevezik.
A véges állapotú gép mind a műszaki eszközök, mind pedig egyes biológiai rendszerek modellje lehet. Az első típusú automaták például a relékészülékek és a különféle elektronikus számítógépek, pl. programozható logikai vezérlők.
Relé eszköz esetén a bemeneti állapotok szerepét a reléeszköz érzékeny elemeinek állapotkombinációi játsszák (az ilyen állapotok mindegyik kombinációja egy „összetett állapot”, amelyet a közvetítő eszköz összes érzékeny elemének jelzése jellemez. ezek a diszkrét állapotok, amelyek egy adott pillanatban vannak). Hasonlóképpen, a relé eszköz közbenső elemeinek állapotkombinációi belső állapotként működnek.
A programozható logikai vezérlő (PLC) egy példa a reléművelet eszközre, amelyet önálló állapotgépnek nevezhetünk.
Valójában, miután a program bekerült a PLC-be, és a vezérlő elkezdett számolni, nincs kitéve külső hatásoknak, és minden további állapotot teljesen meghatároz az előző állapota. Feltételezhetjük, hogy a bemenet minden órajelben azonos állapotú.
Ezzel szemben minden olyan véges állapotú gépet, amelynek egyetlen lehetséges bemeneti állapota van, természetesen autonómnak nevezzük, mivel ebben az esetben a külső környezet nem hordoz olyan információt, amely szabályozná a viselkedését.
Lásd még:
Mikroprocesszoros rendszerek alkalmazása az elektrotechnikában a PLC alkalmazásának példáján