Teorija automata- dio diskretne matematike koji proučava apstraktne automate - računala predstavljena u obliku matematičkih modela - i zadatke koje oni mogu riješiti.
Teorija automata u najbliskijoj je vezi s teorijom algoritama: automat pretvara diskretne informacije u koracima u diskretne trenutke vremena i generira rezultat u koracima zadanog algoritma.
- 1 Terminologija
- 2 Primjena
- 2.1 Tipični zadaci
- 3 Vidi također
- 4 Književnost
- 5 Veze
Terminologija
Simbol- bilo koji atomski blok podataka koji može utjecati na stroj. Najčešće je simbol slovo na uobičajenom jeziku, ali može biti, na primjer, grafički element dijagrama.
- Riječ- niz znakova koji nastaje spajanjem (povezivanjem).
- Abeceda- konačan skup različitih znakova (mnogo znakova)
- Jezik- skup riječi formiran simbolima zadane abecede. Može biti konačan ili beskonačan.
Automati
Automati mogu biti deterministički i nedeterministički.
Deterministički konačni automat (DFA)- je prijelazna funkcija takva da
- - početno stanje
- - skup automatskih stanja
- - abeceda jezika koji automat razumije
- je prijelazna relacija, gdje je prazna riječ. To jest, NFA može skočiti iz stanja q u stanje p, za razliku od DFA, kroz praznu riječ, a također ići iz q u nekoliko stanja (što je opet nemoguće u DFA)
- - skup početnih stanja
- - skup konačnih stanja.
Za jezik L se kaže da ga automat M čita (prihvaća) ako se sastoji od riječi w na temelju abecede tako da ako se te riječi unesu u M, na kraju obrade dolazi u jedno od prihvatljivih stanja F:
Tipično, automat prelazi iz stanja u stanje pomoću funkcije prijelaza, dok čita jedan znak iz ulaza. Postoje automati koji mogu prijeći u novo stanje bez čitanja znaka. Prijelazna funkcija bez čitanja znaka naziva se -jump (epsilon-jump).
Primjena
Teorija automata je temelj svih digitalnih tehnologija i softvera, na primjer, računalo je poseban slučaj praktične implementacije konačnog stroja.
Dio matematičkog aparata teorije automata izravno se koristi u razvoju leksera i parsera za formalne jezike, uključujući programske jezike, kao i u konstrukciji kompilatora i razvoju samih programskih jezika.
Druga važna primjena teorije automata je matematički rigorozno određivanje rješivosti i složenosti problema.
Tipični zadaci
- Konstrukcija i minimizacija automata- konstrukcija apstraktnog automata iz zadane klase koji rješava zadani problem (prihvaćanje zadanog jezika), eventualno s naknadnim minimiziranjem u smislu broja stanja ili broja prijelaza.
- Sinteza automata- izgradnja sustava zadanih "elementarnih automata", ekvivalentnih zadanom automatu. Takav automat naziva se strukturni. Koristi se, na primjer, u sintezi digitalnih električnih krugova na zadanoj bazi elemenata.
vidi također
- Lema o pumpi
- Apstraktni automat
- Igra "Život"
- Minimalni oblik automata
- Shannon-Lupanov teorem
Književnost
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Uvod u teoriju automata, jezike i računanje. - M.: Williams, 2002. - S. 528. - ISBN 0-201-44124-1.
- Kasyanov VN Predavanja iz teorije formalnih jezika, automata i računske složenosti. - Novosibirsk: NSU, 1995. - C. 112.
Linkovi
- Primjena teorije automata
teorija automata
Odjeljak teorijske kibernetike koji proučava matematičke modele (zvane automati, strojevi) stvarno postojećih (tehničkih, bioloških itd.) ili fundamentalno mogućih uređaja koji obrađuju diskretne informacije u diskretnim vremenskim koracima. I. t. nastao hl. način pod utjecajem zahtjeva tehnologije digitalnih računala i upravljačkih strojeva, kao i unutarnjih potreba teorije algoritama i matematičke logike. Koncept "automata" značajno varira ovisno o prirodi tih uređaja, o prihvaćenoj razini apstrakcije i odgovarajućem stupnju općenitosti (automati su konačni, beskonačni, rastući, vjerojatnost, deterministički, autonomni, itd.).
Pitanje je o razvoju takvog koncepta "automatika", koji bi imao max. stupanj općenitosti, a ujedno bi mogao poslužiti kao osnova za postavljanje i rješavanje dovoljno smislenih problema, ne može se smatrati još potpuno riješenim. Međutim, može se smatrati kao poseban slučaj opći koncept kontrolnog sustava.
Izraz "A. T." ušao u upotrebu 50-ih godina 20. stoljeća, iako su se odgovarajući problemi u velikoj mjeri počeli oblikovati već 30-ih godina u okviru teorije algoritama i teorije relejnih uređaja. Već tada su algoritmi teorije bili dovoljno formulirani opći pojmovi Računalo. automat (vidi Turingov stroj) i (implicitno) koncept konačnog automata (glava Turingovog stroja). Utvrđeno je da bi se
sve vrste učinkovitih transformacija informacija, uopće nije potrebno svaki put graditi specijalizirane automate; u principu, sve se to može napraviti na jednom univerzalnom stroju s pravim programom i pravim kodiranjem. Ova teorija. rezultat je kasnije dobio inženjersko utjelovljenje u obliku modernih univerzalnih računala. strojevi. Međutim, detaljno proučavanje procesa koji se događaju u automatima raznih vrsta, i općih zakona kojima su oni podložni, počelo je kasnije tek u okviru A. T. Razlika u formulacijama između problema teorije algoritama i A. T. što strojevi mogu rade i kako to rade. Budući da sudjelovanje drugih vrsta automata (osim Turingovih strojeva) zasigurno ne proširuje zalihu izračunljivih transformacija informacija, onda je za teoriju algoritama takva uključenost samo epizodna i povezana je samo s primijenjenom tehnikom dokazivanja. S druge strane, za A. t. takvo razmatranje postaje samo sebi svrha. Theor. i primijenjeni problemi automatizacije, račun. tehnologija i programiranje, biol modeliranje. ponašanje itd. nastavljaju stimulirati probleme A. t. No, uz to, A. t. već razvija svoje unutarnje probleme. Aparat algebre, matematičke logike, kombinatorne analize (uključujući teoriju grafova) i teorije vjerojatnosti široko se koristi u algebarskoj teoriji.
U teoriji automata neki se njezini smjerovi pojavljuju sasvim jasno, određeni izborom vrsta automata koji se proučavaju (konačni, probabilistički itd.), prihvaćenom razinom apstrakcije (vidi Apstraktna teorija automata, Strukturna teorija automata ), ili specifičnostima primijenjene matematike. metode (vidi Algebarska teorija automata). Uz to, srodni problemi i metode intenzivno se razvijaju u teoriji relejnih uređaja, u teoriji digitalnih računala i u teoriji programiranja, stoga je često teško razlikovati sfere djelovanja ovih teorija i A. t.
Ponašanje i struktura. U srcu A. t. su egzaktni mat. koncepti koji formaliziraju intuitivne ideje o funkcioniranju i ponašanju automata, kao i o njegovoj strukturi (unutarnjoj strukturi). Sa stajališta njihovog ponašanja, automati se najčešće smatraju pretvaračima rječničkih informacija, odnosno pretvaračima nizova slova u nizove slova. Transformacija koja se provodi obično se tumači kao izračunavanje vrijednosti neke funkcije (operatora) prema danim vrijednostima argumenata, ili kao transformacija zapisa stanja problema određene vrste u zapise odgovarajuća rješenja. Konkretno, tzv. prepoznavajući automati, percipirajući ulaznu informaciju, reagiraju na nju na način da neke ulazne sekvence signala prihvaćaju, a druge odbijaju. U tom smislu prepoznaju ili, kako kažu, predstavljaju mnoge ulazne sekvence. Konačno, generativni automat funkcionira kao autonomni sustav, koji nije povezan s ulaznim informacijama, njegovo ponašanje je određeno koje je izlazne sekvence u stanju generirati. Navedena klasifikacija u smislu transformacije, prepoznavanja i generiranja ovisi o pravilima za funkcioniranje automata, odnosno o programu za interakciju njegovih unutarnjih stanja s ulazom (koji dolazi iz vanjskog okruženja) i izlazom (proizvedenim u vanjsko okruženje) signali. Neka su Q, X, Y, redom, skup unutarnjih stanja ulaznih i izlaznih signala automata. Ako je ovo deterministički automat, njegov se program formalizira u terminima prijelaza f-ts i izlaznog f-ts F, navodeći za svaki ulazni signal x i svako stanje stanje u koje automat prelazi, i izlazni signal koji on generira
Apstraktnu automatsku teoriju karakterizira viša razina apstrakcije: u njoj se koncept automata poistovjećuje s konceptom automatskog programa, odnosno s pet (), s potpunom apstrakcijom od njegove strukture. Struktura automata odražava način na koji je organiziran od jednostavnijih međusobno povezanih komponenti (elementarnih automata ili jednostavno - elemenata), pravilno povezanih u jedinstveni sustav. Na primjer, računica stroj se sastoji od elementarnih ćelija kao što su okidači, invertori itd.; živčani sustav izgrađen od neurona. Strukturna klasifikacija automata određena je prirodom dopuštenih veza (veze mogu biti krute ili se mijenjati tijekom rada, podvrgnute određenim geom. ograničenjima), kao i specifičnostima funkcioniranja i interakcije korištenih elemenata ( na primjer, elementi mogu samo razmjenjivati informacije ili mogu generirati nove elemente, izgrađujući strukturu). Formalizacija strukturnih koncepata provodi se u smislu različitih tipova shema (vidi Logička mreža). AN Kolmogorov iznio je pristup koji je doveo do formulacije vrlo općenitog, ali ipak konstruktivnog koncepta strukture automata (vidi Rastući automati), koji, po svemu sudeći, pokriva sve poznate vrste automatskih struktura i sve one koje se mogu predvidjeti u na suvremenoj razini znanosti. Sasvim je očito da postoji bliska veza između strukture automata i njegovog ponašanja. Međutim, zasebno proučavanje svakog od ova dva aspekta, sa značajnom apstrakcijom od drugog, ne samo da je moguće, već je često korisno u postavljanju i rješavanju mnogih važnih problema. Takvo proučavanje provodi se u apstraktnoj (biheviorskoj) teoriji strukture automata.
Vrste strojeva. Najčešća je klasifikacija automata i suodn. odjeljci A. t., posvećeni raznim
vrste strojeva, prema sljedećim značajkama.
1) Količina memorije. Konačni i beskonačni automati karakterizirani su prema. konačnost i beskonačnost količine memorije (broj unutarnjih stanja). Konačni automati su zasebni blokovi modernog računalstva. strojeve pa čak i stroj u cjelini. Mozak se također može promatrati kao konačni stroj. Beskonačni automati su prirodna prostirka. idealizacija koja izrasta iz ideje automata s konačnim, ali beskonačno velikim brojem stanja. To se odnosi samo na potencijalnu beskonačnost sjećanja, koja se očituje u činjenici da sjećanje, iako ostaje konačno u svakom trenutku vremena, može beskonačno rasti. Takva je idealizacija prvi put nastala u okviru teorije algoritama u procesu rafiniranja intuitivne ideje algoritma. Strukturno rastući automat predstavljen je kao kombinacija elemenata sposobnih za reprodukciju i rast sheme. Suvremena računala se mogu smatrati rastućim (i u isto vrijeme potencijalno beskonačnim) automatima u sljedećem smislu: da bi izračuni bili dovršeni u svim slučajevima, potrebno je dopustiti mogućnost neograničenog rasta vanjske (tračne) memorije.
2) Mehanizam slučajnog odabira. U determinističkim automatima, ponašanje i struktura u svakom trenutku vremena jedinstveno su određeni trenutnim ulaznim informacijama i stanjem automata koje se razvilo u neposredno prethodnom trenutku. U probabilističkim (stohastičkim) automatima oni također ovise o nekom slučajnom izboru. Stohastičke automate ne treba miješati s nedeterminističkim automatima, kod kojih je uvjet jedinstvenosti također narušen (međutim, bez sudjelovanja k.l. mehanizma slučajnog odabira).
Problemi i metode. Središnji problemi automatske teorije uključuju probleme analize, tj. opisivanje ponašanja automata na temelju zadanog programa ili strukture, i sinteze, tj. projektiranja automata čije bi ponašanje zadovoljilo unaprijed određene zahtjeve. S tim problemima usko su povezani i mnogi drugi problemi koji se intenzivno proučavaju (potpunost i univerzalnost, minimizacija, jezici, asimptotske procjene itd.). Najviše se analiza i sinteza proučavaju u teoriji konačnih determinističkih automata, a različito se tumače u apstraktnoj i strukturnoj teoriji automata. Tako, na primjer, u strukturnoj teoriji, sinteza (vidi Sinteza strukturnih automata) znači konstrukciju kruga iz zadanog asortimana elemenata koji bi bio optimalan. (ili blizu optimalnog) u smislu određenog kriterija za složenost sklopova. Ovdje prevladavaju kombinatorno-informacijske metode i asimptotske procjene (K. Shannon, S. V. Yablonskii, O. B. Lupanov i drugi). U apstraktnoj teoriji automata zadovoljava se konstruiranjem programa za funkcioniranje automata (vidi Apstraktna sinteza automata), na primjer, u obliku prijelaznih i izlaznih funkcija za konačni automat, koji obično služi kao polazna materijal za daljnji razvoj strukturne sinteze. Ovdje pretežno algebarski (S. K. Klini, V. M. Glushkov, itd.), matematički i logički. (B. A. Trakhtenbrot, R. Buchi i dr.) i igre (R. McNotop) metode i koncepti. Problem analize i sinteze konačnih determinističkih automata također zauzima istaknuto mjesto u teoriji relejnih uređaja.
U teoriji eksperimenata s automatima (E. Moore) razvijaju se metode koje omogućuju, koristeći informacije dobivene vanjskim promatranjem ponašanja automata, da se obnovi program njegova funkcioniranja ili barem neka njegova svojstva. Ove metode se mogu smatrati nekom vrstom apstraktne sinteze i dekodiranja automata (Ya. M. Barzdin). Radovi K. Shanona, M. Rabina i drugih poslužili su kao poticaj za razvoj teorije probabilističkih automata u sljedećim smjerovima: 1) u kojoj se mjeri koncepti i metode teorije determinističkih automata prenose na stohastičke automate. ; 2) kakva pojednostavljenja izračuna. procesi su ostvarivi prelaskom uže klase determinističkih automata u širu klasu vjerojatnosnih automata. Proučavanje rastućih automata uglavnom je usmjereno na sljedeće probleme: 1) razvoj modela rastućih automata i proučavanje njihovih pojedinačnih klasa (iterativni automati - F. Henny, registarski automati - VM Glushkov, samoreproducirajući automati - J. von Neumann, generalizirani rastući automati - A. N. Kolmogorov, Ya. M. Barzdin); 2) evaluacija izračunatog sposobnost i složenost računanja rastućih automata (Ya. M. Barzdin, B. A. Trakhtenbrot, Yu. Khartmanis, G. S. Tseitin, M. Rabin, itd.).
Odnos s drugim znanstvenim područjima.
Već je gore objašnjeno značenje teorije algoritama i teorije relejnih uređaja za automatsku tehnologiju. Također treba istaknuti reciprocitet A. t., čije su metode omogućile rješavanje niza problema koji su se pojavili u matematici. logika i teorija algoritama (R. Buchi). Problemi koji se pojavljuju u teoriji rastućih automata (na primjer, složenost proračuna) u osnovi leže na sjecištu teorije algoritama i asimptotičkih pravilnosti u strukturnoj sintezi automata. Snažan međusobni prodor matematičke lingvistike i matematičke lingvistike, čiji je jedan od važnih pojmova generativna gramatika, objekt je vrlo blizak generativnom automatu. Stoga se pojedini prilično važni stavovi teorije gramatike u načelu mogu pripisati automatskoj teoriji.U apstraktnoj teoriji automata, mat. pitanja učenja, kao i svrsishodnog ponašanja jednog pojedinca ili tima, razjašnjena su i proučavana u smislu automata igre (M. L. Tsetlin). Koristan
postojala je i veza između teorije konačnih automata i teorije računalnog dizajna i teorije programiranja (V. M. Glushkov, A. A. Letichevsky).
Lit .: Gavrilov M A. Teorija relejno-kontaktnih krugova. M. - L., 1950 [bibliogr. iz. 298-299]; “Radnici Matematičkog instituta. V. A. Steklov Akademija znanosti SSSR-a, 1958, v. 51; Glushkov V. M. Sinteza digitalnih automata. M., 1962 [bibliogr. iz. 464-469]; Kobrinsky N. E., Trakhtenbrot B. A. Uvod u teoriju konačnih automata. M., 1962 [bibliogr. iz. 399-402]; Tsetlin ML Istraživanje teorije automata i modeliranja bioloških sustava. M., 1969 [bibliogr. iz. 306-316]; Trakhtenbrot B. A., Barzdin Ya. M. Konačni automati (Ponašanje i sinteza). M., 1970 [bibliogr. iz. 389-395]; Automati. Po. s engleskog. M., 1956. B.A, Trakhtenbrot.
Državno sveučilište Vyatka
FAKULTET AUTOMATIKE I RAČUNARSTVA
Zavod za elektronička računala
Teorija automata (I. dio) Bilješke s predavanja
Teorija automata (I dio). Bilješke s predavanja /Kirov, Vyatsky Državno sveučilište, 2010., 56s.
Bilješke s predavanja za kolegij "Teorija automata" (I. dio) pružaju potreban teorijski materijal, uključujući osnove primijenjene teorije digitalnih automata, osnovne definicije i pravila za sintezu apstraktnih konačnih automata, sklop diskretnog automata. pretvarač VM Glushkov i tri glavna modela konačnih automata: Mealyjev model, Mooreov model i model C-automata. Zatim razmatramo metode za kodiranje memorijskih elemenata, minimiziranje automata s memorijom i kanoničku metodu za sintezu strukturnih automata. Posebna je pozornost posvećena pravilima za konstruiranje optimalne kombinatorne sheme automata prema kanonskim jednadžbama, uzimajući u obzir odabrane memorijske elemente. Navedena je relevantna literatura.
Kolegij predavanja namijenjen je redovitim studentima specijalnosti 230101 – „Računala, kompleksi, sustavi i mreže“, kao i prvostupnicima smjera 230100.62 – „Računarstvo i računalna tehnologija“.
Sastavio: dr. sc., izvanredni profesor Katedre. Računalo V.Yu. Meltsov.
Državno sveučilište Vyatka, 2010
Meltsov V.Yu.
1. Uvod 4
2. Problemi analize i sinteze 4
3. Apstraktni upravljački automat 7
4. Sinteza apstraktnih automata 9
5. Sinkroni stroj 10
6. Asinkroni strojevi 11
7. Mealy i Moore strojevi 12
8. Načini postavljanja automata 14
8.1 Tabelarni način određivanja automata 15
8.2. Postavljanje automata pomoću stupca 17
8.3. Matrična metoda specificiranja automata 19
9. Prijelaz s Mealy stroja na Moore stroj i obrnuto 19
10. Faze sinteze automata 23
11. Minimiziranje broja unutarnjih stanja automata 26
12. Minimizacija potpuno definiranih automata. 27
13. Model kombiniranog automata (C-automat) 31
14. Strukturna sinteza automata 32
14.1. Kanonska metoda strukturne sinteze automata 32
14.2. Strukturna sinteza C-automata 35
15. Kodiranje stanja automata 41
15.1. Metoda anti-trkaćeg kodiranja stanja automata 42
15.2. Susjedsko kodiranje stanja automata 45
15.3. Kodiranje stanja automata za minimiziranje kombinacijskog kruga 47
16. Elementarni memorijski automati 50
17. Sinteza automata na PLM i ROM 54
1. Uvod
Posljednjih godina se velikim intenzitetom provode istraživanja i rad na izradi i primjeni različitih automatskih sustava za obradu informacija. Takvi se sustavi obično implementiraju u obliku blokova koji čine sustav za upravljanje i obradu informacija. U skladu s tim nastala je nova znanstvena disciplina koja je nazvana "Teorija sustava".
Cilj teorije sustava je stvoriti arsenal ideja i alata koji bi bili podjednako korisni stručnjacima u različitim područjima (elektrotehnika, mehanika, fizika, kemija, sociologija itd.). Taj se cilj postiže promatranjem sustava ne kroz njegovu unutarnju strukturu, već kroz matematičke zakone koji određuju njegovo promatrano ponašanje. U ovom slučaju, najčešće korišteni pristup naziva se metoda “crne kutije” (tj. metoda u kojoj se analiziraju ulazni podaci i podaci dobiveni na izlazu stroja, a interni procesi se ne razmatraju). Dokazano je da se svi sustavi mogu okarakterizirati istim pojmovima i analizirati korištenjem istog skupa pravila.
Sastavni dio teorije sustava je teorija automata. Bavi se matematičkim modelima koji su dizajnirani da više ili manje približe prikaz fizikalnih pojava. Primjena modela teorije automata nije ograničena na neko posebno područje, već je moguće riješiti probleme u gotovo svakom području studija.