Automatų teorija.docx – Automatų teorija. Bendrosios sąvokos
Teorinės kibernetikos šaka, kuri tiria matematiniai modeliai(vadinami automatais, mašinomis) realiai egzistuojantys (techniniai, biologiniai ir kt.) arba iš esmės galimi įrenginiai, diskrečią informaciją apdorojantys diskretiškais laiko ciklais. Ir. t. iškilo hl. taip, veikiant skaitmeninių kompiuterių ir valdymo mašinų technologijos reikalavimams, taip pat vidiniams algoritmų teorijos ir matematinės logikos poreikiams. „Automato“ sąvoka labai skiriasi priklausomai nuo šių prietaisų pobūdžio, nuo priimto abstrakcijos lygio ir atitinkamo bendrumo laipsnio (automatai yra baigtiniai, begaliniai, augantys, tikimybiniai, deterministiniai, autonominiai ir kt.).
Klausimas yra apie tokios koncepcijos "automatą" sukūrimą, kuris turėtų maks. Bendrumo laipsnio ir tuo pačiu galėtų būti pagrindu nustatant ir sprendžiant pakankamai esmines problemas, dar negali būti laikomos visiškai išspręstomis. Kartu tai gali būti laikoma specialiu bendrosios valdymo sistemos sampratos atveju.
Sąvoka „A. T." pradėta naudoti XX amžiaus šeštajame dešimtmetyje, nors atitinkamos problemos didele dalimi pradėjo formuotis dar 30-aisiais algoritmų teorijos ir relių įtaisų teorijos rėmuose. Tada teorijos algoritmuose buvo suformuluotos gana bendros skaičiavimo sąvokos. automatas (žr. Tiuringo mašiną) ir (netiesiogiai) baigtinio automato samprata (tiūringo mašinos galvutė). Nustatyta, kad norint
visokios efektyvios informacijos transformacijos, visai nebūtina kiekvieną kartą kurti specializuotų automatų; iš esmės visa tai galima padaryti vienoje universalioje mašinoje su tinkama programa ir tinkamu kodu. Ši teorija. rezultatas vėliau gavo inžinerinį įsikūnijimą modernių universalių kompiuterių pavidalu. mašinos. Tačiau išsamus įvairių tipų automatuose vykstančių procesų ir jiems taikomų bendrųjų dėsnių tyrimas prasidėjo vėliau tik A. T. Formuluotės skirtumai tarp algoritmų teorijos problemų ir A. T. kokios mašinos gali daryti ir kaip jie tai daro. Kadangi kitų tipų automatų (išskyrus Tiuringo mašinas) įtraukimas tikrai neišplečia skaičiuojamų informacijos transformacijų atsargų, tai algoritmų teorijai toks įtraukimas yra tik epizodinis ir siejamas tik su taikoma įrodinėjimo technika. Kita vertus, A. t. toks svarstymas tampa savitiksliu. Theor. ir taikomosios automatizavimo, skaičiavimo problemos. technologija ir programavimas, biol modeliavimas. elgesys ir tt toliau skatina A. t.. Tačiau kartu su tuo A. t. jau vystosi savo vidines problemas. Algebros teorijoje plačiai naudojamas algebros, matematinės logikos, kombinatorinės analizės (įskaitant grafų teoriją) ir tikimybių teorijos aparatas.
Automatų teorijoje kai kurios jo kryptys išryškėja gana aiškiai, nulemtas tiriamų automatų tipų (baigtinių, tikimybinių ir kt.) pasirinkimo, priimto abstrakcijos lygio (žr. Abstrakčių automatų teorija, Struktūrinė automatų teorija). ), arba pagal taikomosios matematikos specifiką. metodai (žr. Algebrinių automatų teoriją). Kartu su tuo susijusios problemos ir metodai intensyviai plėtojami relinių įrenginių teorijoje, skaitmeninių kompiuterių teorijoje ir programavimo teorijoje, todėl dažnai sunku atskirti šių teorijų veikimo sritis nuo A. t.
Elgesys ir struktūra. A. t. centre yra tikslūs kilimėliai. sąvokos, kurios formalizuoja intuityvias idėjas apie automato veikimą ir elgesį, taip pat apie jo struktūrą (vidinę struktūrą). Automatai savo elgsenos požiūriu dažniausiai laikomi žodyno informacijos konverteriais, t.y. raidžių sekų keitėjais į raidžių sekas. Įgyvendinama transformacija paprastai interpretuojama kaip tam tikros funkcijos (operatoriaus) reikšmių apskaičiavimas pateiktomis argumentų reikšmėmis arba kaip tam tikro tipo problemų sąlygų įrašų pavertimas į įrašus atitinkamus sprendimus. Visų pirma, vadinamieji. atpažindami automatus, suvokdami įvesties informaciją, į ją reaguoja taip, kad vienas įvesties signalų sekas priimtų, o kitas atmestų. Šia prasme jie atpažįsta arba, kaip sakoma, atstovauja daugybei įvesties sekų. Galiausiai generacinis automatas funkcionuoja kaip autonominė sistema, nesusijusi su įvesties informacija, jo elgesį lemia tai, kokias išvesties sekas jis sugeba generuoti. Aukščiau pateikta klasifikacija transformacijos, atpažinimo ir generavimo požiūriu priklauso nuo automato veikimo taisyklių, ty nuo jo sąveikos programos. vidines būsenas su įvestimis (gaunama iš išorinė aplinka) ir išvesties (pagamintas į aplinką) signalus. Tegu Q, X, Y yra atitinkamai automato įėjimo ir išėjimo signalų vidinių būsenų rinkinys. Jei tai deterministinis automatas, jo programa formalizuojama perėjimo f-ts ir išėjimo f-ts Ф atžvilgiu, kiekvienam įvesties signalui x ir kiekvienai būsenai nurodant būseną, į kurią pereina automatas, ir jo generuojamą išėjimo signalą.
Abstrakčiai automatinei teorijai būdingas aukštesnis abstrakcijos lygis: joje automato sąvoka tapatinama su automato programos sąvoka, tai yra su penkiais (), visiškai abstrakcija nuo jos struktūros. Automato struktūra atspindi, kaip jis yra organizuotas iš paprastesnių tarpusavyje sąveikaujančių komponentų (elementarių automatų arba tiesiog elementų), tinkamai sujungtų viena sistema. Pavyzdžiui, skaičiavimas mašina sudaryta iš elementarių elementų, tokių kaip trigeriai, keitikliai ir kt.; Nervų sistema susideda iš neuronų. Struktūrinę automatų klasifikaciją nulemia leidžiamų jungčių pobūdis (jungtys gali būti standžios arba eksploatacijos eigoje besikeičiančios, taikomos tam tikri geom. apribojimai), taip pat naudojamų elementų veikimo ir sąveikos specifika ( pavyzdžiui, elementai gali tik keistis informacija arba gali generuoti naujus elementus, sukurdami struktūrą). Struktūrinių sąvokų formalizavimas atliekamas pagal įvairių tipų schemas (žr. Loginis tinklas). AN Kolmogorovas apibūdino metodą, kuris paskatino suformuluoti labai bendrą, bet vis dar konstruktyvią automato struktūros koncepciją (žr. Augantys automatai), kuri, matyt, apima visus žinomus automatų struktūrų tipus ir visus tuos, kuriuos galima numatyti šiuolaikinio lygio mokslai. Visiškai akivaizdu, kad tarp automato struktūros ir jo elgesio yra glaudus ryšys. Tačiau atskiras kiekvieno iš šių dviejų aspektų tyrimas su reikšmingu abstrakcija nuo kito yra ne tik įmanomas, bet dažnai naudingas nustatant ir sprendžiant daugelį problemų. svarbius klausimus. Toks tyrimas atliekamas atitinkamai abstrakčioje (elgesio) ir struktūrinėje automatų teorijoje.
Mašinų tipai. Labiausiai paplitęs yra automatų ir ko-resp. skyriai A. t., skirti įvairiems
mašinų tipų, atsižvelgiant į šias savybes.
1) Atminties kiekis. Baigtiniai ir begaliniai automatai apibūdinami pagal. atminties kiekio (vidinių būsenų skaičiaus) baigtinumą ir begalybę. Baigtiniai automatai yra atskiri šiuolaikinio skaičiavimo blokai. mašinos ir net visa mašina. Smegenys taip pat gali būti vertinamos kaip baigtinės būsenos mašina. Begaliniai automatai yra natūralus kilimėlis. idealizavimas, išaugantis iš idėjos apie automatą su baigtiniu, bet beribiu didelis skaičius teigia. Tai reiškia tik potencialią atminties begalybę, kuri pasireiškia tuo, kad atmintis, nors ir išlieka baigtinė kiekvienu laiko momentu, gali augti neribotai. Toks idealizavimas pirmą kartą atsirado algoritmų teorijos rėmuose, tobulinant intuityvią algoritmo idėją. Struktūriškai augantis automatas vaizduojamas kaip elementų, galinčių daugintis ir augti, derinys. Šiuolaikinius kompiuterius galima laikyti augančiais (o kartu ir potencialiai begaliniais) automatais tokia prasme: kad skaičiavimai būtų baigti visais atvejais, reikia pripažinti neriboto išorinės (juostinės) atminties augimo galimybę.
2) Atsitiktinės atrankos mechanizmas. Deterministiniuose automatuose elgesį ir struktūrą kiekvienu laiko momentu vienareikšmiškai lemia dabartinė įvesties informacija ir automato būsena, kuri susiformavo prieš pat momentą. Tikimybiniuose (stochastiniuose) automatuose jie taip pat priklauso nuo kažkokio atsitiktinio pasirinkimo. Stochastiniai automatai neturėtų būti painiojami su nedeterministiniais automatais, kuriuose taip pat pažeidžiama unikalumo sąlyga (tačiau nedalyvaujant c.l. atsitiktinės atrankos mechanizmui).
Problemos ir metodai. Pagrindinės automatinės teorijos problemos apima analizės, ty automato elgesio aprašymo pagal jo pateiktą programą ar struktūrą, ir sintezės, ty automatų projektavimo, kurių elgesys atitiktų iš anksto nustatytus reikalavimus, problemas. Su šiomis problemomis glaudžiai susijusios ir daugelis kitų intensyviai tiriamų problemų (išsamumas ir universalumas, minimizavimas, kalbos, asimptotiniai įverčiai ir kt.). Labiausiai analizė ir sintezė buvo tiriama baigtinių deterministinių automatų teorijoje, o abstrakčiai ir struktūrinėje automatų teorijoje jie interpretuojami skirtingai. Taigi, pavyzdžiui, struktūrų teorijoje sintezė (žr. Struktūrinių automatų sintezę) reiškia grandinės sukūrimą iš tam tikro elementų asortimento, kuris būtų optimalus. (arba artimas optimaliam) tam tikro grandinių sudėtingumo kriterijaus prasme. Čia vyrauja kombinatoriniai-informaciniai metodai ir asimptotiniai įverčiai (K. Shannon, S. V. Yablonskii, O. B. Lupanov ir kt.). Abstrakčioje automatų teorijoje pasitenkinama automato veikimo programos konstravimu (žr. Abstrakti automatų sintezė), pavyzdžiui, baigtinio automato perėjimo ir išėjimo funkcijų forma, kuri dažniausiai yra pradinė. medžiaga tolesnei struktūrinės sintezės plėtrai. Čia vyrauja algebrinė (S. K. Klini, V. M. Gluškovas ir kt.), matematinė ir loginė. (B. A. Trakhtenbrot, R. Buchi ir kt.) ir žaidimo (R. McNotop) metodai ir sąvokos. Relinių įtaisų teorijoje svarbią vietą užima ir baigtinių deterministinių automatų analizės ir sintezės problema.
Eksperimentų su automatais teorijoje (E. Moore) kuriami metodai, kurie leidžia, naudojant informaciją, gautą iš išorės stebėjimo automato elgseną, atkurti jo veikimo programą ar bent kai kurias jo savybes. Šiuos metodus galima vertinti kaip savotišką abstrakčią automatų sintezę ir dekodavimą (Ya. M. Barzdin). K. Shannon, M. Rabin ir kitų darbai pasitarnavo kaip postūmis plėtoti tikimybinių automatų teoriją m. vadovaudamiesi nurodymais 1) kiek deterministinių automatų teorijos sąvokos ir metodai perkeliami į stochastinius automatus; 2) kokie skaičiavimo supaprastinimai. procesai pasiekiami paliekant siauresnę deterministinių automatų klasę į platesnę tikimybinių automatų klasę. Auginimo automatų tyrimas daugiausia orientuotas į šias problemas: 1) auginimo automatų modelių kūrimas ir atskirų jų klasių tyrimas (iteraciniai automatai - F. Henny, registro automatai - V. M. Gluškovas, savaime atkuriantys automatai - J. von Neumann, apibendrintas auginimo automatas - A. N. Kolmogorovas, Ya. M. Barzdinas); 2) įvertinimas skaičiuojamas auginimo automatų (Ya. M. Barzdin, B. A. Trakhtenbrot, Yu. Khartmanis, G. S. Tseitin, M. Rabin ir kt.) skaičiavimo galimybė ir sudėtingumas.
Ryšys su kitomis mokslo sritimis.
Algoritmų teorijos ir relinių įtaisų teorijos reikšmė automatinei technologijai jau buvo paaiškinta aukščiau. Taip pat turėtume atkreipti dėmesį į A. t. abipusiškumą, kurio metodai leido išspręsti daugybę matematikos problemų. logika ir algoritmų teorija (R. Buchi). Augančių automatų teorijoje iškylanti problema (pavyzdžiui, skaičiavimo sudėtingumas) iš esmės glūdi algoritmų teorijos ir asimptotinių dėsningumų sankirtoje automatų struktūrinėje sintezėje. Stiprus abipusis matematinės lingvistikos ir matematinės kalbotyros, kurios viena iš svarbių sąvokų yra generacinė gramatika, skverbtis yra objektas, labai artimas generatyviniam automatui. Todėl tam tikrus gana svarbius gramatikų teorijos teiginius iš esmės galima priskirti automatinei teorijai Abstrakčioje automatų teorijoje mat. mokymosi, taip pat vieno individo ar komandos tikslingo elgesio klausimai buvo išaiškinti ir tiriami žaidimo automatų požiūriu (M. L. Tsetlin). Naudinga
taip pat buvo ryšys tarp baigtinių automatų teorijos ir kompiuterių projektavimo bei programavimo teorijos (V. M. Gluškovas, A. A. Letichevskis).
Lit .: Gavrilov M A. Relių-kontaktinių grandinių teorija. M. - L., 1950 [bibliogr. Su. 298-299]; „Matematikos instituto darbai. V. A. Steklovo SSRS mokslų akademija, 1958, t. 51; Gluškovas V. M. Skaitmeninių automatų sintezė. M., 1962 [bibliogr. Su. 464–469]; Kobrinsky N. E., Trakhtenbrot B. A. Įvadas į baigtinių automatų teoriją. M., 1962 [bibliogr. Su. 399-402]; Tsetlin ML Automatų teorijos ir biologinių sistemų modeliavimo tyrimai. M., 1969 [bibliogr. Su. 306-316]; Trakhtenbrot B. A., Barzdin Ya. M. Baigtiniai automatai (Elgesys ir sintezė). M., 1970 [bibliogr. Su. 389-395]; Automatas. Per. iš anglų kalbos. M., 1956. B. A., Trakhtenbrotas.
AUTOMATOV TEORIJA, diskrečiosios matematikos skyrius, tiriantis diskrečiųjų informacijos keitiklių, vadinamų automatais, matematinius modelius. Tokių keitiklių pavyzdžiai yra ir realios sistemos (kompiuteriai, techniniai automatai, gyvi organizmai), ir abstrakčios sistemos (abstrakčiai kompiuteriai, aksiomatinės teorijos). Automatų teorija atsirado XX amžiaus viduryje, tiriant automatus kaip biologinių sistemų ir kompiuterių matematinius modelius. Ateityje automatų teorijos problema gerokai išsiplėtė.
Automatų teorija yra glaudžiai susijusi su algoritmų teorija, ypač su abstrakčių kompiuterių teorija, nes automatai gali būti laikomi jų aproksimacijos atvejis.
Automatas gali būti apibūdinamas kaip įrenginys, turintis įvesties ir išvesties kanalus ir esantis vienoje iš vidinių būsenų kiekvienu atskiru laiko momentu. Signalai-įtakos tokiu momentu patenka į įvesties kanalą. Tais pačiais momentais prietaisas generuoja reakcijos signalus per išvesties kanalą. Automato būsenos, signalai-veiksmai ir signalai-reakcija pateikiamos atitinkamų abėcėlių raidėmis: būsenų abėcėlė, taip pat įvesties ir išvesties signalų abėcėlė. Šių abėcėlių raidžių sąveikos dėsnius pateikia dvi funkcijos – perėjimo funkcija ir išvesties funkcija, kurios atitinkamai susieja poras (būseną – įvesties raidę) į būsenas ir išvesties raides. Automato įvesties aplinka yra įvesties abėcėlės žodžių rinkinys, o jo vidinė ir išvesties aplinka yra būsenos abėcėlės ir išvesties abėcėlės žodžių rinkiniai. Automatas apdoroja žodžius iš įvesties aplinkos raidė po raidės į dviejų kitų aplinkų žodžius. Šis procesas vadinamas automato elgesiu. Abėcėlės ir funkcijų savybės nustato skirtingi tipai mašinos. Tuo atveju, kai visos abėcėlės yra baigtinės, gaunamas baigtinis automatas, kitu atveju automatas vadinamas begaliniu. Funkcijų pakeitimas ryšiais veda prie dalinių ir nedeterministinių automatų; naudojimas atsitiktinės funkcijos veda prie tikimybinio automato. Aiškinant įvesties aplinką terminais ar grafikais, prieina prie automatų per terminus ir automatų labirintuose.
Dauguma automatų teorijos problemų yra bendros pagrindiniams valdymo sistemų tipams, jos apima automatų analizės ir sintezės problemas, užbaigtumo, minimizavimo problemas, taip pat problemas, susijusias su ekvivalentinėmis automatų transformacijomis. Analizės uždavinys – aprašyti jo elgesį pagal duotą automatą arba iš nepilnų duomenų apie automatą ir jo veikimą nustatyti vienokias ar kitokias jo savybes. Sintezės užduotis yra sukurti automatą su tam tikru elgesiu arba operacija. Greta šios problemos yra problemos, susijusios su tam tikros elgsenos automatų sudėtingumo įvertinimu, taip pat su optimalaus konstravimo. tam tikra prasme mašinos. Išsamumo problema yra išsiaiškinti, ar tam tikrą automatų rinkinį galima gauti iš mažesnio rinkinio, naudojant tam tikras automatų operacijas. Automatų mažinimo užduotis yra sumažinti automato parametrų reikšmes (pavyzdžiui, būsenų skaičių), todėl gaunamas automatas, kuris viena ar kita prasme yra lygiavertis pradiniam. Be užduočių, bendrų pagrindiniams valdymo sistemų tipams, automatų teorijoje atsižvelgiama specifines problemas būdingas automatams. Taigi, atsižvelgiant į problemos sąlygas, patogu įjungti automatų elgesį skirtingomis kalbomis(taisykliniai posakiai, kanoninės lygtys, predikatinės logikos kalba ir kt.), su kuriomis susijusios pakankamai patogios adekvačios kalbos pasirinkimas ir vertimas iš vienos kalbos į kitą yra svarbūs uždaviniai. Automato būsenų skaičiaus mažinimo problema yra susijusi su sintezės ir lygiaverčių transformacijų problemomis. Dėl vienos klasės automatų elgesio modeliavimo kitos klasės automatais iškyla modeliavimo automatų mažinimo ir jų sudėtingumo įvertinimo problemos. Speciali automatų teorijos dalis yra susijusi su vadinamaisiais eksperimentais su automatais. Pagrindinis šio skyriaus uždavinys – gauti tam tikrą informaciją apie automato sandarą, stebint jo reakciją į tam tikrus išorinius poveikius. Šiuo atveju iškyla problemų, susijusių su eksperimentų klasifikavimu ir problemų išsprendžiamumu tam tikro tipo eksperimentais, taip pat su minimalių eksperimentų trukmės, pakankamos tam tikroms problemoms išspręsti, įvertinimu. Eksperimento su automatais koncepcija taip pat naudojama automatų valdymo uždaviniuose. Specialūs automatų teorijos skyriai – tai automatų žaidimai ir automatų elgesys atsitiktinėje aplinkoje, kuriuose nagrinėjami automatų sąveikos tarpusavyje ir su tam tikra išorine aplinka klausimai. Daugelis aukščiau išvardintų problemų gali būti laikomos masinėmis problemomis (žr. Algoritminę problemą). Dėl baigtinių automatų dauguma jų turi teigiamą sprendimą.
Automatų teorija pritaikoma daugelyje sričių. Pavyzdžiui, kai kurių formalių skaičiavimų išsprendžiamumas įrodomas naudojant teorijos automatus. Automatų teorijos metodai ir sąvokos iš esmės naudojami matematinės lingvistikos srityse. Automato samprata gali pasitarnauti kaip pavyzdinis objektas sprendžiant įvairias problemas, o tai leidžia panaudoti teorijos automatus įvairiuose taikomuosiuose tyrimuose.
Lit .: Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S. Įvadas į automatų teoriją. M., 1985 m.
Federalinė švietimo agentūra
valstybė švietimo įstaiga aukštasis profesinis išsilavinimas
„MASKVOS VALSTYBINIO UNIVERSITETAS
INSTRUMENTAI IR INFORMATIKA »
IT-4 katedra „Asmeniniai kompiuteriai ir tinklai“
"PATVIRTINTI"
Skyriaus vedėjas IT-4
Michailovas B.M.
„___“ __________________ 2007 m
PASKAITOS
1425 disciplinoje „Automatų teorija“
IT fakulteto II kurso studentams
Specialybės 230101
„Kompiuteriai, kompleksai, sistemos ir tinklai“
Aptartas skyriaus posėdyje
„___“ ________________ 2007 m
_____ protokolas Nr.
Maskva 2007 m
^ Bendrosios nuostatos
Disciplinos tikslai ir uždaviniai
Disciplinos tikslas – pristatyti programinės ir techninės įrangos organizavimo principus asmeninių kompiuterių rėmuose naudojant automatų teoriją, įsisavinant kūrimo įgūdžius. programinė įranga ir kompiuterinė įranga.
^ Reikalavimai disciplinos turinio įsisavinimo lygiui
Žinios, įgytos įsisavinant discipliną:
Automatų teorijos principai ir pagrindinės sąvokos;
Automatų teorijos taikymas konstruojant algoritminių kalbų vertėjus;
Automatų teorijos taikymas kuriant įrenginius ir atskirą įrangą asmeniniuose kompiuteriuose;
Automatų teorijos taikymas taikomiesiems uždaviniams spręsti;
Atskirų įrenginių projektavimas;
Vertėjo dizainas;
Pagrindinė literatūra
1. Saveliev A.Ya. Informatikos pagrindai: vadovėlis universitetams.-M.: Leidykla MSTU im. N. Bauman, 2001.-328s.
2. Karpovas Yu.G.
3. Zaicevas E.I. Automatų teorija: Vadovėlis.-M.: MGAPI, 2002.-59s.
papildomos literatūros
1. Hopcroft D., Motwani R., Įvadas į automatų teoriją, kalbas ir skaičiavimus: vertimas iš anglų kalbos-M.: Izdat. Domas Viljamsas, 2002.-528psl.
Paskaita numeris 1.
Pagrindinės sąvokos ir apibrėžimai
Trukmė: 2 valandos (90) minučių
1.1. Pagrindinės (pagrindinės) problemos (akimirkos)
„Automatų teorijos“ disciplinos vieta daugelyje katedroje skaitytų disciplinų
Automatų teorijos objektai
Automatų teorijos problemos
Pagrindinės sąvokos ir apibrėžimai.
^ AUTOMATŲ TEORIJA.
1.2.1. Automatų teorijos pagrindai. Iki 20 minučių
Mašina (iš graikų - veikiantis savarankiškai) - valdymo sistema, kuris yra baigtinių būsenų mašina arba tam tikra jo modifikacija, gauta pakeitus jo komponentus ar veikimą. Pagrindinė sąvoka – baigtinis automatas – atsirado XX amžiaus viduryje dėl bandymų matematine kalba apibūdinti nervų sistemų funkcionavimą, universalius kompiuterius ir kt. tikros mašinos. būdingas bruožas toks aprašymas yra diskretiškumas atitinkamus matematinius modelius ir jų parametrų diapazonų baigtinumą, dėl ko susidaro baigtinio automato samprata.
Automatų teorija yra teorijos skyrius valdymo sistemos, kuris tiria diskrečiųjų informacijos keitiklių matematinius modelius, vadinamas kulkosvaidis. Tam tikru požiūriu tokie keitikliai yra ir realūs įrenginiai (kompiuteriai, automatai, gyvi organizmai ir kt.), ir abstrakčios sistemos (pavyzdžiui, formali sistema, aksiomatinės teorijos ir kt.). Labiausiai susiję su algoritmų teorija.
Dauguma automatų teorijos problemų yra bendros pagrindiniams valdymo sistemų tipams. Tai automatų analizės ir sintezės problemos, užbaigtumo, minimizavimo, lygiaverčių automatų transformacijų problemos ir kt. Analizės užduotis susideda iš jo elgesio apibūdinimo remiantis tam tikru automatu arba, remiantis nepilnais duomenimis apie automatą ir jo veikimą, vienokių ar kitokių jo savybių nustatymo. Sintezės užduotis automatas susideda iš automato su iš anksto nustatyto elgesio ar veikimo sukūrimas. Išsamumo iššūkis yra išsiaiškinti, ar rinkinys turi M" M automatai su užbaigtumo savybe, t.y. ar sutampa su M visų automatų rinkinys, gautas baigtiniu skaičiumi kai kurių operacijų taikymų automatams iš tam tikro automatų poaibio M" . Lygiaverčių transformacijų problema bendras vaizdas yra rasti transformacijos taisyklių sistemą (vadinamą pilna sistema taisyklės) automatai, kurie tenkina tam tikras sąlygas ir leidžia savavališką automatą paversti bet kuriuo lygiaverčiu automatu (du automatai yra lygiaverčiai, jei jų elgsena yra tokia pati. Mašinos elgesys matematinė sąvoka aprašantis automato sąveiką su išorine aplinka. Baigtinio automato aplinkos pavyzdys yra įvesties žodžių rinkinys, o elgsena yra automato įdiegta žodyno funkcija arba automato vaizduojamas įvykis.)
Be aukščiau išvardintų, automatų teorijoje yra specifinių problemų, kurios būdingos automatams. Taigi, atsižvelgiant į problemos sąlygas, patogu nurodyti automato elgesį skirtingomis kalbomis, dėl kurių svarbios užduotys yra pakankamai patogios adekvačios kalbos pasirinkimas ir vertimas iš vienos kalbos į kitą. Glaudžiai susijęs su sintezės ir lygiaverčių transformacijų problemomis minimizavimo problema automato būsenų skaičių, taip pat atitinkamų įverčių gavimą. Glaudus klausimų ratas kyla dėl vienos klasės automatų elgesio modeliavimo kitos klasės automatais. Čia taip pat domina modeliavimo automatų sumažinimo ir jų sudėtingumo įvertinimo klausimai. Ypatinga automatų teorijos šaka yra susijusi su vadinami eksperimentais su automatais(t.y. informacijos apie automatų vidinę sandarą gavimo būdai pagal jų elgesį). Pagrindinė užduotis čia yra gauti tam tikrą informaciją apie automato sandarą, stebint jo reakciją į tam tikrus išorinius poveikius. Tai sukelia didelis ratas problemos, susijusios su eksperimentų klasifikavimu ir problemų išsprendžiamumo tam tikro tipo eksperimentais klausimais, taip pat su minimalių eksperimentų trukmės įverčiais, kurių pakanka tam tikroms problemoms išspręsti. Eksperimento su automatais sąvoka taip pat naudojama uždaviniuose patikimumas ir kontrolė valdymo sistemos, ypač automatų valdymas. Daugelis aukščiau išvardytų problemų gali būti vertinamos kaip algoritminės problemos. Dėl baigtinių automatų dauguma jų turi teigiamą sprendimą.
Automatų teorija pritaikoma tiek kitose matematikos srityse, tiek sprendžiant praktines problemas. Pavyzdžiui, kai kurių formalių skaičiavimų išsprendžiamumas įrodomas automatų teorijos pagalba. Automatų teorijos metodų ir sąvokų taikymas formaliųjų ir natūralių kalbų studijoms paskatino matematinės lingvistikos atsiradimą (matematinė lingvistika yra matematinė disciplina, kurios dalykas yra formalaus aparato, skirto natūralių ir natūralių kalbų struktūrai apibūdinti, sukūrimas). kai kurios dirbtinės kalbos.) Automato sąvoka gali pasitarnauti kaip pavyzdinis objektas sprendžiant įvairiausias problemas , o tai leidžia panaudoti automatų teoriją įvairiuose moksliniuose ir taikomuosiuose tyrimuose.
^ 1.2.2. Automatų teorija sprendžiami uždaviniai ir uždaviniai. Iki 30 minučių
Automatų teorija- diskrečiosios matematikos šaka, tirianti realių (techninių, biologinių, ekonominių) ar galimų įrenginių, apdorojančių diskrečią informaciją diskrečiaisiais laiko ciklais, matematinius modelius.
Šioje teorijoje jos kryptys yra gana aiškiai nustatytos dėl:
tiriamų automatų tipų pasirinkimas (baigtinis, begalinis, deterministinis, tikimybinis, autonominis, kombinacinis, be išėjimo)
priimtas abstrakcijos lygis (abstrakčiai ir struktūriniai automatai)
taikomosios matematikos specifika (algebrinė automatų teorija)
Centrinės skaitomos teorijos problemos yra sintaksės ir analizės problemos (t.y. automato funkcinės schemos sukūrimas pagal duotą elgseną ir automato elgesio aprašymas pagal žinomą struktūrą). Šios problemos yra glaudžiai susijusios su pilnumo, lygiavertiškumo ir automatų būsenų skaičiaus sumažinimo problemomis.
Be to, automatas, kaip prietaisas, skirtas atlikti tikslingus veiksmus be žmogaus įsikišimo, yra laikomas arba įgyvendinančiu vieną ar kitą formaliąją gramatiką (abstraktus automatas), arba kaip elementų rinkinį ir jų sujungimo schemą (struktūrinis automatas).
sąveikaujančių procesų sistemų tikrinimas;Tai galima spręsti iš mokslininkų ir specialistų pranešimų seminare „Programinė įranga 2000...“.
Dougas Rossas: "...80 ar net 90% kompiuterių mokslo (Computer Science) ateityje bus paremta baigtinių automatų teorija..."
Herveris Gallaire'as: "Žinau, kad "Boeing" žmonės dirba su orlaivių stabilizavimo sistemomis, naudojant gryną automatų teoriją. Sunku įsivaizduoti, ką jie padarė su šia teorija."
Brianas Randelas: " Dauguma automatų teorija buvo sėkmingai naudojama sistemos programos ir teksto filtrai UNIX OS. Tai leidžia daugeliui žmonių dirbti aukšto lygio ir labai tobulėti veiksmingos programos".
1.1. Pagrindinės sąvokos ir apibrėžimai.
Paprasčiausias informacijos keitiklis (1.1 pav., a) atvaizduoja tam tikrą informacijos elementų rinkinį Xincoming į įėjimą į tam tikrą rinkinį išėjime Y. Jei aibės X ir Y yra baigtinės ir diskrečios, tai yra, transformacija vykdoma diskrečiu laiku, tai tokie informacijos keitikliai vadinami baigtiniais keitikliais. Nustatykite elementus X ir Y šiuo atveju yra iš anksto užkoduoti dvejetainiais kodais ir sukuriama vienos rinkinio transformacija į kitą.
Konversijos rezultatas dažnai priklauso ne tik nuo to, kokia informacija yra Šis momentas atsirado prie įėjimo, bet ir iš to, kas įvyko anksčiau, tai yra iš virsmo priešistorės. Pavyzdžiui, tas pats indėlis – kaimyno atsiprašymas po to, kai sausakimšame autobuse jis užlipo tau ant kojos – pirmą kartą sukels vienokią reakciją, o penktą – visiškai kitokią.
Ryžiai. 1.1.
Taigi yra sudėtingesnių informacijos transformatorių (IT), kurių atsakas priklauso ne tik nuo įvesties signalų šiuo metu, bet ir nuo to, kas vyko anksčiau, nuo įvesties istorijos. Tokie PI vadinami automatais (atminties grandinėmis). Šiuo atveju kalbama apie automatinį informacijos transformavimą (1.1 pav., b). Automatas gali skirtingai reaguoti į tą patį įvesties signalą, priklausomai nuo būsenos, kurioje jis buvo. Automatas keičia savo būseną su kiekvienu įvesties signalu.
Pažvelkime į kelis pavyzdžius.
1 pavyzdys 1 Karpovas Yu.G. Automatų teorija-Sankt Peterburgas: Sankt Peterburgas, 2003 m. Automatas, apibūdinantis „protingo“ tėvo elgesį.
Apibūdinkime, kaip elgiasi tėvas, kurio sūnus eina į mokyklą ir atneša dvejetus ir penketukus. Tėvas nesinori kiekvieną kartą griebtis diržo, vos tik sūnus gauna dvikovą, ir pasirenka subtilesnę auklėjimo taktiką. Tokį automatą apibrėžiame grafiku, kuriame viršūnės atitinka būsenas, o lankas iš būsenos s į būseną q, pažymėtas x/y, nubrėžiamas, kai automatas iš būsenos s, veikiamas įvesties signalo x, pereina į būseną. q su išvesties reakcija y. Išmanųjį tėvų elgesį imituojančio automato grafikas parodytas 1.2 pav. Šis automatas turi keturias būsenas 
, du įvesties signalai – įvertinimai ir išvesties signalai , kuriuos interpretuosime kaip pirminio veiksmus taip:
Paimkite diržą;
barti sūnų;
Nuramink sūnų;
viltis;
džiaugtis;
Džiaukis.
Ryžiai. 1.2.
Sūnus, gavęs tą patį pažymį – dvikovą, namuose tikisi visai kitokios tėvo reakcijos, priklausomai nuo studijų fono. Pvz., po trečio dvikovo istorijoje sūnus bus pasveikintas diržu, o istorijoje bus nuramintas ir t.t.
Būsenos mašina gali būti įdiegta tiek programinėje, tiek techninėje įrangoje. Programinės įrangos diegimas galima padaryti bet kuriuo kalba aukštas lygis Skirtingi keliai. 1.3 paveiksle parodyta programos, kuri įgyvendina 1 pavyzdžio automato elgesį, blokinė schema. Nesunku pastebėti, kad programos blokinės diagramos topologija pakartoja automato perėjimo grafiko topologiją. Kiekviena būsena yra susieta su operacija NEXT , kuri atlieka funkciją laukti kito naujo įvesties signalo atėjimo įvykio ir nuskaityti jį į kokį nors standartinį buferį x , taip pat vėliau analizuoti, koks tai signalas. Priklausomai nuo to, koks signalas atėjo į įvestį, ta ar kita funkcija vykdoma ir įvyksta perėjimas į naują būseną.
Ryžiai. 1.3.
Antroje šio skyriaus dalyje bus aptariamas automato aparatinis įgyvendinimas.
2 pavyzdys. „Studentas“
Automatas , kurio modelis parodytas 1.4 pav., apibūdina mokinio ir dėstytojų elgesį.
Ryžiai. 1.4.
valstybėse;
- įvesties signalai: "n", "2" ir "5".
Išvesties reakcijos:
3 pavyzdys 1 . Elektroninis laikrodis (1.5 pav.).
Įvairių funkcionalumų elektroniniai laikrodžiai – vienas plačiausiai kasdieniame gyvenime naudojamų elektroninių prietaisų, kurio valdymas sukonstruotas baigtinio automato modelio pagrindu. Paprastai jie rodo: laiką, datą; jie turi tokias funkcijas kaip „laiko ir datos nustatymas“, „chronometras“, „žadintuvas“ ir kt. Supaprastinta struktūrinė schema elektroninis laikrodis parodytas 1.5 pav
Ryžiai. 1.5.
Registruose rodomas arba laikas, arba data, arba chronometras, priklausomai nuo „Valdymo“. Valdymo įtaisas pastatytas baigtinio automato modelio pagrindu. Būsenos mašina reaguoja į „a“ mygtuko paspaudimus ant kūno pereidama į būseną „Nustatyti minutes“, kai paspaudus mygtuką „b“ skaičius padidės.
Vyatkos valstybinis universitetas
AUTOMATIKOS IR SKAIČIAVIMO INŽINERIJOS FAKULTETAS
Elektroninių kompiuterių katedra
Automatų teorija (I dalis) Paskaitų konspektas
Automatų teorija (I dalis). Paskaitų konspektas /Kirov, Vyatsky Valstijos universitetas, 2010, 56s.
Kurso „Automatų teorija“ (I dalis) paskaitų konspektuose pateikiama reikiama teorinė medžiaga, apimanti taikomosios skaitmeninių automatų teorijos pagrindus, pagrindinius abstrakčių baigtinių automatų, diskrečiųjų automatų grandinės apibrėžimus ir sintezės taisykles. konverteris VM Gluškovas ir trys pagrindiniai baigtinių automatų modeliai: Mealy modelis, Moore modelis ir C automato modelis. Toliau aptariame atminties elementų kodavimo metodus, automatų sumažinimą naudojant atmintį ir kanoninį struktūrinių automatų sintezės metodą. Ypatingas dėmesys skiriamas optimalios automato kombinacinės schemos konstravimo taisyklėms pagal kanonines lygtis, atsižvelgiant į pasirinktus atminties elementus. Nurodyta atitinkama literatūra.
Paskaitų kursas skirtas 230101 – „Kompiuteriai, kompleksai, sistemos ir tinklai“ specialybės dieninių studijų studentams, taip pat krypties 230100.62 – „Kompiuterija ir kompiuterinės technologijos“ bakalaurams.
Sudarė: Ph.D., katedros docentas. Kompiuteris V.Yu. Melcovas.
Vyatkos valstybinis universitetas, 2010 m
Meltsovas V. Ju.
1. Įvadas 4
2. Analizės ir sintezės problemos 4
3. Abstraktaus valdymo automatas 7
4. Sintezė abstraktūs automatai 9
5. Sinchroninė mašina 10
6. Asinchroninės mašinos 11
7. Mealy ir Moore mašinos 12
8. Automatų nustatymo būdai 14
8.1 Lentelinis automatų nurodymo būdas 15
8.2. Automato nustatymas naudojant 17 stulpelį
8.3. Matricinis automatų nurodymo metodas 19
9. Perėjimas nuo Mealy mašinos prie Moore mašinos ir atvirkščiai 19
10. Automatų sintezės etapai 23
11. Automato vidinių būsenų skaičiaus sumažinimas 26
12. Visiškai apibrėžtų automatų sumažinimas. 27
13. Kombinuotas automato modelis (C-automatas) 31
14. Struktūrinė automato sintezė 32
14.1. Kanoninis automato struktūrinės sintezės metodas 32
14.2. Struktūrinė C automato sintezė 35
15. Automato būsenų kodavimas 41
15.1. Automato būsenų kodavimo prieš lenktynes metodas 42
15.2. Kaimyninis automato būsenų kodavimas 45
15.3. Kodavimo automato būsenos, siekiant sumažinti kombinuotą grandinę 47
16. Elementariosios atminties automatai 50
17. Automatų sintezė PLM ir ROM 54
1. Įvadas
Pastaraisiais metais itin intensyviai vykdomi įvairių automatinių informacijos apdorojimo sistemų kūrimo ir pritaikymo tyrimai bei darbai. Tokios sistemos dažniausiai diegiamos blokų pavidalu, kurie sudaro informacijos valdymo ir apdorojimo sistemą. Atsižvelgiant į tai, atsirado nauja mokslo disciplina, kuri vadinosi „Sistemų teorija“.
Sistemų teorijos tikslas – sukurti idėjų ir priemonių arsenalą, kuris būtų vienodai naudingas įvairių sričių (elektros inžinerijos, mechanikos, fizikos, chemijos, sociologijos ir kt.) specialistams. Šis tikslas pasiekiamas nagrinėjant sistemą ne per jos vidinę struktūrą, o per matematinius dėsnius, lemiančius jos stebimą elgesį. Šiuo atveju dažniausiai naudojamas metodas vadinamas „juodosios dėžės“ metodu (t. y. metodu, kai analizuojami įvesties duomenys ir mašinos išvestyje gauti duomenys, neatsižvelgiant į vidinius procesus). Įrodyta, kad visas sistemas galima apibūdinti tais pačiais terminais ir analizuoti naudojant tą patį taisyklių rinkinį.
Neatsiejama sistemų teorijos dalis yra automatų teorija. Jame nagrinėjami matematiniai modeliai, skirti daugiau ar mažiau apytiksliai parodyti fizikinius reiškinius. Automatų teorijos modelio taikymas neapsiriboja jokia konkrečia sritimi, bet gali išspręsti beveik bet kurios studijų srities problemas.