n põhimääratlused Lõplik automaat on süsteem M =(А, B, S, y), milles n n n А = (а 1, . . . , am) on lõplik sisendtähestik, B =(b 1, . . . , bk ) - lõplik väljundtähestik, S =(s 1, . . . , sn) - lõpliku oleku tähestik, : A S S - üleminekufunktsioon, y: A S B - väljundfunktsioon. n Kui automaadis M on valitud üks olek, mida nimetatakse algolekuks (tavaliselt arvestatakse, et see on s 1), siis nimetatakse saadud automaati algolekuks ja seda tähistatakse (M, s 1). n Automaadi defineerimiseks on kaks võimalust: Automaadi tabel, üleminekuskeem
Automaadi tabel n 1) 2) 3) 4) Näide: määrake automaat sõna "001" lugemiseks, kui on sisestatud märgid "0" ja "1". Sisendtähestik A=(0, 1) Väljundtähestik A=(Y, N) Olekutähestik S=(s 0 "" , s 1 " 0" , s 2 " 00" s 3 "001" ) Automaatne tabel kahel viisil . 1) read on automaadi olekud. Veerud on sisestussümbolid. Ridade ja veergude ristumiskohas on näidatud funktsioonid, y. 2) S, A, y on antud veergude kaupa. Harjutus 25 Ehitage automaat sõna CAKADU SA 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" otsimiseks. " S 1 , N S 0, N S In y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 N S 1 S 2 S 3
Üleminekuskeem n Olekutele vastab orienteeritud multigraaf, mida nimetatakse graafiku siirdediagrammiks, või graafik. Kui (Si, aj)=Sk, y(Si, aj)=bl, siis tipust Si tippu Sk kulgeb kaar, millele on kirjutatud (aj, bl) n Iga tipu si juures on korrektsuse tingimused : 0 1 S 0 "" S 1, N S 0, N S 1 "0" n tipud, y S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1, N S 0, N 1, N täidetud 1) iga sisendtähe aj puhul on si-st väljuv kaar, millele on kirjutatud aj (täielikkuse tingimus); 2) mis tahes täht aj esineb ainult ühel si-st väljuval serval (järjepidevuse või determinismi tingimus) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3
Automaadid ja sisendsõnad n Antud automaati M korral on selle funktsioonid M ja y. M saab defineerida mitte ainult kõigi sisendtähtede hulgal A, vaid ka kõigi sisendsõnade hulgal A*. n Iga sisendsõna puhul = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk). y (si, aj 1 aj 2. . . ajk) = y((… (si, aj 1), aj 2), . . . , ajk-1), ajk).
Näide: automaadid ja sisestussõnad Näide: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2) , 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) \u003d N, y S 2, N S 3, Y S 3 "001" S 1, N S 0, N
Automaatne kaardistamine n Fikseerime M-s algoleku S 0 ja iga sisendsõna jaoks = a 1 a 2. . . ak omistame väljundtähestikus sõna: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1... ak). (3 a) n Seda vastavust, mis vastendab sisendsõnad väljundsõnadeks, nimetatakse automaatseks vastendamiseks n Kui sõnale operaatori rakendamise tulemus on väljundsõna, siis tähistatakse seda vastavalt M() = .
Näide: Automaatne vastendamine Määrame väljundtähestiku sõnale sisendsõna = 0101: = y (S 0, 0) y(S 0, 01)y(S 0, 0101). y (S 0, 0) = N, y 0 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y 1 S 3 "001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S) 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN
Automaadi kuvamise omadused 1) sõnad ja = M() on sama pikkusega: | | = | | (pikkuse säilimise omadus); 2) kui = 1 2 ja M(1 2) = 1 2, kus | 1| = | 1|, siis M(1) = 1; teisisõnu on i pikkuse lõigu kujutis võrdne sama pikkusega kujutise segmendiga.
Automaatide tüübid n Lõpliku automaati (S-finite) üldmudelit, mida käsitleti varem, nimetatakse Mealy automaatiks. n Automaadi nimetatakse autonoomseks, kui selle sisendtähestik koosneb ühest tähest: A=(a). Kõik autonoomse automaadi sisendsõnad on kujul aa. . . a. n Lõplikku automaati nimetatakse Moore'i automaatiks, kui selle väljundfunktsioon sõltub ainult olekutest, st mis tahes s, ai korral aj y(s, ai) = y(s, aj). Moore'i automaadi väljundfunktsioon on loomulikult üheargumendiline; seda tähistatakse tavaliselt tähega ja seda nimetatakse märkide funktsiooniks. Moore'i automaadi graafikus on väljund kirjutatud mitte äärtele, vaid ülaossa.
Moore'i automaat n Teoreem: iga Mealy automaati jaoks on olemas samaväärne Moore'i automaat. n Automaatide võimaluste uurimisel piisab Moore'i automaatide kasutamisest. See on mugav, sest Moore’i automaati saab vaadelda kui väljunditeta automaati, mille olekud on mitmeti märgistatud.
Autonoomse automaadi näide SA a S 1 S 3, 0 S 2 S 4, 0 S 3 S 4, 0 S 4 S 7, 0 S 5 S 4, 2 S 6 S 5, 0 S 7 S 6, 1 S 8 S 9, 0 S 9, 1 S S S S S A=(a), B=(0, 1, 2), S= (S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S9)
Eristamatud olekud n Olgu M ja T kaks sama sisend- ja väljundtähestikuga automaati. Automaadi M olek s ja automaadi T olek r on eristamatud, kui mis tahes sisendsõna jaoks M(s,) = T(r,). n Automaadid M ja T nimetatakse eristamatuteks, kui automaati M mis tahes oleku s korral on automaati T olek r, mis ei ole sellest eristatav, ja vastupidi, mis tahes r korral T-st on M-st eristamatu olek s. n Eristamatuid olekuid nimetatakse ekvivalentseteks
Minimaalne automaat n Üleminekut automaadist M samaväärsele automaatile nimetatakse automaati M ekvivalentseks teisenduseks. n Antud automaatiga samaväärsete ja antud omadustega automaatide leidmisel võib tekkida erinevaid probleeme. Sellistest probleemidest on enim uuritud automaadi olekute arvu minimeerimise probleem: M-ga ekvivalentsete automaatide hulgast leidke väikseima olekute arvuga automaat - minimaalne automaat.
Automaatide “töö” aspektid Automaatide “töö” juures võib eristada kahte peamist aspekti: 1) automaatid tunnevad ära sisendsõnad, st vastavad küsimusele, kas sisendisse antud sõna kuulub antud hulka (need on automaatide tuvastajad); 2) automaadid muudavad sisendsõnad väljundsõnadeks, s.t rakendavad automaatide vastendusi (trafoautomaate).
TA metamatemaatika raames n Algoritmide ja formaalsete süsteemide teooria aine metamatemaatika raames - milliseid objekte ja nendel toiminguid tuleks pidada täpselt määratletuks, millised omadused ja võimalused on elementaartoimingute kombinatsioonidel, mida saab ja mida mitte. tehtud nende abiga. n Algoritmide teooria põhirakenduseks on teatud matemaatiliste ülesannete algoritmilise (st täpse ja ühemõttelise) lahendamise võimatuse tõestamine.
Algoritm n Algoritm on ettekirjutus, mis unikaalselt määrab algandmete vajalikuks tulemuseks teisendamise protsessi n Teisendusprotsess ise koosneb elementaarsetest diskreetsetest sammudest, mille rakendamine lõplikult arv kordi viib tulemuseni
Algoritmide põhitüübid n Algoritmide teooria on metateooria, mis uurib algoritmide erinevaid (kvalitatiivseid ja kvantitatiivseid) omadusi. n Kvalitatiivsete omaduste uurimiseks defineeritakse 3 peamist tüüpi algoritme: 1) Rekursiivsed funktsioonid 2) Turingi masin 3) Kanoonilised Postisüsteemid ja Markovi tavaalgoritmid.
Lihtsamad rekursiivsed funktsioonid n S 1(x) = x+1 - funktsioon sõltub ühest muutujast x ja on võrdne x+1-ga. n Sees(x 1…xn) =0 - funktsioon sõltub n muutujast ja on alati võrdne 0-ga. n Imn(x 1…xn) = xm - funktsioon, mis sõltub n muutujast ja on alati võrdne muutuja xm väärtusega
Primitiivne rekursioon n Funktsioon f(x 1…xn+1) saadakse primitiivse rekursiooni algoritmi abil funktsioonidest g(x 1…xn) ja h(x 1…xn+2), kui f(x 1, …xn, 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), kus z=f(x 1, …xn, y) (2) Funktsioon f nimetatakse primitiivseks rekursiivseks , kui seda on võimalik saada kõige lihtsamatest funktsioonidest S 1, On, Imn lõpliku arvu superpositsiooni- ja primitiivsete rekursioonitehtetega.
Näide n Et tõestada, et funktsioon on primitiivne rekursiivne: 1) Vastavalt võrranditele (1) ja (2) defineerige selgelt funktsioonid g() ja h(). 2) Näidake, et g() ja h() on kõige lihtsamad funktsioonid S 1, On, Imn või varem tõestatud primitiivsed rekursiivsed funktsioonid. Ülesanne 26: Tõesta, et funktsioon f(x, y) = x+y on primitiivne rekursiivne Churchi tees: Algoritmiliselt arvutatavate arvfunktsioonide klass ühtib kõigi rekursiivsete funktsioonide klassiga.
Turingi masin n Turingi masin sisaldab: n 1) Välismälu - n lahtrist koosnev lint. Iga i-s lahter on olekus ai. Olekute tähestik on määratud. Lint võib olla mõlemas suunas lõputu. Tühjad olekud jäetakse välja. n 2) Masina sisemälu – seade on hetkel olekus qi. Sisemise oleku tähestik on antud. Algseisund q 1, lõpp q 0 või qz. n 3) Osuti – osutab aktiivsele lahtrile ja liigub mööda linti. n 4) Juhtseade – loeb lahtri märgi, millele osuti osutab. Vastavalt programmile muudab lahtri olekut ja liigutab kursorit.
Olek ja programm MT n Turingi masina olekut nimetatakse sõnaga n n n n a 1…ak-1 qi ak…ar , mis on moodustatud sisemise oleku sümboli sisestamisel jälgitava lahtri ette. Turingi masina programm on käskude komplekt, mida masin saab täita qi aj qi' aj' D, kus qi on masina sisemine olek aj on jälgitava raku olek qi' on masina uus olek aj' on jälgitavasse lahtrisse kirjutatud uus märk D = ( L, R, E) - märgid, mis sümboliseerivad kursori nihutamist ühe lahtri võrra vastavalt vasakule, paremale ja nihke puudumist.
MT näide Harjutus 27: Turingi masina lõppoleku leidmine Algtähestik: A = (0, 1) Siseoleku tähestik: Q = (q 0, q 1, q 2) Programm: ( 1) q 10 q 20 R, 2) q 20 q 01 E, 3) q 11 R, 4) q 21 R ) Algsõna: q 111
Näide MT juhtelement 28 Leidke Turingi masina lõppseisund Algtähestik: A \u003d (0, 1, ) Sisemise oleku tähestik: Q \u003d (q 0, q 1, q 2, q 3) Programm: ( 1 ) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L) A) Algsõna: q 111 1 B) Algsõna: q 11 111
Turingi tees Turingi tees: iga algoritmi A jaoks saab ehitada Turingi masina, mis samade algandmete juures annab samad tulemused mis algoritm A. n Kui 1 q 1 2 1 qz 2, siis ütleme, et masin T töötleb sõna 1 2 sõnaks 1 2 ja tähistab seda T(1 2) = 1 2. n Tähistus T() on masina T tähistus algväärtustega.
Markovi tavaalgoritmid n Markovi tavaalgoritmid (NAM) teisendavad lõpliku pikkusega sõnad üksteiseks, kasutades asendust. n Ülesanne NAM Asendamine Tähestik u v Lõplik asendus u v n Juhtimine 29 Määratakse tavaline Markovi algoritm: Tähestik on vene keele tähestik. Asendusskeem (I U, L U, S M, V B, R T, T R, O X, N A) n Algsõna SLON. n Otsi lõppsõna.
Algoritmide keerukuse hindamine n Oletame, et funktsioonid f(n) ja g(n) mõõdavad kahe algoritmi jõudlust, siis tavaliselt nimetatakse neid aja keerukuse funktsioonideks. Ütleme, et funktsiooni f(n) kasvu järjekord on maksimaalselt g(n) kui on olemas positiivne konstant C, mille puhul | f(n) |
Algoritmide efektiivsus A B C D E n 3 n 2 2 n 2+4 n n 3 2 n 1 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1024 s 100 ms 100 ms 100 ms 20.10 s 30 ms. päeva 10176 sajandit 1000 ms 0,83 h 1 ms
Algoritmide teooria n Algoritmide teooria – liigitab probleeme keerukuse järgi. Sel juhul klassifitseeritakse ainult tuvastusülesanded. n Tuvastamisülesanne on ülesanne, mis vastab küsimusele: kas sisendandmetel on mingi omadus. Meie puhul: sisendandmeteks on graaf, omadus – kas graaf on Hamiltoni?
Klassid P ja NP n Keerukusklass P: on olemas algoritm A, mis lahendab ülesande polünoomses ajas. n Keerukusklass NP - on olemas algoritm A, mis kontrollib pakutud lahendust polünoomilises ajas. n Hamiltoni tsükli ülesanne on välja selgitada, kas antud graafikul G on Hamiltoni tsükkel, mis kuulub NP-klassi.
Näiteid NP-ülesannetest n Boole'i rahuldavuse probleem: uuri antud Boole'i valemist, kas selles on hulk muutujaid, mis muudab selle 1-ks. n Klikiülesanne: uuri antud graafikult, kas on olemas klikke (täielikud alamgraafikud) selles etteantud suurusega . n Hamiltoni tsükli olemasolu probleem graafis. n Lineaarvõrratuste süsteemi täisarvulise lahendi olemasolu.
NP-ülesannete lahendamise võimalus n loendamisega Esialgu pole lahendus teada. Seetõttu on oluline, et iga NP-klassiga seotud probleemi saaks lahendada eksponentsiaalse aja jooksul, loetledes üles kõik n-i võimalikud kombinatsioonid, mis juhtub Hamiltoni tsükli leidmise algoritmis.
Р ja NP seos n Iga ülesanne P-st kuulub NP-le. n Seega sisaldab klass NP klassi P. Praegu ei ole teada, kas klassid P ja NP on samad, kuid enamik eksperte usub, et mitte.
P ja NP suhe n Kui selgub, et P = NP 1) NP ülesanded lahendatakse mõistliku aja jooksul. 2) On mitmeid probleeme, mille puhul kasutatakse teadlikult eksponentsiaalse keerukusega ülesandeid (st eeldatakse, et probleemi ei saa lahendada). Näiteks krüptograafias on avaliku võtmega krüptimise jaotis, mida on peaaegu võimatu dekrüpteerida. Kui äkki P = NP, siis paljud saladused lakkavad olemast sellised.
NP-täielikud probleemid n Kõige kaalukam põhjus arvata, et P ≠ NP on NP-täielike probleemide olemasolu. n Mitteametlikult!!!, ülesanne Q taandub ülesandeks Q′, kui ülesannet Q saab lahendada mis tahes sisendi polünoomilise aja jooksul, eeldades, et ülesande Q′ lahendus mõne muu sisendi jaoks on teada. Näiteks lineaarvõrrandi lahendamise ülesanne taandatakse ruutvõrrandi lahendamise ülesandeks.
NP-täielikud ülesanded n NP-täielikud ülesanded on klassi NP probleem, millele saab taandada mis tahes muu klassi NP ülesande. n NP-täielikud ülesanded moodustavad NP-klassi "kõige raskemate" probleemide alamhulga. Kui mis tahes NP-täieliku ülesande jaoks leitakse polünoomilise lahenduse algoritm, siis saab polünoomilise aja jooksul lahendada mis tahes muud NP-klassi ülesannet. n Kõik loetletud NP-probleemid on NP-täielikud. Sealhulgas Hamiltoni tsükli probleem.
Baranov Viktor Pavlovitš Diskreetne matemaatika. Jaotis 6. Olekumasinadja ametlikud keeled.
31. loeng Sünteesi ülesanne. Elementaarsed autod ja sina
30. loeng LÕPETATU AUTOMATA MÄÄRATLUS JA MEETODID.
SÜNTEESI PROBLEEM. ELEMENTARY AUTOMAATID
Loengu kava:
1. Lõpliku automaadi definitsioon.
2. Lõpliku automaati defineerimise meetodid.
- Automaadi sünteesi probleem.
- Elementaarsed masinad.
- Automaadi aluse täielikkuse probleem.
- Automaadi sünteesi kanooniline meetod.
- Oleku masina määratlus
SFE ei võta arvesse tõsiasja, et reaalsed seadmed töötavad õigel ajal. Võrreldes SFE-ga on lõplik automaat diskreetmuunduri täpsem mudel. b infoarendaja. Samal ajal on piiratud automaadi kontseptsioon nagu iga mudel ma kuid mitmete lihtsustavate eeldustega.
Esiteks eeldatakse, et automaadi sisend ja väljund võivad igal ajahetkel olla ainult ühes piiratud arvust erinevatest olekutest. Kui päris b Kui muunduril on pidev sisendsignaal, siis selle kirjeldamiseks lõpliku automaati abil on vaja see signaal kvantifitseerida. Automaadi formaalses definitsioonis nimetatakse automaadi sisend- ja väljundolekute lõplikku hulka coo t vastutustundlikult sisendi ja väljundtähestik, ja üksikud osariigid nende alfade ja vitide tähed.
Teiseks eeldatakse, et aeg muutub diskreetselt. Sisend- ja väljundolekud vastavad diskreetsele ajajadale. b Kuna ajahetke määrab üheselt selle indeks, siis lihtsuse huvides eeldame, et aeg võtab väärtused 1, 2, ..., ... Ajavahemikku nimetatakse taktitunne.
Masina tööpõhimõte on esitatud järgmiselt.
Automaadi sisend võtab vastu signaale sisendtähestikust, mis toob kaasa signaalide ilmumise sisendtähestiku väljundisse. Z a Väljundjada sõltuvus sisendjadast oleneb automaadi sisemisest struktuurist. Pange tähele, et erinevalt SFE-st, millel pole mälu, on automaat eel d on mäluga seade, st automaadi väljund määratakse mitte ainult b sissepääsuni, aga ka tagalugu. Ajaloo raamatupidamine ma määrab väljundsignaali sõltuvus mitte ainult sisendist, vaid ka praegusest olekust, mida me tähistame.
Anname automaadi formaalse definitsiooni.
olekumasinnimeta viis objekti
, (1)
kus
sisestustähestik; – üks võimalikest sisendolekutest;
on lõplik hulk, mida nimetatakseväljundtähestik; element selle komplekti võimalikud väljundseisundid määrate teie;
on lõplik hulk, mida nimetataksesiseolekute tähestik I nii;
ülemineku funktsioonmasin: ; see funktsioon määrab igale "sisend-olek" paarile oleku;
- väljundfunktsioon masin: ; see funktsioon seob iga sisend-oleku paari väljundväärtusega.
Automaadi toimimise seadus: automaat muudab oma olekuid vastavalt t funktsiooni ja genereerib väljundsignaale vastavalt funktsioonile tegevusele:
- Olekumasina määratlemise viisid
1. Tabelite määramise meetod. Kuna funktsioonide ja ulatuse jaoks e väärtused ja väärtused kuuluvad lõplikku hulka, siis määratakse need tabelite abil.
Näide 1 Automaadi defineerime järgmiselt: , Defineerime funktsiooni kasutadeshüppelauad,ja funktsioon koos väljumise tabelid.
Tabel 1. Hüppetabel Tabel 2. Väljunditabel
|
Sissepääs |
osariik |
||
|
Sissepääs |
osariik |
||
Kui on teada signaalide jada automaadi sisendis, siis tabelid e liigutused ja väljumised määrab üheselt väljundjärjestuse.
2 . Graafiline seadistusviis. kasutatud ülemineku-väljundi diagramm.See on suunatud multigraaf, milles iga sisemine t tipp vastab automaadi varasele olekule. Automaadi üleminekud olekust olekusse on kujutatud nooltega, millest igaühele on kirjutatud sisendsümbol. s kutsudes seda üleminekut ja automaati genereeritud väljundsümbolit.
| | |
Joon.1 Üleminekute-väljundite skeem
Näide 2 On vaja ehitada automaat, mis töötaks järgmiselt a zom: igas tsüklis võetakse terminite järgmised kahendnumbrid vastu automaati sisendis ja sisse tomat annab nende summale vastava kahendnumbri. Kahele h meil on rea terminid: , .
Automaat on olekus 1, kui eelmiste numbrite liitmisel on ja kannab kaasas kandmist ja olekus 0 muidu. Ülemineku-väljumise diagramm ja zana joonisel fig. 2.
00|0 11|1 01|0
01|1 10|0
10|1 00|1 11|1
Riis. 2
- Automaadi sünteesi probleem
Analoogiliselt SFE sünteesimise probleemiga võib püstitada automaatse sünteesi probleemi. a seltsimees Põhiautomaate on piiramatul hulgal. On vaja kokku panna etteantud töövõimega automaat. Sel juhul põrkub sünteesi probleem t teatud probleemidega.
Oletame, et peate ühendama automaadi väljundi automaadi sisendiga. See on võimalik tingimusel, et teisiti umbes sülemimasin ei saa esimesest tulevatest signaalidest aru. See toob kaasa segaduse ja olukordi, kus mõned ühendused pole võimalikud.
Selle takistuse ületamiseks võetakse kasutusele konstruktsiooniautomaadi kontseptsioon, milles umbes kõik tähestikud (sisend, väljund ja siseolekud) on kodeeritud kahendsõnadega.
Laskma olla piiratud hulk elemente, ja on hulk e pikkusega kahendsõnade hulk, kus. Kutsutakse välja suvaline süstitav kaardistaminekomplekti kodeerimine kahendsõnadega.
Kodeerime suvalise automaati tähestikud:
Tähistame vastavalt automaadi kodeeritud sisendit, väljundit ja olekut ajahetkel. Seejärel esitatakse vormis toimimisseadus
(2)
Pärast kodeerimist saadud automaati kutsutakse struktuurne . Eeldame, et struktuurautomaadil on kahendsisendid, binaarsed väljundid ja automaadi sisemine olek on antud pikkusega kahendsõnaga. Joonisel fig. 3 näidatud abstraktne automaat ja sellele vastav ehitusautomaat.
… …
Riis. 3
Üleminek struktuursele automaatile annab sünteesiks kaks olulist eelist. e stva.
1 . Sisendite ja väljundite ühilduvus, kuna binaarne ja n moodustamine. Konstruktsiooniautomaatidest me ei anna ahela üldist määratlust - see sarnaneb SFE-ga.
2 . Kirjutame seosed (2) “koordinaatidesse”:
(3)
(3) järeldub, etkonstruktsiooniautomaadi talitlusseadus on antud koos ja Boole'i funktsiooni tüvi.
- Elementaarsed automaadid
Toome välja kõige lihtsamad ehitusautomaadid ja anname neile nime.
Kõigepealt pange tähele, et funktsionaalset elementi, millel on ainult üks olek, võib pidada ilma mäluta automaatiks.
Liigume edasi kahe olekuga automaatide juurde. Olgu automaadil üks kahendsisend ja üks kahendväljund, mis langevad kokku sisemise olekuga: :
Riis. 4.
Joonisel fig. näidatud automaadi seadistamiseks. 4, piisab, kui täpsustada ainult tabel p e üleminekud:
Tabel 3
|
Sissepääs |
osariik |
|
Tärnide asemel peate panema 0 ja 1. Seda saab teha 16 viisil, kuid mitte kõik pole vastuvõetavad. Oletame näiteks, et tabeli 3 esimeses veerus on mõlemad elemendid n sa oled null. Selline automaat, olles jõudnud olekusse 0, ei välju sellest enam, see tähendab, et see töötab funktsionaalse elemendina. Sarnaste olukordade analüüs näitab, et selleks, et saada automaat, mis ei ole taandatav ilma mäluta automaadiks, on vaja nõuda umbes tagamaks, et iga tabeli 3 veerg sisaldab nii nulli kui ka ühte. Sellised tabelid on ego h e rehv.
Tabel 4 Tabel 5
|
Sissepääs |
osariik |
|||||
|
Sissepääs |
osariik |
|||||
Tabel 6 Tabel 7
|
Sissepääs |
osariik |
|
|
Sissepääs |
osariik |
|
Meil on ainult kaks kõige lihtsamat automaati, kuna 7 saadakse 4-st ja 6 5-st siseolekute ümberpööramise teel.
Tabelis 4 toodud automaati nimetatakse viivitus või päästik:
ehk see automaat lükkab signaali ühe tsükli võrra edasi.
Tabelis 5 nimetatud automaati kutsutaksepäästik loenduri sisendiga või -päästik . Automaadi olek muutub vastupidiseks, kui sisend on 1, ja jääb muutumatuks, kui sisend on 0:
Laske esialgsel ajal- triger on olekus 0. Kui n e millisel ajahetkel- triger on olekus 0, see tähendab, et automaadi sisendisse on laekunud paarisarv üheseid. Kui olekus 1, siis paaritu. Nii et arr ja zom, - päästik loeb ühikute arvu sisendis, kuid kuna sellel on ainult kaks olekut ma niya, siis loeb kaheni.
Päästikute füüsilisel rakendamisel kasutatakse kahte väljundit: otsene ja tagurpidi (joonis 5). Kui me need ära vahetame, siis- päästik, saate tabelis 7 määratud automaati ja alates- päästik - tabelis 6 määratud automaat.
Riis. 5.
- Automaadi aluse täielikkuse probleem
Struktuursete automaatide komplekti nimetatakse täielikuks (või automaatiks b a zisom), kui neist on võimalik konstrueerida mis tahes etteantud struktuurne automaat.
Matemaatikute jõupingutusi automaatide jaoks Posti teoreemi analoogi saamiseks ei suurendata. n tabas edu. Aastal 1964 M.I. Tõestas lühidalt määramisalgoritmi puudumist e süsteemi täielikkus. Sel juhul pakuvad huvi täielikkuse teoreemi variandid koos täiendavate eeldustega süsteemi kohta. Vaatleme neist kõige populaarsemat.
Teoreem. automaatne süsteem,sisaldab täiskomplekti PV ja -päästik (või -trigger) on lõpetatud.
Tõestus. Vaatleme seosega antud suvalist automaati e (2) ja kirjeldage selle näidatud automaatide skeemi, mida nimetataksekanooniline struktuur(joonis 6) .
Skeem koosneb kahest osast.
…
…
…
Riis. 6.
Vasakut poolt nimetatakse mäluosaks. See koosneb trigeritest, mille olekute hulk moodustab automaadi oleku: kui hetkel
, …,
siis see tähendab, et automaat on olekus.
Paremat poolt nimetatakse kombineeritud osaks ja see tähistab SFE-d. Selle vooluahela sisendid on:
- kahendsõna - automaadi sisendsignaal;
- kahendsõna on automaadi hetkeline sisemine olek.
Väljundid:
- binaarsõna - automaati väljundsignaal, mida rakendatakse t valemite (3) järgi;
- kahendsõna, mis sisestab mällu trigerite sisendid a praegune osa ja juhib masina mälu.
Näitame, et mälu juhtsignaalid on samade muutujate Boole'i funktsioonid nagu automaati väljund, mis tähendab, et neid saab täielikult realiseerida ja FE tüvi.
Igal ajahetkel peavad mälu juhtsignaalid tõlkima a sisse tomat osariigist osariiki. Selleks peate muutma iga päästiku olekut
, .
Kanoonilises skeemis kasutatavatel -päästikutel või -päästikutel on järgmised e järgmine omadus: iga olekupaari jaoks on sisendsignaal, e masinaga osariigist osariiki sõites. Tähistame seda signaali tähega . -triggeri puhul, kuna olek, milles -triger on seatud, on võrdne sisendsignaaliga. -trigger: kui peate sisestama n umbes anna 0 oleku muutmata jätmiseks; -1 juures, et päästikut pöörata.
Niisiis, või vektorkujul
Väljendagem automaadi talitlusseadusest (2). Siis
Teoreem on tõestatud.
- Automaadi sünteesi kanooniline meetod
Vaatleme seda meetodit konkreetsel näitel.
Näide. Konveieril, mida mööda liiguvad ja paigaldatakse kahte tüüpi osad sisse linamasin, mille ülesandeks on osade sorteerimine nii, et pärast möödumist e masinast möödudes moodustasid nad rühmad. Vale osa masina sta l noogutab konveierilt. Sellise automaadi vooluring on vajalik -trigeri ja elementide "AND", "OR", "NOT" abil.
Automaadi süntees on jagatud järgmisteks etappideks.
1 . Abstraktse automaadi ehitamine.
Sisestustähestik on . Väljundtähestik on , kus C - detaili kokkupõrge, P on tema pass. Automaadi siseolekud peegeldavad tema mälu selle kohta, millise rühma osa ta on juba moodustanud: . Rühma moodustamisel liigub automaat tsükliliselt läbi nende olekute, muutmata olekut, kui saabub sobimatu osa. Ülemineku-väljundi diagramm on näidatud joonisel fig. 7.
| | |
Riis. 7.
2 . Tähestiku kodeerimine.
Järgnevalt on toodud üks võimalikest kodeerimisvalikutest. e laudade puhumine.
Sisendväljundi olek
3 . Automaadi kanoonilise struktuuri ehitamine.
Arendatava automaadi kanooniline struktuur on näidatud joonisel fig. kaheksa.
Riis. kaheksa.
Leiame SFE väljundite sõltuvused muutujatest esmalt tabelina (tabel 8), vastavalt k umbes mille valemid hiljem koostame
, .
Tabel 8
Neid funktsioone nimetatakseosaliselt määratletud, kuna neid ei määratleta aadressil. Nende funktsioonide esitamiseks valemitega defineeritakse need ümber nii, et saadakse valemite lihtsam vorm.
4 . Automaadi väljundfunktsioonide ja mäluhaldusfunktsioonide kujutamine r muulad.
Kasutades Boole'i funktsioonide minimeerimise meetodeid, ehitame võimalusel ek umbes Funktsioonide nominaalne esitus, valemid aluses:
5 . SFE teostus ja automaadi lõplik skeem (joon. 9).
Riis. üheksa.
SFE
SFE
MITTE
VÕI
Kombineeritud skeemid, kuigi need võimaldavad teil rakendada mis tahes fikseeritud sisend- ja väljundsignaalide vahelised sõltuvused ei saa muuta nende käitumise olemust (st andmetöötluse järjekorda) - iga selline muutus eeldab ahela struktuuri muutmist, st tegelikult üleminekut teisele vooluringile. Töö ümberstruktureerimise probleemi on võimalik lahendada ilma skeemi struktuuri muutmata, kui sellesse sisse viia mäluelemendid, mis võimaldaks fikseerida ja salvestada seadme vaheolekuid - sel juhul ei sõltu väljundsignaal mitte ainult sisendsignaalist, vaid ka vooluringi olekust. Kui selliste elementide arv on lõplik, siis, nagu eespool mainitud, kutsutakse diskreetne seade otsa masin.
olekumasinnimetatakse süsteemiks
Nagu varem öeldud, Y (x, q) määrab sisendsümbolite teisendamise järjekorra ja eelmise tsükli automaati oleku järgmise tsükli olekusse, a Q (x, q) - sisendsümbolite ja automaadi oleku muutmine jooksval tsüklil väljundsümboliks. Kui a q 0 on automaadi algseisund ja i- mõõta number, siis selle tööd kirjeldab süsteem:
Neid suhteid nimetatakse kanooniliste võrrandite süsteemid lõplik automaat. Saate neid kasutada alates q 0, järjestikku leida automaati ja väljundsümbolite kõik järgnevad olekud.
Masinaid on kahte tüüpi - esialgne ja mittealguline. AT algautomaatidel on fikseeritud algseisund (st nad algavad alati samast olekust q0). Mittealgsetes automaatides mis tahes komplektist K; see valik määrab ära automaadi edasise käitumise.
Konkreetse lõpliku automaati esitus taandatakse tegelikult seda defineerivate automaati funktsioonide kirjelduseks. Süsteemist (9.3) järeldub, et lõpliku arvu võimalike siseolekute korral osutub ka automaati funktsioonide võimalike väärtuste arv lõplikuks. Neid saab kirjeldada mitmel viisil, millest levinuim on tabelikujuline ja abiga diagrammid.
AT tabelikujuline viis automaatfunktsioonid on antud kahe lõpliku tabeliga, mis on vastavalt nimetatud üleminekumaatriks ja väljundmaatriks. Nendes tabelites on read tähistatud sisendtähestiku tähtedega ja veerud sisemise tähestiku tähtedega (automaati sisemist olekut kodeerivad sümbolid). Üleminekumaatriksis rea ristumiskohas (xk) ja veerg (qr) funktsiooni Y väärtused asetatakse ( q r, x k), a väljundite maatriksis - funktsiooni Q väärtused (q r , x k).
Baranov Viktor Pavlovitš Diskreetne matemaatika. Jaotis 6. Lõplikud automaadid ja formaalsed keeled.
31. loeng Sünteesi ülesanne. Elementaarsed automaadid
30. loeng
SÜNTEESI PROBLEEM. ELEMENTARY AUTOMAATID
Loengu kava:
1. Lõpliku automaadi definitsioon.
2. Lõpliku automaati defineerimise meetodid.
- Automaadi sünteesi probleem.
- Elementaarsed masinad.
- Automaadi aluse täielikkuse probleem.
- Automaadi sünteesi kanooniline meetod.
- Oleku masina määratlus
SFE ei võta arvesse tõsiasja, et reaalsed seadmed töötavad õigel ajal. Võrreldes SFE-ga on lõplik automaat diskreetse teabe muunduri täpsem mudel. Samal ajal on lõpliku automaadi mõiste, nagu iga mudel, seotud mitmete lihtsustavate eeldustega.
Esiteks eeldatakse, et automaadi sisend ja väljund võivad igal ajahetkel olla ainult ühes piiratud arvust erinevatest olekutest. Kui reaalsel muunduril on pidev sisendsignaal, siis selle kirjeldamiseks lõpliku automaati abil on vaja see signaal kvantifitseerida. Automaadi formaalses definitsioonis nimetatakse automaati sisend- ja väljundseisundite lõplikku kogumit vastavalt sisend- ja väljundtähestikuks ning üksikuid olekuid nende tähestike tähtedeks.
Teiseks eeldatakse, et aeg muutub diskreetselt. Sisend- ja väljundolekud vastavad diskreetsele ajajadale Kuna ajahetke määrab üheselt selle indeks, siis lihtsuse huvides eeldame, et aeg võtab väärtused 1, 2, ..., ... Ajavahemikku nimetatakse taktiks.
Masina tööpõhimõte on esitatud järgmiselt.
Automaadi sisend võtab vastu signaale sisendtähestikust, mis toob kaasa signaalide ilmumise sisendtähestiku väljundisse. Väljundjada sõltuvus sisendjadast oleneb automaadi sisemisest struktuurist. Pange tähele, et erinevalt SFE-st, millel pole mälu, on automaat mäluga seade, st automaadi väljundi määrab mitte ainult sisend, vaid ka eellugu. Eelajalugu arvestab väljundsignaali sõltuvus mitte ainult sisendist, vaid ka praegusest olekust, mida me tähistame.
Anname automaadi formaalse definitsiooni.
Olekumasin on viiest objektist koosnev komplekt
on lõplik hulk, mida nimetatakse sisendtähestikuks; – üks võimalikest sisendolekutest;
on lõplik hulk, mida nimetatakse väljundtähestikuks; selle komplekti elemendid määratlevad võimalikud väljundseisundid;
on lõplik hulk, mida nimetatakse siseolekute tähestikuks;
– automaatse ülemineku funktsioon: ; see funktsioon määrab igale "sisend-olek" paarile oleku;
– masina väljundite funktsioon: ; see funktsioon seob iga sisend-oleku paari väljundväärtusega.
Automaadi toimimise seadus: automaat muudab oma olekuid vastavalt funktsioonile ja genereerib väljundsignaale vastavalt funktsioonile:
- Olekumasina määratlemise viisid
1. Tabelikujuline seadistusviis. Kuna funktsioonide puhul kuuluvad nii ulatus kui ka väärtused lõplikku hulka, määratakse need tabelite abil.
Näide 1. Defineerime automaati järgmiselt: , Defineerime funktsioon üleminekutabeli abil ja funktsioon - väljundtabeli abil.
Tabel 1. Hüppetabel Tabel 2. Väljunditabel
|
osariik |
|||
|
osariik |
|||
Kui signaalide jada automaadi sisendis on teada, siis on väljundjada üheselt määratud üleminekute ja väljundite tabelitega.
2. Graafiline seadistusviis. Kasutatakse ülemineku-väljundi diagrammi. See on suunatud multigraaf, milles automaati igale siseolekule vastab üks tipp. Automaadi üleminekud olekust olekusse on kujutatud nooltega, millest igaühele on kirjutatud seda üleminekut põhjustav sisendsümbol ja automaadi genereeritud väljundsümbol.
Joon.1 Üleminekute-väljundite skeem
Näide 2. Vajalik on ehitada automaat, mis töötaks järgmiselt: igas tsüklis võetakse automaati sisendis vastu terminite järgmised kahendnumbrid, automaat genereerib nende summale vastava kahendkoha. Kahekohaliste terminite jaoks on meil: , .
Automaat on olekus 1, kui eelmiste numbrite lisamise ajal toimub edasikandmine, ja muidu olekus 0. Ülemineku-väljundi diagramm on näidatud joonisel fig. 2.
- Automaadi sünteesi probleem
Analoogiliselt SFE sünteesi probleemiga võib püstitada automaatide sünteesiprobleemi. Põhiautomaate on piiramatul hulgal. On vaja kokku panna etteantud töövõimega automaat. Samal ajal on sünteesi ülesandel teatud probleemid.
Oletame, et peate ühendama automaadi väljundi automaadi sisendiga. See on tingimusel võimalik, kuna vastasel juhul ei saa teine automaat esimesest tulevatest signaalidest aru. See toob kaasa segase olukorra, kus mõned ühendused pole võimalikud.
Selle takistuse ületamiseks võetakse kasutusele struktuurse automaati kontseptsioon, milles kõik tähed (sisend, väljund ja siseolekud) on kodeeritud kahendsõnades.
Laskma olla piiratud hulk elemente ja olla hulk kahendsõnu pikkusega, kus. Suvalist süstivat vastendamist nimetatakse komplekti kodeerimiseks kahendsõnadega.
Kodeerime suvalise automaati tähestikud:
Tähistame vastavalt automaadi kodeeritud sisendit, väljundit ja olekut ajahetkel. Seejärel esitatakse vormis toimimisseadus
Pärast kodeerimist saadud automaati nimetatakse struktuurautomaatiks. Eeldame, et struktuurautomaadil on kahendsisendid, binaarsed väljundid ja automaadi sisemine olek on antud pikkusega kahendsõnaga. Joonisel fig. Joonisel 3 on kujutatud abstraktne automaat ja sellele vastav struktuurautomaat.
Üleminek struktuursele automaatile annab sünteesiks kaks olulist eelist.
1. Sisendite ja väljundite ühilduvus, kuna nende kaudu edastatakse kahendinformatsiooni. Konstruktsiooniautomaatidest me ei anna ahela üldist määratlust - see sarnaneb SFE-ga.
2. Kirjutame seosed (2) "koordinaatidesse":
(3) järeldub, et struktuurse automaati toimimise seadus on antud Boole'i funktsioonide süsteemiga.
- Elementaarsed automaadid
Toome välja kõige lihtsamad ehitusautomaadid ja anname neile nime.
Kõigepealt pange tähele, et funktsionaalset elementi, millel on ainult üks olek, võib pidada ilma mäluta automaatiks.
Liigume edasi kahe olekuga automaatide juurde. Olgu automaadil üks kahendsisend ja üks kahendväljund, mis langevad kokku sisemise olekuga: :
Joonisel fig. näidatud automaadi seadistamiseks. 4, piisab ainult üleminekutabeli määramisest:
Tabel 3
|
osariik |
||
Tärnide asemel peate panema 0 ja 1. Seda saab teha 16 viisil, kuid mitte kõik pole vastuvõetavad. Oletame näiteks, et tabeli 3 esimeses veerus on mõlemad elemendid nullid. Selline automaat, olles jõudnud olekusse 0, ei välju sellest enam, see tähendab, et see töötab funktsionaalse elemendina. Sarnaste olukordade analüüs näitab, et selleks, et saada automaat, mis ei ole taandatav ilma mäluta automaadiks, on vaja nõuda, et tabeli 3 igas veerus esineksid nii null kui ka üks. Selliseid tabeleid on ainult neli.
Tabel 4 Tabel 5
|
osariik |
||||||
|
osariik |
||||||
Tabel 6 Tabel 7
|
osariik |
||
|
osariik |
||
Meil on ainult kaks kõige lihtsamat automaati, kuna 7 saadakse 4-st ja 6 5-st siseolekute ümberpööramise teel.
Tabelis 4 antud automaati nimetatakse viivituseks või -trigeriks:
ehk see automaat lükkab signaali ühe tsükli võrra edasi.
Tabelis 5 nimetatud automaati nimetatakse loendussisendiga trigeriks või -trigeriks. Automaadi olek muutub vastupidiseks, kui sisend on 1, ja jääb muutumatuks, kui sisend on 0:
Olgu -triger algsel ajahetkel olekus 0. Kui mingil ajahetkel on -triger olekus 0, siis see tähendab, et automaadi sisendisse on saadud paarisarv 1. Kui olekus 1, siis paaritu. Seega -triger loendab ühikute arvu sisendis, kuid kuna sellel on ainult kaks olekut, siis loeb see kuni kaks.
Päästikute füüsilises teostuses kasutatakse kahte väljundit: otsene ja pöördvõrdeline (joon. 5). Kui neid vahetada, siis -trigerist saame tabelis 7 määratud automaati ja -trigerist - tabelis 6 määratud automaati.
- Automaadi aluse täielikkuse probleem
Struktuursete automaatide komplekti nimetatakse terviklikuks (või automaatikaaluseks), kui neist saab konstrueerida suvalise struktuuriautomaati.
Matemaatikute katsed saada automaatide jaoks Posti teoreemi analoogi olid ebaõnnestunud. Aastal 1964 M.I. Tõestas lühidalt süsteemi terviklikkuse määramise algoritmi puudumist. Sel juhul pakuvad huvi täielikkuse teoreemi variandid koos täiendavate eeldustega süsteemi kohta. Vaatleme neist kõige populaarsemat.
Teoreem. Automaatide süsteem, mis sisaldab täielikku FE-de komplekti ja -triggerit (või -triggerit), on valmis.
Tõestus. Vaatleme suhetega (2) antud suvalist automaati ja kirjeldame selle näidatud automaatide skeemi, mida nimetatakse kanooniliseks struktuuriks (joonis 6).
Skeem koosneb kahest osast.
Vasakut poolt nimetatakse mäluosaks. See koosneb trigeritest, mille olekute hulk moodustab automaadi oleku: kui hetkel
siis see tähendab, et automaat on olekus.
Paremat poolt nimetatakse kombineeritud osaks ja see tähistab SFE-d. Selle vooluahela sisendid on:
- kahendsõna - automaadi sisendsignaal;
- kahendsõna on automaadi hetkeline sisemine olek.
- kahendsõna - automaadi väljundsignaal, mis realiseeritakse valemite (3) järgi;
- kahendsõna, mis sisestab salvestusosas trigerite sisendid ja juhib automaadi mälu.
Näitame, et mälu juhtsignaalid on samade muutujate Boole'i funktsioonid nagu automaati väljund, mis tähendab, et neid saab realiseerida tervikliku FE süsteemiga.
Igal ajahetkel peavad mälu juhtsignaalid automaati olekust olekusse üle kandma. Selleks peate muutma iga päästiku olekut
Kanoonilises skeemis kasutatavatel -trigeritel või -trigeritel on järgmine omadus: mis tahes olekupaari jaoks on sisendsignaal, mis kannab automaati olekust olekusse. Tähistame seda signaali tähega . -triggeri puhul, kuna olek, milles -triger on seatud, on võrdne sisendsignaaliga. For -trigger: millal, tuleb sisendile rakendada 0, et olek ei muutuks; -1 juures, et päästikut pöörata.
Niisiis, või vektorkujul
Väljendagem automaadi talitlusseadusest (2). Siis
Teoreem on tõestatud.
- Automaadi sünteesi kanooniline meetod
Vaatleme seda meetodit konkreetsel näitel.
Näide. Konveierile, mida mööda liiguvad kahte tüüpi osad ja, on paigaldatud automaat, mille ülesandeks on sorteerida osad nii, et need pärast masinast möödumist moodustaksid rühmad. Masin lükkab ebasobiva osa konveierilt maha. Sellise automaadi vooluring on vajalik -trigeri ja elementide "AND", "OR", "NOT" abil.
Automaadi süntees on jagatud järgmisteks etappideks.
1. Abstraktse automaadi ehitamine.
Sisestustähestik on . Väljundtähestik on , kus C on detaili kokkupõrge, P on selle vahelejätmine. Automaadi siseolekud peegeldavad tema mälu selle kohta, millise rühma osa ta on juba moodustanud: . Rühma moodustamisel liigub automaat tsükliliselt läbi nende olekute, muutmata olekut, kui saabub sobimatu osa. Ülemineku-väljundi diagramm on näidatud joonisel fig. 7.
2. Tähestiku kodeerimine.
Üks võimalikest kodeerimisvalikutest on näidatud järgmistes tabelites.
Sisendväljundi olek
3. Automaadi kanoonilise struktuuri konstrueerimine.
Arendatava automaadi kanooniline struktuur on näidatud joonisel fig. kaheksa.
SFE väljundite sõltuvused muutujatest leiame esmalt tabelina (tabel 8), mille abil konstrueerime edasi valemeid
Tabel 8
Neid funktsioone nimetatakse osaliselt määratletuks, kuna neid ei määratleta aadressil. Nende funktsioonide esitamiseks valemitega defineeritakse need ümber nii, et saadakse valemite lihtsam vorm.
4. Automaadi väljundfunktsioonide ja mälu juhtimise funktsioonide kujutamine valemitega.
Kasutades Boole'i funktsioonide minimeerimise meetodeid, koostame funktsioonide ökonoomse esituse võimaluse korral valemite alusel:
5. SFE teostus ja automaadi lõplik skeem (joon. 9).
LÕPETATU AUTOMATA MÄÄRATLUS JA MEETODID. SÜNTEESI PROBLEEM. ELEMENTARY AUTOMAATID
Automaatide teooria on diskreetse matemaatika osa, mis uurib diskreetsete teabemuundurite mudeleid. Sellised muundurid on nii reaalsed seadmed (arvutid, elusorganismid) kui ka kujuteldavad seadmed (aksiomaatilised teooriad, matemaatilised masinad). Sisuliselt võib lõpliku oleku masinat kirjeldada kui seadet M , millel on sisend- ja väljundkanalid, samas kui igal diskreetsel ajal, mida nimetatakse kella hetkedeks, on see ühes lõppolekus.
Sisendkanalil igal ajal t =1, 2, ... seadmesse M saabuvad sisendsignaalid (mingist lõplikust signaalide hulgast). Olekumuutuse seadus järgmisele ajahetkele seatakse sõltuvalt sisendsignaalist ja seadme olekust antud ajahetkel. Väljundsignaal sõltub olekust ja sisendsignaalist praegusel ajal (joonis 1).
Olekumasin on reaalsete diskreetsete infotöötlusseadmete matemaatiline mudel.
olekumasin nimetatakse süsteemiks A= (X , K , Y , , ), kus X , K , Y on suvalised mittetühjad lõplikud hulgad ja ja - funktsioonid, millest:
trobikond X ={a 1 , ..., a m ) kutsutakse sisestustähestik , ja selle elemendid on sisendsignaalid , on nende järjestused sees lööklaused ;
trobikond K ={q 1 , ..., q n ) kutsutakse paljud osariigid automaat ja selle elemendid - osariigid ;
trobikond Y ={b 1 , ..., b lk ) kutsutakse väljundtähestik , selle elemendid on väljundsignaalid , nende järjestused on väljundsõnad ;
funktsiooni : X K K helistas ülemineku funktsioon ;
funktsiooni :X K Y helistas väljundfunktsioon .
Seega (x , q )K , (x , q )Y eest x X , q K .
Olekumasinaga on seotud kujuteldav seade, mis töötab järgmiselt. See võib olla komplektist pärit olekus K , võtavad vastu seadmest signaale X ja väljastavad komplektist signaale Y .
2. Lõpliku automaati defineerimise meetodid
Abstraktsete automaatide määratlemiseks on mitu samaväärset viisi, millest kolm on: tabelikujuline , geomeetriline ja funktsionaalne .
2.1. Masina tabeli määramine
Automaadi definitsioonist järeldub, et seda saab alati defineerida kahe sisendiga tabeli abil t read ja P veerud, kus veeru ristumiskohas q ja jooned a funktsiooni väärtused on väärt (a i , q j ), (a i , q j ).
|
q a |
q 1 |
q j |
q n |
||
|
a 1 |
(a 1 , q 1), (a 1 , q 1) |
(a 1 , q j ), (a 1 , q j ) |
(a 1 , q n ), (a 1 , q n ) |
||
|
a i |
(a i , q 1), (a i , q 1) |
(a i , q j ), (a i , q j ) |
(a i , q n ), (a i , q n ) |
||
|
a m |
(a m , q 1), (a m , q 1) |
(a m , q j ), (a m , q j ) |
(a m , q n ), (a m , q n ) |
2.2. Automaadi defineerimine Moore'i diagrammi järgi
Teine võimalus lõpliku oleku masina määramiseks on graafiline, st graafiku kasutamine. Automaat on kujutatud märgistatud suunatud graafikuna G(K , D ) paljude tippudega K ja palju kaare D ={(q j , (a i , q j ))| q j K , a i X ), samas kui kaar ( q j , (a i , q j )) on märgistatud paariga ( a i , (a i , q j )). Seega selle meetodi puhul kujutatakse automaadi olekuid ringidega, kuhu sisestatakse olekute sümbolid q j (j = 1, …, n ). Igast ringist viiakse läbi t nooled (suunatud servad) üks-ühele, mis vastavad sisendtähestiku tähemärkidele X ={a 1 , ..., a m ). Tähele vastav nool a i X ja ringist lahkudes q j K , paar ( a i , (a i , q j )) ja see nool viib ringile, mis vastab (a i , q j ).
Saadud joonist nimetatakse automaatgraafik või, Moore'i diagramm . Mitte väga keeruliste automaatide puhul on see meetod illustreeriv kui tabelikujuline.
