Automatų teorija, baigtiniai automatai
Įvairių mašinų struktūrą, dizainą, veikimo principą daugiausia lemia jų funkcinė paskirtis. Atskirkite technologines, transporto, skaičiavimo, karines ir kitas mašinas. Įvairiose pramonės šakose plačiai pristatomi ištisi automatiniai kompleksai, skirti atlikti sudėtingus technologinius procesus. Projektuojami ir gaminami automatai, kurie atlieka įvairias logines funkcijas (loginės mašinos).
Automatų teorija — kibernetikos skyrius, kuris atsirado veikiant skaitmeninių kompiuterių ir valdymo mašinų technologijos reikalavimams. Automatų teorijoje tyrinėjami diskretieji automatai yra abstraktūs realių sistemų (tiek techninių, tiek biologinių) modeliai, apdorojantys diskrečią (skaitmeninę) informaciją diskretiškais laiko žingsniais.
Automatų teorija remiasi tiksliomis matematinėmis sąvokomis, kurios formalizuoja intuityvias idėjas apie automato veikimą (elgseną) ir apie jo struktūrą (vidinę struktūrą).
Šiuo atveju informacijos transformavimas visada suprantamas kaip operacija, kuri paverčia įvesties sekas, sudarytas iš įvesties abėcėlės raidžių, į išvesties sekas, sudarytas iš išvesties abėcėlės raidžių.
Plačiai naudojamas matematinės logikos, algebros, tikimybių teorijos, kombinatorikos ir grafų teorijos aparatas.
Išaugo problema, susijusi su automatų teorija kai kuriose jos dalyse (automatų struktūrinė teorija). iš relių-kontaktinių grandinių teorijos, kuris pradėjo formuotis praėjusio amžiaus trečiojo dešimtmečio pabaigoje. imtinai loginės algebros metodai.
Struktūrinėje automatų teorijoje tiriamos įvairių tipų schemos, skirtos aprašyti, kaip iš paprastesnių komponentų (elementų), tinkamai sujungtų sistemoje, sukuriamas sudėtingas automatas.
Kita kryptis, vadinama abstrakčiąja automatų teorija, tiria automatų elgesį (tai yra jų vykdomos informacijos transformacijos pobūdį), abstrahuojantis nuo jų vidinės struktūros specifikos, ir atsirado šeštajame dešimtmetyje.
Abstrakčios automatų teorijos rėmuose sąvokų „automatas“ ir „mašina“ turinys iš esmės yra išnaudotas standartiniame informacijos transformavimo aprašyme, kurį atlieka automatas. Tokia transformacija gali būti deterministinė, bet gali būti ir tikimybinio pobūdžio.
Labiausiai tiriamos deterministinės mašinos (automatai), kurios apima baigtinius automatus – pagrindinį automatų teorijos tyrimo objektą.
Baigtinės būsenos mašina pasižymi ribotu atminties kiekiu (vidinių būsenų skaičiumi) ir apibrėžiama naudojant perėjimo funkciją.Su tam tikru pagrįstu idealizavimu visos šiuolaikinės matematinės mašinos ir net smegenys, jų veikimo požiūriu, gali būti laikomos baigtiniais automatais.
Sąvokos „nuosekli mašina“, „Milly automatas“, „Mūro automatas“ literatūroje (ir ne visų autorių vienodai) vartojamos kaip termino „baigtinis automatas“ sinonimai arba norint pabrėžti tam tikras baigtinio perėjimo funkcijų ypatybes. automatas.
Automatas su neribota atmintimi yra Tiuringo mašina, galinti atlikti (galbūt) bet kokią veiksmingą informacijos transformaciją. „Turingo mašinos“ sąvoka atsirado anksčiau nei „ribinės būsenos mašinos“ sąvoka ir daugiausia tiriama algoritmų teorijoje.
Abstraktioji automatų teorija yra glaudžiai susijusi su gerai žinomomis algebrinėmis teorijomis, pavyzdžiui, pusgrupių teorija. Taikomuoju požiūriu įdomūs yra rezultatai, apibūdinantys informacijos transformaciją automate pagal atminties dydį.
Taip yra, pavyzdžiui, problemos, susijusios su eksperimentais su automatais (E.F. Moore'o darbai ir kt.), kai iš automato rezultatų gaunama vienokia ar kitokia informacija apie automato perėjimo funkcijas ar apie jo atminties talpą. eksperimentai.
Kita užduotis – remiantis turima informacija apie automato atminties dydį ir įvesties sekų periodus apskaičiuoti išvesties sekų periodus.
Labai svarbu sukurti metodus, kaip sumažinti baigtinių būsenų mašinų atmintį ir tirti jų elgesį atsitiktinėse aplinkose.
Abstrakčioje automatų teorijoje sintezės problema yra tokia.Kalbant apie kažkokią aiškiai formalizuotą kalbą, yra parašytos sąlygos suprojektuoto automato elgsenai (automate vaizduojamam įvykiui). Tokiu atveju būtina sukurti metodus, kurie pagal kiekvieną rašytinę sąlygą:
1) išsiaiškinti, ar egzistuoja tokia būsenos mašina, kurios transformuojama informacija atitinka šią sąlygą;
2) jei taip, tada sukonstruojamos tokios baigtinių būsenų mašinos perėjimo funkcijos arba įvertinamas jos atminties dydis.
Sintezės uždavinio sprendimas tokioje formuluotėje suponuoja preliminariai sukurti patogią kalbą automato darbo sąlygoms fiksuoti su patogiais algoritmais perėjimui nuo įrašymo prie pereinamųjų funkcijų.
Struktūrinėje automatų teorijoje sintezės uždavinys yra sudaryti tam tikro tipo elementų grandinę, kuri realizuoja baigtinį automatą, kurį suteikia jo pereinamosios funkcijos. Šiuo atveju jie dažniausiai nurodo kokį nors optimalumo kriterijų (pavyzdžiui, minimalų elementų skaičių) ir siekia gauti optimalią schemą.
Kaip paaiškėjo vėliau, tai reiškia, kad kai kurie anksčiau sukurti metodai ir koncepcijos, susiję su relės kontaktinėmis grandinėmis, yra taikomi kito tipo grandinėms.
Kalbant apie elektroninių technologijų plėtrą, labiausiai paplitusios yra schemos funkcinių elementų (loginiai tinklai). Ypatingas loginių tinklų atvejis yra abstraktūs neuroniniai tinklai, kurių elementai vadinami neuronais.
Sukurta daug sintezės metodų, priklausomai nuo grandinių tipo ir informacijos, kuriai jie skirti, transformavimo (Relių įrenginių sintezė).
Žiūrėk -Kombinuotų grandinių minimizavimas, Carnot žemėlapiai, grandinių sintezė
Baigtinės būsenos mašina — matematinis valdymo sistemos modelis su fiksuotu (negalinčiu didėti veikimo metu) atminties dydžiu.
Baigtinės būsenos mašinos sąvoka yra matematinė abstrakcija, apibūdinanti valdymo sistemų rinkinio (pavyzdžiui, kelių kilpų relinio įrenginio) bendrąsias charakteristikas. Visos tokios sistemos turi bendrų bruožų, kuriuos natūralu priimti kaip baigtinio automato apibrėžimą.
Kiekvienas sukomplektuotas automatas turi įėjimą, veikiamą išorinių poveikių ir vidinių elementų. Tiek įvesties, tiek vidinių elementų atveju yra fiksuotas skaičius atskirų būsenų, kurias jie gali įgyti.
Įvesties ir vidinių elementų būsenos pokytis įvyksta atskirais laiko momentais, intervalai tarp kurių vadinami erkėmis. Vidinę būseną (vidinių dalių būseną) juostos pabaigoje visiškai lemia vidinė būsena ir įvesties būsena juostos pradžioje.
Visi kiti baigtinio automato apibrėžimai gali būti sumažinti iki šios charakteristikos, ypač apibrėžimai, kuriuose daroma prielaida, kad baigtinis automatas turi išėjimą, kuris priklauso nuo automato vidinės būsenos tam tikru metu.
Kalbant apie tokią charakteristiką, jo įėjimų ir vidinių būsenų pobūdis neturi reikšmės pilno automato aprašymui. Vietoj įvesties ir būsenų galite tiesiog pažvelgti į jų skaičius atsitiktine tvarka.
Būsenos mašina bus nustatyta, jei bus nurodyta jos vidinio būsenos numerio priklausomybė nuo ankstesnio vidinio būsenos numerio ir ankstesnio įvesties būsenos numerio. Tokia užduotis gali būti galutinės lentelės forma.
Kitas įprastas būdas apibrėžti pilną automatą yra vadinamojo konstravimo perėjimų diagramos. Įvesties būsenos dažnai vadinamos tiesiog įvestimis, o vidinės būsenos yra tiesiog būsenos.
Baigtinės būsenos mašina gali būti ir techninių prietaisų, ir kai kurių biologinių sistemų modelis. Pirmojo tipo automatai yra, pavyzdžiui, reliniai įrenginiai ir įvairūs elektroniniai kompiuteriai, įskaitant. programuojami loginiai valdikliai.
Relinio įtaiso atveju įvesties būsenų vaidmenį atlieka jautrių relinio įrenginio elementų būsenų deriniai (kiekvienas tokių būsenų derinys yra „sudėtinga būsena“, kuriai būdingas visų jautrių elementų rodymas). šias atskiras būsenas, kurias jie turi tam tikru momentu). Panašiai relinio įrenginio tarpinių elementų būsenų deriniai veikia kaip vidinės būsenos.
Programuojamas loginis valdiklis (PLC) yra relės veikimo įrenginio, kurį galima pavadinti atskira būsenos mašina, pavyzdys.
Tiesą sakant, įvedus programą į PLC ir valdikliui pradėjus skaičiuoti, ji nėra veikiama išorinių poveikių ir kiekviena paskesnė būsena yra visiškai nulemta ankstesnės būsenos. Galime manyti, kad įvestis turi tą pačią būseną kiekviename laikrodžio cikle.
Ir atvirkščiai, bet kuri baigtinės būsenos mašina, turinti vienintelę įmanomą įvesties būseną, natūraliai vadinama autonomine, nes šiuo atveju išorinė aplinka neturi informacijos, kuri valdytų jos elgesį.
Taip pat žiūrėkite:
Mikroprocesorinių sistemų panaudojimas elektrotechnikoje PLC panaudojimo pavyzdžiu