Problemos nėštumo metu 

Automatų teorija. Pamoka

Ieškokite medžiagų:

Jūsų medžiagų skaičius: 0.

Pridėkite 1 medžiagą

Sertifikatas
apie kūrybą el. portfelis

Pridėkite 5 medžiagas

Paslaptis
dovana

Pridėkite 10 medžiagų

Diplomas už
švietimo informatizavimas

Pridėkite 12 medžiagų

Apžvalga
ant bet kokios medžiagos nemokamai

Pridėkite 15 medžiagų

Video pamokos
greitai sukurti įspūdingus pristatymus

Pridėkite 17 medžiagų

Dėl pastaraisiais dešimtmečiais buvo ir vyksta intensyvus darbas kuriant
ir įvairių sistemų bei prietaisų naudojimas diskrečiųjų apdorojimui
informacija. Diskretūs informacijos keitikliai yra plačiai naudojami kaip
įvairių rūšių techniniai automatai, skaičiavimo įrenginiai ir jų funkciniai
blokai, roboto valdymo įrenginiai, kurie valdo objektus pagal duotą
algoritmas. Plati tokių keitiklių klasė yra vienijanti bendruoju pavadinimu
automatai. Šie įrenginiai turi ribotą skaičių įvesčių, kurios priima informaciją,
ir baigtinis skaičius išėjimų apdorotai informacijai išduoti. Santykiai tarp
įvestis ir išvestis pateikiami pagal nustatytą informacijos apdorojimo algoritmą.
Įvesties ir išvesties informacija pavaizduota simboliais, fizinėmis laikmenomis
kurie yra laiko kvantuoti signalai.
Jei "K" simboliai vienu metu po lygiagrečios įvesties arba išvesties
kanalus, bus traktuojami kaip vienas simbolis iš atitinkamos abėcėlės
į vieną „priklijuotą“ kanalą, tuomet tokį automatą galima pavaizduoti kaip įrenginį su
vienas įėjimas ir vienas išėjimas (1 pav.).
Fig.1 - Bendrasis diskrečiosios informacijos keitiklio funkcinis modelis
Yra du automato termino apibrėžimo būdai. Iš pradžių interpretuojama
kaip prietaisas, kuris, tiesiogiai nedalyvaujant asmeniui, atlieka funkcijas
priimti, konvertuoti ir perduoti energiją, informaciją ir kt. pagal
joje įdėta programa, o antroji – kaip matematinis tikrojo modelis
diskretieji informacijos keitikliai. Jo veikimas yra
baigtinių arba apskritai begalinių simbolių seka z1,z2,...
abėcėlės Z, patekusi į įvestį, savo išvestyje sukelia tam tikrą
tos pačios ar kitos abėcėlės simbolių seka w1,w2,.... Šiuo būdu,
bendriausias matematinis diskrečiosios informacijos keitiklio modelis yra
sekos funkcija, rodanti visų sekų Z rinkinį
abėcėlės Z simbolius į kitą W abėcėlės simbolių sekų rinkinį W*.
Šis aiškinimas leidžia schematiškai pavaizduoti keitiklį kaip įrenginį,
realizuojant vienos aibės susiejimą su kita (2a pav.).

Fig.2a – formalus keitiklio modelis
Šis žemėlapių sudarymas vadinamas abėcėliniu žemėlapiu arba abėcėliniu
operatorius.
Automatų teorija yra valdymo sistemų teorijos šaka, tirianti matematiką
diskrečiųjų informacijos keitiklių modeliai, vadinami automatais. NUO
tam tikru požiūriu tokie keitikliai yra kaip tikri įrenginiai
(kompiuteriai, gyvi organizmai) ir abstrakčios sistemos
(pavyzdžiui, formali sistema yra abstrakčių, nesusijusių objektų rinkinys
su išoriniu pasauliu, kuriame pateikiamos veikimo su simbolių rinkiniu taisyklės
griežtai sintaksinė interpretacija neatsižvelgiant į semantinį turinį, t.y.
semantika; aksiomatinės teorijos, apibūdinančios tam tikrą reiškinių rinkinį
jų priežastiniame ryšyje vienas su kitu).
Automatų teorija glaudžiausiai susijusi su algoritmų teorija. Tai paaiškinama faktu
kad automatas diskrečią informaciją žingsniais paverčia diskretiškais momentais
laiko ir generuoja gautą informaciją apie tam tikro algoritmo veiksmus. Šie
transformacijos galimos techninių ir/ar programinių priemonių pagalba. Mašina
gali būti pavaizduotas kaip koks nors įrenginys (juodoji dėžė), prie kurio
imami įėjimai ir išėjimai ir kurie gali turėti tam tikrą vidinį
teigia. Analizuojant automatus, jų elgesys tiriamas esant įvairiems sutrikimams.
įtakoja ir sumažina automato būsenų skaičių dirbant pagal duotybę
algoritmas. Toks automatas vadinamas abstrakčiu, nes abstrahuotas nuo tikrojo
fizinius įvesties ir išvesties signalus, laikydami juos tiesiog kai kurių raidėmis
abėcėlė ir ryšys su idealizuotu diskrečiu laiku. Sintezuojant automatus
(jungimo ar susiejimo procesas) sudaro elementariųjų automatų sistemą,
lygiavertis duotam abstrakčiam automatui. Toks automatas
vadinamas struktūriniu. Ypatingą vietą automatų teorijoje užima baigtinio sąvoka
mašina.
Transformacijos įvesties => išvesties rezultatas (2a pav.) dažnai priklauso ne tik nuo įvesties į
Šis momentas laiko, bet ir iš to, kas buvo anksčiau prie įvesties, iš įvesties istorijos, t.y.
iš transformacijos istorijos. Galimų įvesties istorijų skaičius yra begalinis (skaičiuojamas),
net jei automatas turi baigtinį skaičių skirtingų įvesties informacijos elementų (kaip pvz

galutinis funkcinis keitiklis). Norint kažkaip prisiminti šias istorijas ir
Norėdami atskirti vienas nuo kito, keitiklis turi turėti atmintį. Tam prietaisas
(1.1,6 pav.) įvedama būsenų Q = (qx,q2,...qm) abėcėlė.
Valstybės q samprata čia vaidina labai svarbų vaidmenį. Jų valstybėse mašina
prisimena savo koncentruotą praeitį. Dėl tos pačios įvesties
keitiklis gali reaguoti skirtingai, priklausomai nuo būsenos, kurioje
jis šiuo metu yra.
Baigtinis automatas (2b pav.) – matematinė abstrakcija, leidžianti apibūdinti kelius
pakeisti objekto būseną, atsižvelgiant į jo esamą būseną ir įvesties duomenis,
su sąlyga, kad bendras galimas būsenų Q skaičius ir įvesties signalų rinkinys
Z yra baigtiniai. Baigtinis automatas yra ypatingas abstraktaus automato atvejis.
2b pav. – Būsenos mašina
Būsenos mašina yra viena iš svarbiausių valdymo sistemų tipų.
Pagrindinis baigtinių automatų privalumas yra tai, kad jie natūraliai
taip aprašomos išorinių įvykių valdomos sistemos.
Automatų teorija nagrinėja procesus, vykstančius įvairiuose automatuose
natūra, ir bendrieji modeliai, kuriems jie taikomi, plačiai naudojami tam
algebrinis aparatas, matematinė logika, kombinatorinė analizė ir teorija
tikimybės.
Projektuojant patikimus, gerai veikiančius automatus tenka spręsti nepaprastus
sunkių užduočių. Pavyzdžiui, norint sumažinti, būtina nustatyti sistemų stabilumą
įvairūs automatinių mašinų veikimo nukrypimai. Reikia mokytis ir jautrumo
automatai, nes veikimo procese valdymo sistemų savybės neišlieka
nuolatinis.
Automatų teorija pritaikoma tiek matematikoje, tiek sprendžiant praktines problemas.
užduotys. Pavyzdžiui, pasitelkus automatų teoriją įrodomas kai kurių išsprendžiamumas
formalusis skaičiavimas. Automatų teorijos metodų ir sampratų taikymas studijoms
formalios ir natūralios kalbos paskatino matematikos atsiradimą
lingvistika (matematinė kalbotyra yra matematinė disciplina, dalykas
kuri yra formalaus aparato kūrimas gamtos struktūrai apibūdinti
o kai kurios dirbtinės kalbos.) Automato samprata gali pasitarnauti kaip modelis

objektą atliekant įvairiausias užduotis, o tai leidžia pritaikyti teoriją
automatai įvairiuose moksliniuose ir taikomuosiuose tyrimuose.
Automatų teorijos aktualumas
Yra daug valdymo objektų, susijusių su dideliu
Atsakomybė: branduoliniai ir cheminiai reaktoriai, pramoniniai kompleksai,
gynyba, kosmosas, kasyba. Sėkmės su jais tiesiogiai susidoroti
priklauso nuo veiksmų aiškumo ir nuoseklumo, nuo gebėjimo priimti pagrįstus sprendimus ir
kompetentingai išanalizuoti situaciją, atsižvelgiant į vienareikšmiško aiškinimo galimybę
informacija. Skirtingas objektuose vykstančių fizinių procesų pobūdis, kompleksas
jų ir valdymo sistemų sąveikos pobūdis lemia
valdymo užduočių kūrimo, algoritmizavimo ir programavimo sunkumai. Kilti
sunkumai, susiję su poreikiu pasiekti matomumą ir struktūrą.
Šioms problemoms spręsti naudojamas sukurtas automatų teorijos matematinis aparatas.
Elgesio logikos aprašymas (kokiomis sąlygomis būtina atlikti tam tikrus
veiksmai) automatinio požiūrio struktūroje. Ši savybė daro automatinį
aiškiai ir glaustai apibūdina sudėtingą elgesį. Darbo teisingumas
automatinių mašinų naudojimas yra numatytas projektavimo etape, dėka
grafinis vaizdavimas, t.y.
 vizualiai atvaizduoja valdymo automatų elgesį (grafiškai, lentelėse)
ir kompozicijos iš jų;
 Rodomos norimos būsenos;
 atspindi automato perėjimų iš būsenos į būseną dinamiką ir sąlygas;
 nesunkiai matote galimas dizaino klaidas, pvz., trūkstamas
tam tikras perėjimas, nepasiekiama būsena ir pan.
Visa tai leidžia aiškiai suprasti įrenginio veikimą. valdymo procesai,
dizainai gali būti pavaizduoti kaip elementai, kurių elgesys yra nuspėjamas.
Pavyzdys: vienas didžiausių pasaulyje aviacijos, kosmoso ir
karinė įranga– Amerikos korporacija „Boeing“ užsiima stabilizavimo sistemomis
orlaivių naudojant grynąją automatų teoriją. Didžioji dalis automatų teorijos
buvo sėkmingai naudojamas sistemos programose ir teksto filtruose UNIX OS.
Tai leidžia daugeliui žmonių dirbti aukšto lygio ir labai tobulėti
veiksmingos programos.

TA taikymo sritys yra įspūdingos savo apimtimi ir neapsiriboja siauromis
dėmesys ir specializacija. Panagrinėkime kai kuriuos iš jų.
Programavimas
Kyla klausimas, kodėl automatų teorijos baigtinių automatų modelis yra ypatingas
aktualu dabar, kai egzistuoja puiki suma kaip kalbos
programavimo ir programinės įrangos kūrimo aplinkos? Yra dvi problemos:
 nenuspėjamas išskirtinai sukurtos programos kodo elgesys
RAD įrankiai (Rapid Application Development – ​​greito kūrimo įrankiai
programos);
 „programavimo kultūros“ „išblukimas“.
RAD pavyzdžiai: „Borland Delphi“ ir „C++“ pagreitintam kūrimui
taikomąsias programas naudojant objektinį ir vizualinį
programavimas. Jie leidžia ne tik programuoti įprasta to žodžio prasme,
bet ir iš tikrųjų piešti programas (ir sąsają, ir įgyvendinimą) naudojant
vaizdiniai VCL komponentai.
Bet kuris vizualinis VCL objektas pasižymi daugybe savybių, metodų ir įvykių.
Atrodytų, kad paprasčiausiai manipuliuojant išvardytais atributais galima priversti
kuriama programa, kad padarytų tai, ko iš jos reikalauja programuotojas kūrėjas. Bet
tai toli gražu nėra tiesa.
Jau seniai buvo aišku, kad VCL linkęs slėpti tikslų įgyvendinimą
objektus, taip užkertant kelią pašaliniams asmenims pakeisti numatytąją kodo elgseną. Kaip
praktika rodo, kad programos, sukurtos naudojant RAD priemones, kodo elgesys ne
visada nuspėjamas net labai patyrusiam programuotojui, jau nekalbant apie pradedančiajam.
Programa, nepaisant autoriaus kodo „akivaizdumo“, visada stengiasi eiti savo keliu.
būdu, patekti į tokius sudėtingus įvykių tvarkytojus, kurių egzistavimas
tu gali net neatspėti.
IN modernus pasaulis Kuriamų programų apimtis ir sudėtingumas didėja
kiekvieną dieną, todėl šis metodas žymiai padidina programinės įrangos testavimo ir derinimo laiką.
Automatų teorijos mechanizmas leidžia valdyti kodo elgesį.
prieš keturiasdešimt metų.
Programavimo stiliai skiriasi pagrindinėmis sąvokomis, kurios yra
vartojamos tokios sąvokos kaip „įvykis“, „paprogramė“, „funkcija“, „klasė“.

("objektas") ir tt Programavimo stilius, pagrįstas aiškiu būsenos paskirstymu
ir automatų naudojimas programų veikimui apibūdinti, vadinamas „automatiniu“.
programavimas“, ir atitinkamas programos dizaino stilius –
„automatizuotas dizainas“. Automatinis programavimas gali būti laikomas ne
tik kaip savarankiškas programavimo stilius, bet ir kaip priedas prie kitų
stilių, pavyzdžiui, į objektinį, nes Mes kalbame ne tik ir ne tiek
naudojant baigtinių būsenų mašinas programuojant, kiek apie kūrimo metodą
programas apskritai, kurių elgesį apibūdina automatai. Tie. kaip atskiras
komponentas, o visa programa gali būti įdiegta kaip automatas.
Yra dvi automatinio programavimo kryptys: SWITH technologija ir
KA (finite-automatic) technologija. Komutatorių technologija – sistemų kūrimo technologija
loginis valdymas, pagrįstas baigtiniais automatais, apimantis procesą
projektavimas, įgyvendinimas, derinimas, tikrinimas (patikrinimas), dokumentacija ir
palydos.
Automatų kodavimas/programavimas KA technologijos rėmuose remiasi
šiais principais:
 supažindino su dinaminio objekto, kuriam gali būti suteiktas algoritmas, samprata
elgesys laikui bėgant;
 objekto elgesio algoritmas pateikiamas baigtinio automato modeliu;
 automato aprašymo kalba paremta automatų vaizdavimu lentelėje;
 objekto elgesio logika (automatų perėjimo lentelė) atskirta nuo metodų
automato objektas (predikatai ir veiksmai), susiję su jo įgyvendinimu
elgesys laikui bėgant;
 Lygiagrečiai gali būti vykdomi bet kokie dinaminiai objektai.
Pažvelkime į šias technologijas atidžiau:
1) SWITH technologija. Pagrindinės nuostatos: siūloma „valstybės“ sąvoką padaryti
pirminis, o algoritmai pateikiami pereinamųjų grafikų (būsenų diagramų) pavidalu, t.y.
vaizduoti programą kaip sąveikaujančių baigtinių automatų sistemą,
aprašyti pereinamaisiais grafikais. Būsenos yra užkoduotos, kad būtų galima jas atskirti.
Grafikai vaizdine forma žmogui atspindi perėjimus tarp būsenų, taip pat
„suriša“ išvesties veiksmus ir kitus automatus su būsenomis ir (arba) perėjimais.
Programos viduje automatai gali sąveikauti:

 sudėjus lizdus (vienas automatas yra įdėtas į vieną ar kelias kito būsenas
mašina)
 pagal iškviečiamumą (iš išvesties su tam tikru įvykiu iškviečiamas vienas automatas
įtaka, susidariusi perėjus kitam automatui)
 pranešimų siuntimas (vienas automatas gauna pranešimus iš kito)
 pagal būsenos numerius (vienas automatas patikrina, kokia būsena
kita mašina).
Neribojamas nei tam tikroje būsenoje įdėtų automatų skaičius, nei lizdo gylis.
Pagrindinis valdymo automatų optimalaus įgyvendinimo kriterijus yra galimybė
perėjimo grafiko konvertavimas į programos kodą.<><><>Yra žinoma daug
įrankiai, skirti generuoti programas, kurios įgyvendina perėjimo grafikus:
 Visio2Switch įrankis Visio2Switch leidžia grafiškai
perėjimai, sukurti naudojant „Microsoft Visio“ redaktorių automatiškai
įgyvendinti ją kaip izomorfinę C programą.Visio2Switch Converter
šiuo metu naudojamas kuriant programinę įrangą daugeliui
atsakingos realaus laiko sistemos.
 MetaAuto MetaAuto įrankis leidžia, atsižvelgiant į perėjimo grafiką,
sukurtas naudojant tą patį redaktorių, automatiškai įdiekite jį formoje
izomorfinė programa bet kuria programavimo kalba, kuriai
iš anksto sukurtas šablonas (C, C#, Turbo Assembler ir kt.).
 UniMod įrankis UniMod skirtas palaikyti
automatinis programavimas ir ne tik automatų, bet ir automatų konstravimas bei diegimas
programos apskritai.
Praktika parodė, kad daugeliui programų klasių programinės įrangos tik 20-30 proc
kodas kuriamas rankiniu būdu.
SWITCH technologijos pagrindu jau sukurtos aplikacijos: prekybos įrenginiams
sodos vanduo, bankomatas (žr. 1 pavyzdį), šviesoforai, valdymo sistemos
keleivinis liftas, automobilio signalizacijos valdymo sistema (žr. 2 pavyzdį),
automatizuota mokėjimo sistema Mobilusis telefonas, valiutos keitimo įrenginiai,
bilietų pardavimo įrenginiai ir kt.
2) KA technologija leidžia įgyvendinti lygiagretumo idėją. Plėtros technologijos
iš viršaus į apačią, iš apačios į viršų, struktūrinis požiūris į tokias galimybes ar ne

turi arba jie yra riboti. Net ir objektinėje technologijoje
programavimas (OOP), objektų lygiagrečio veikimo klausimai iš jo ribų išbraukiami.
Kitų technologijų, pagrįstų gerai žinomais lygiagrečiais modeliais, naudojimas,
yra kupinas sunkumų, susijusių, jei ne su jų taikymo srities apribojimais, tai
su vėlesnio diegimo programinės ir (arba) aparatinės įrangos lygiais problemomis.
Lygiagretūs modeliai yra viena iš pagrindinių ir perspektyvių plėtros sričių
programavimas ir techninė įranga. Lygiagretumo idėja yra labai patraukli. Bet
norint juo naudotis, būtina, pirma, išspręsti aprašymo problemą, t.y. pasirinkimas
formalus paralelinis modelis, ir, antra, modelio įgyvendinimo problema. KA
technologija naudoja modelį su lygiagretumo vaizdavimo ir aprašymo priemonėmis,
kurie savo galimybėmis nėra prastesni už kitus lygiagrečius modelius, o jos
įgyvendinti daug lengviau. Be to, naudojant standartinius metodus, tai lengva
pereiti nuo lygiagrečio baigtinio automato vaizdavimo į nuoseklųjį
apibūdinimas.
KA technologijos taikymo pavyzdžiai: skaičiavimo tipo apskaitos programos
darbo užmokesčio ar nuomos apskaita, projektų valdymo sistema
technologinis kristalų auginimo procesas su daugeliu dinamiškai
generuojami lygiagrečiai veikiančiuose objektuose, kurie įgyvendina pašalinimo procesus
duomenys iš jutiklių, valdymo veiksmų suteikimas objektui, automatų algoritmai
vairuotojų darbas su įvairia įranga, rodymo ir skaičiavimo procesai.
3) Pagrindinis skirtumas tarp nagrinėjamų technologijų yra logikos įgyvendinimas
automatines programas. SWITCH technologijoje jis įgyvendinamas perkeliant automatinį
aprašymai programavimo kalbos programiniame kode, KA yra įdiegta technologija
tiesioginis automatų vykdymas, interpretuojant jo pirminę lentelę
atstovavimas. Tai trumpesnis ir aiškesnis automatų diegimo būdas, nors ir daugiau
lėtas, jei atsižvelgsime į atskiro tinklo komponento automato lygį
mašinos.
Išvada: šiuo metu naudojamas automatinis programavimas
kritinių objektų automatizavimo sistemų programinės įrangos projektavimas
valdymas (automatinis kriogeninio-vakuuminio bloko valdymas, dyzelinis generatorius).
Valstybės mašina veikia principu „žingsnis į šoną – nepriimtina“. Įgyvendinti
būsenos mašina neduos vartotojui nenumatytų veiksmų (originalas
kodo variantas), nei pati programa (modifikuotas kodo variantas).

Šiuo metu vyksta kūrybos bumas Kompiuteriniai žaidimai. Dažniau
žaidimo valdymo logika, kuria gali žaisti žaidimo srityje judantys personažai
veikti įvairiais režimais (pavyzdžiui, veikėjas bėga pirmyn arba atgal, lipa
laiptai, kritimai ir pan.) yra įgyvendinama kaip valstybės mašina.
Diskretinės matematikos ir programavimo algoritmų vizualizatorių diegimas
Tiriant informacijos apdorojimo algoritmus, atstovaujamus įvairiems
duomenų struktūras, svarbų vaidmenį atlieka algoritmų vizualizatoriai, leidžiantys
vaizdinė forma dinamiškai parodo savo darbo detales.
Vizualizatorius yra programa, kuri savo veikimo metu yra kompiuterio ekrane
dinamiškai demonstruoja algoritmo pritaikymą pasirinktam duomenų rinkiniui.
Vizualizatoriai leidžia tyrinėti algoritmų veikimą žingsnis po žingsnio režimu, panašiu į
programos sekimo režimas. Jie leidžia atsekti, jei reikia.
išplėsti žingsniai, ignoruojant įprastą skaičiavimo proceso dalį, kuri
būtini, pavyzdžiui, surašymo algoritmams.
Kai kuriems algoritmams yra dinaminė jo darbo demonstravimo versija
natūraliau nei statiškų iliustracijų rinkinys.
Mokant daugumą algoritmų, kartu su „žingsnio į priekį“ režimu, tai labai naudinga
taip pat „žingsnio atgal“ režimas, leidžiantis greičiau ir visapusiškai suprasti algoritmą.
Pavyzdžiui, naudojant atgalinio sekimo algoritmus gali tekti atlikti kelis veiksmus
atgal, kad suprastų, kodėl buvo atmesta ta ar kita paieškos atšaka.
Vizualizatorių pavyzdžiai: dvejetainio medžio perėjimas, planavimo algoritmai,
rūšiavimas ir kt. Tie. sudėtingi algoritmai su daugybe perėjimų, sąlygų ir
šakas galima pavaizduoti kompaktiškiau ir aiškiau: baigtinio automato pavidalu su
nuspėjamas ir matomas elgesys.
Dirbtinis intelektas
Dirbtiniai neuroniniai tinklai (ANN) – matematiniai modeliai, taip pat jų programinė įranga
arba techninės įrangos diegimai, sukurti organizacijos ir veikimo principu
biologiniai neuroniniai tinklai – gyvo organizmo nervinių ląstelių tinklai. Ši sąvoka
atsirado tiriant smegenyse vykstančius procesus ir bandant juos modeliuoti
procesus.
Neuroniniai tinklai yra išskirtinai galinga modeliavimo technika, leidžianti
atkurti itin sudėtingas priklausomybes. ANN yra konfigūruojami ir

mokymasis. Automatų naudojimas dirbtiniams neuroniniams tinklams kurti
leidžia neįtraukti nenumatytų būsenų darbe.
Neuroninės technologijos ypač intensyviai naudojamos ekspertinėse sistemose.
indėlių ir finansinių reikalų prognozavimas vertinant investicijas.
Pavyzdys: skystųjų raketų varikliuose (LRE), kurie yra sudėtingi
techninė sistema, susidedanti iš daugelio tarpusavyje sąveikaujančių vienetų
pati, būtina greita valdymo sistemos reakcija į vykstančius procesus.
viename iš kritiškiausių ir labiausiai įtemptų agregatų – turbosiurblio bloke
(TNA). Naudojant neuroninius tinklus ir automatus, tai tampa įmanoma
ankstyva ekstremaliųjų situacijų diagnostika, o tai sumažina avarijos pasekmes
ir užkirsti kelią variklio sunaikinimui atliekant gaisro bandymus (žr. 3 pavyzdį).
Kai veikia, TNA vaizduojama kaip baigtinės būsenos mašina. valstijos, in
kuris gali būti: budėjimo režimas, paleidimas, pagrindinis režimas, sustabdymas, avarinis režimas
būsena (suskirstyta į daugybę būsenų, klasifikuojančių gedimo pobūdį).
Ribinio nuokrypio reikšmė parenkama taip, kad būtų
minimalus ir tuo pačiu leidžiantis nedidelius variantus. Atsisakymo atveju (išeiti
bet kuris iš keturių tinklų yra lygus vienetui), neuroniniai tinklai treniruojami
būdingas TNA gedimams, pagal kurių parodymus galima nustatyti, kas tarnavo
gedimo priežastis (tinklo išvestis lygi vienetui). Jei tai nepavyksta (keli
tinklo išėjimai yra lygūs vienetui), tada laikoma, kad gedimas sujungiamas – tuo pačiu metu
buvo keletas gedimų, o esant netikrumui (visi tinklo išėjimai yra vienodi
nulis), įrenginys persijungia į Naujo gedimo būseną.
Sukurta technika leidžia aptikti turbosiurblio bloko gedimus. Nes
šis prietaisas yra labai sudėtingas, tada po avarinės situacijos
sunku nustatyti gedimo tipą, kokioje darbo būsenoje šiuo metu
įrenginio vieta ir kaip jį grąžinti į darbinę būklę. Neuroninis tinklas
leidžia išvengti avarijos arba nustato laiką, kada įvyko gedimas, ir
nustato gedimo tipą. SWITCH technologijos taikymas kuriant valdymą
Programinė įranga leidžia gauti visą diagnostikos mašinos veikimo protokolą - bet kuriuo metu
jos veikimo metu galite sužinoti, kokios būklės ir kokios yra mašina
jos būsena gali būti išversta.
Programinės įrangos kūrimas mobiliuosius įrenginius ir mikrovaldikliai

Kuriant serverio programas, kurios reaguoja į užklausas, svarbų vaidmenį atlieka
„be pilietybės“ – nebūtina saugoti būsenų tarp dviejų
nuoseklūs prašymai.
Kuriant sėkmingą interaktyvią įvykiais pagrįstą programą, daug
priklauso nuo to, ar gerai apgalvotas valstybės valdymo modelis.
Valstybės mašina yra labai patogi koncepcija, kuri yra naudinga
struktūrizavimo programos.
Kadangi mobiliosios programos turi naudoti ekrano erdvę ir sistemą
išteklius efektyviai, būsenos mašinos ypač naudingos, kai
programinės įrangos kūrimas tokioms programoms.
Programa yra baigtinių sąveikaujančių automatų rinkinys
tarpusavyje ir su išoriniu pasauliu. KA perėjimo diagramoje aprašomi perėjimai tarp
ekrano formos, perėjimo lankai iš būsenos į būseną aprašo veiksmus
Vartotojas. Kiekviena sukonstruota forma turi būti susieta su būsenos mašina,
kontroliuojantis vizualinį formos elgesį. Jei pačioje formoje yra keletas
puslapiuose, pavyzdžiui, dialogo languose su skirtukais, tada jis pateikiamas kiekvienam iš jų
subpuslapiai savo būsenos mašiną.
Būsenos mašinos labai pagerina vykdymo kontrolę
fono užduotis. Jų naudojimas leidžia sukurti fono gijas
informacija apie vykdymo būklę, taip pat kitų gijų kreipimasis su prašymais į
fono giją tam tikriems veiksmams atlikti, pavyzdžiui, su užklausa
nustokite vykdyti foninį darbą. Tuo pačiu vaizdine grafine forma
tiek jungtys tarp automatų ir jų vidinių
struktūra. Pagrindinis privalumas: kodo pakartotinis naudojimas, greitas
modifikavimas, matomumas, kuris yra svarbus mobiliųjų įrenginių programoms,
reikalaujantis taupiai išnaudoti ekrano erdvę, atmintį, kompiuteriją
galia ir kiti ištekliai.
Darbo eigos modelių kūrimas remiantis baigtinio automato teorijos modeliu
kulkosvaidis
Šiuolaikinėje visuomenėje vyksta skaičiavimo intensyvėjimo procesas ir
informacines technologijas visose veiklos srityse.
Dokumentų srautas – dokumentų judėjimas organizacijoje nuo jų sukūrimo momento arba
gavimas prieš užbaigiant vykdymą: siuntimas ir (arba) siuntimas į bylą. Įgyvendinimas

elektroninis dokumentų valdymas yra neatidėliotinas uždavinys šiuolaikinė visuomenė, nes
tai leidžia padaryti dokumentų judėjimo procesą valdomą ir kontroliuojamą, o tai
teikia geresnes valdymo paslaugas. Įmonės ir organizacijos, skirtos
Šios problemos sprendimas reikalauja daug laiko ir pinigų. Tuo pačiu metu kiekvienas
dokumentų valdymo sistemos kūrimas yra unikalus ir galimybė pakartoti
praktiškai nenaudojama visa įgyta patirtis. Teisingai
šio proceso organizavimas lemia bet kurio darbo kokybę ir stabilumą
įmonių.
Naudojant automato modelį kuriant dokumentų srautų specifikacijas ir
programinės įrangos produktas leidžia sukurti sistemas, labiau atitinkančias reikalavimus
vartotojų ir suteikia galimybę pasiekti programų suderinamumą.
Automatų teorija leidžia įgyvendinti dokumentų judėjimo šakojimo tarp logiką
dokumentų valdymo procesų dalyviai. Aparatas leidžia nustatyti reakciją
darbo eigos sistemos elementai sistemos pokyčiams.
Sumodeliuotu objektu laikomas vadinamasis sudėtinis objektas.
dokumentų srautas, tai yra toks dokumentų srautas, kuriame jie dalyvauja, tiek elektroninis,
taip pat popieriniai pareiškimai. Sudėtinė darbo eiga
pavaizduotas trigubu: Dm = (U, D, F), kur
 Дт – formalus darbo eigos modelis;
 Y – dalyvių rinkinys;
 D – veiksmų rinkinys;
 F – dokumento būsenų rinkinys.
Dokumento būsenų rinkinys S gaunamas analizuojant gyvavimo ciklą
dokumentas. Tai visų būsenų, kurias gali priimti dokumentas, rinkinys
modeliuojamoje darbo eigoje, kur kiekviena reikšmė yra unikali: (S)=(F).
Pradinė būsena yra pradinė būsena, į kurią patenka
dokumentas po proceso inicijavimo. Pateikiant dokumento srautą formoje
procesų rinkinys, pradinė būsena yra pirmasis žingsnis, po kurio
galime sakyti, kad dokumentas egzistuoja ir procesas suaktyvintas. Šiuo būdu,
pradinės būsenos – tai objektai, aibės Ф elementai, turintys vieną arba
keli išeinantys ryšiai ir nė vieno įeinančio.

Darbo eiga susideda iš procesų rinkinio, kurių kiekvienas vyksta
vieną ar daugiau dokumentų. Darbo eigos proceso gyvavimo ciklas
yra nulemtas dokumentų judėjimo iš pradinių būsenų į galutines būsenas.
Nagrinėjamame modelyje galutinės automato būsenos apibrėžiamos kaip būsenos
dokumentus, kuriems atsiradus mašinos veikimas sustoja, t.y.
darbo eiga nustoja egzistuoti. Taigi, finalas
būsenas galima apibrėžti kaip aibės Ф objektus, kurie turi vieną arba
keli įeinantys ryšiai ir nė vienas išeinantis.
Darbo eigoje dokumentas įgauna tokią būseną, priklausomai nuo
su juo atliktų veiksmų rezultatas. automatinio perėjimo funkcija
darbo eigos modelius galima apibrėžti kaip i-tąjį veiksmų rinkinio elementą (D)
darbo eiga, po kurios būsena pasikeičia į
sąlyga. (F) = (D)
Automato abėcėlė yra simbolių rinkinys, kurio rinkiniai ateina arba gali
veikti automatiškai. Kaip automato abėcėlę, reikėtų atsižvelgti į sąrašą
dalyvių.
Galima vienareikšmiškai apibrėžti automatą, kuris tinkamai įgyvendins modelį
darbo eiga. Deterministinių automatų pagrindu sukurtas modelis leidžia
kurti modelius, kuriuos lengviau suvokti vizualiai. Jiems lengviau statyti
programinės įrangos diegimas. Tuo pačiu metu kuriant proceso modelius, kurie turi
sudėtinga išsišakojusi struktūra, automato modelis deterministiniuose automatuose
jis tampa didelis ir masyvus.
Nedeterministiniai automatai leidžia nurodyti sudėtingus procesus naudojant
mažiau aprašomosios medžiagos. Tačiau aiškumo dėlei jie
daug sunkiau.
Išvada: mažiems, šiek tiek šakotiems procesams geriau naudoti
deterministiniai automatai, o nedeterministiniai yra patogesni
nurodant procesus su daugybe žingsnių ir atšakų.
Sukūrus teorinę bazę, įdiegiama programinė įranga,
taikant praktikoje automatinius ir grafinius darbo eigos modelius. Kiekvienas iš
dalyviai turi galimybę pasiekti tam tikrų tipų dokumentus ir
atlikti su jais griežtai apibrėžtus veiksmus.

Sudėtinių darbo eigos sistemų įdiegimas leidžia dirbti biure
skaidresnis ir nuspėjamas, mažina asmeninę atlikėjo įtaką
darbuotojai už galutinį rezultatą.
Nagrinėjama pramonė šiuo metu sparčiai vystosi. Toliau
šios krypties tyrimai, ypač kalbant apie CSgrammatics naudojimą ir
sukurti programinę įrangą, kuri įgyvendina aprašytą automato modelį
visa sudėtinė darbo eiga.
Eilučių paieška tekste
Remiantis oficialia statistika, apie 85% interneto vartotojų nuolat
susisiekite su paieškos sistemomis
(„Google“, „Yandex“, „Rambler“, „Yahoo!“, „Aport“, „[email protected]“ ir kt.), kad surastumėte
jiems reikalingos informacijos apie prekes ar paslaugas.
Automatų teorijos nuostatos puikiai tinka tokiai realybei apibūdinti
užduotys, atsirandančios programose, pvz., paieška internete ir ištraukimas
informacija iš teksto. Daugelis šiuolaikinių paieškos sistemos Interneto naudojimas
speciali programa – paieškos robotas, kuris yra automatas.
Interneto ir skaitmeninių bibliotekų su nuolatine prieiga amžiuje įprasta
kita problema. Jums duotas žodžių rinkinys ir norite juos rasti
dokumentai, kuriuose yra vienas (arba visi) iš jų. Populiarus tokio pavyzdys
procesas yra paieškos sistemos, kuri naudoja specialią technologiją, darbas
paieška, vadinama atvirkštiniais indeksais (apverstais indeksais). Už kiekvieną žodį
rasti internete (o jų yra apie 100 000 000), visų vietų, kur
tai susitinka. Labai didelio tūrio mašinos laisvosios kreipties atmintis teikti
nuolatinė prieiga prie labiausiai pageidaujamų sąrašų, leidžianti daugeliui žmonių
vienu metu ieškoti dokumentų.
Atvirkštinio indekso metodas naudoja ne būsenos mašinas, o šį metodą
Nukopijuoti ir perrašyti tinklo turinį užtrunka daug laiko
indeksai. Yra daug susijusių programų, kuriose taikoma technika
atvirkštiniai indeksai neįmanomi, tačiau galite sėkmingai naudoti metodus, pagrįstus
mašinos. Tos programos, kurioms tinka automatinė paieškos technologija,
turi šias išskirtines savybes:
1. Ieškomas tekstų parduotuvės turinys yra greitas
keičiasi.

Štai du pavyzdžiai:
o kiekvieną dieną analitikai ieško straipsnių su naujausiomis naujienomis
aktualiomis temomis. Pavyzdžiui, finansų analitikas gali ieškoti
straipsniai su tam tikromis saugos santrumpos ar pavadinimais
įmonės;
o „robotas pirkėjas“ kliento pageidavimu stebi esamas kainas
tam tikrų produktų pavadinimų. Jis nuskaito puslapius iš žiniatinklio,
su katalogais, tada nuskaito tuos puslapius, kurių ieško
konkrečios prekės kainos informacija.
2. Ieškomi dokumentai negali būti kataloguojami.
Pavyzdžiui, labai sunku internete rasti visus puslapius, kuriuose yra informacijos apie
visų Amazon.com parduodamų knygų, nes šie puslapiai
yra generuojami tarsi „kelyje“ atsakant į užklausą. Tačiau užklausą galime išsiųsti el
knygas konkrečia tema, pasakykite „valstybės mašinos“ ir ieškokite toje dalyje
tekstas, esantis pasirodžiusiuose puslapiuose, pvz., tam tikras žodis
žodis „gražus“.
ATM veikimo modeliavimas
Bankomatas yra automatizuotas įrenginys, leidžiantis atlikti nuotoliniu būdu
operacijos, susijusios su vartotojo autentifikavimu (banko sąskaitos turėtojas),
esamos sąskaitos būklės peržiūra, pinigų išėmimas iš sąskaitos ir uždirbimas
įvairūs mokėjimai. Šiame pavyzdyje nagrinėjamas bankomato veikimas, įskaitant
tik kliento dalis, bet ir serverio dalis, kuri apdoroja užklausas, taip pat
leidimų posistemis.
Pagrindinis uždavinys diegiant tokias sistemas yra garantija aukštas lygis patikimumas
klientų, banko vartotojų ir banko informacinės sistemos.

Nepaisant ryšio tarp automatų trūkumo, AServer yra įdėtas į AClient. At
kai AKliento automatas yra būsenose „Įgaliojimas“, „Balanso užklausa“ ir
„Pinigų prašymas“ programos valdymas perkeliamas į mašiną AServer , kuri
siunčia užklausą į serverį, gauna atsakymą ir grąžina valdymą mašinai

AClient. Pats serveris sukurtas tradiciniu būdu ir įgyvendintas kaip
konsolės programa.
Programos sąsaja:
Pavyzdys rodo, kad UniMod įrankis supaprastina procesą
sukurti programą, palyginti su tradiciniu požiūriu. Tuo pačiu metu dauguma
Kūrėjo laikas skiriamas sistemos projektavimui. Nuo pagrindinės dalies
kodas generuojamas automatiškai, padidinamas programos patikimumas.
Automobilio signalizacijos valdymo sistemos priekiniai žibintai, sirena ir LED kaip valdymo objektai. Naudojant sudėtingą būseną
"2. Įjungta“ (yra 3 būsenos) suteikia galimybę išjungti
nesvarbu, kokioje būsenoje yra mašina.
Sistemos įvykių generatoriai
Įvykių generatorius p1. Šis objektas apibūdina konsolės sukurtus įvykius.
signalizacijos valdymas. Pokyčiai:
 e11 - mygtuko "1" paspaudimas;
 e12 - mygtuko "2" paspaudimas;
 e13 - paspaudus mygtuką "3".
p2 įvykių generatorius. Šis objektas atitinka smūgio jutiklį. Jis gali išduoti du
įvykiai:
 e21 - silpno smūgio fiksavimas;
 e22 – stipraus smūgio fiksavimas.
p3 įvykių generatorius. Šis objektas paleidžia vieną iš trijų laikmačių. Kai atgalinis skaičiavimas
užbaigia, sugeneruoja atitinkamą įvykį. Laikmatis paleidžiamas paprašius
valdymo objektas „o2“, nurodantis numerį ir reikiamą laiką.
 e31 - laikmatis "1" baigė skaičiuoti (laikmatis skaičiuoja laiką būsenoje "3.
aliarmas“ mašinos A1);

 e32 - laikmatis "2" baigė skaičiuoti (laikmatis skaičiuoja laiką būsenoje "2.
Pavojaus būsena“ mašinos A1);
• e33 - laikmatis "3" baigė skaičiuoti (laikmatis nutildymo valdymui).
Sistemos valdymo objektai
Valdymo objektas o1. Šis objektas apibūdina priekinių žibintų atliekamus veiksmus
automobilis.
 z1 – sumirksi vieną kartą;
• z2 – mirksėti du kartus;
• z3 – sumirksi tris kartus;

 z5 – nutraukti bet kokį veiksmą.
Valdymo objektas o2. Šis objektas naudojamas „p3“ laikmačiui paleisti.
 z1 – paleisti laikmatį "1" 15 s;
 z2 – paleisti laikmatį "2" 5 s;
 z3 – paleisti laikmatį "3" 3 s;
z4 - sustabdyti visus laikmačius.
Valdymo objektas o3. Šis valdymo objektas atspindi sirenos veikimą. Jo
išėjimo veiksmai beveik sutampa su priekinių žibintų išėjimo veiksmais.
 x1 yra loginis kintamasis, nurodantis, kad garsas įjungtas (ty gali
signalai) ar ne;
 z1 – garso generavimas, atitinkantis automobilio įjungimą į signalizaciją;
 z2 – garso generavimas, atitinkantis automobilio išėmimą iš signalizacijos;
 z3 – garso generavimas, atitinkantis reakciją į silpną smūgį;
 z4 – pradeda duoti pavojaus signalą;
 z5 - nutraukti garsą;
 z6 – įjungti garsą (leisti duoti signalus);

• z7 – išjungti garsą (uždrausti duoti signalus).
Valdymo objektas o4. Šis valdymo objektas apibūdina šviesos diodo veikimą,
esantis automobilyje. Rodo esamą aliarmo būseną.
 z1 – pradeda mirksėti;
 z2 – nustoti mirksėti.
Valdymo objektas o5. Šis valdymo objektas naudojamas išvesti

automatų teorija
Automatų teorija- diskrečiosios matematikos skyrius, nagrinėjantis abstrakčius automatus - kompiuterius, pateiktus matematinių modelių pavidalu - ir užduotis, kurias jie gali išspręsti.

Automatų teorija glaudžiausiai susijusi su algoritmų teorija: automatas paverčia diskrečią informaciją žingsneliais į atskirus laiko momentus, o rezultatą generuoja tam tikro algoritmo žingsneliais.

  • 1 Terminija
  • 2 Taikymas
    • 2.1 Tipinės užduotys
  • 3 Taip pat žr
  • 4 Literatūra
  • 5 Nuorodos

Terminija

Simbolis- bet koks atominis duomenų blokas, galintis turėti įtakos mašinai. Dažniausiai simbolis yra raidė bendrine kalba, tačiau tai gali būti, pavyzdžiui, grafinis diagramos elementas.

  • Žodis- simbolių eilutė, sukurta sujungimo (sujungimo) būdu.
  • Abėcėlė- baigtinis skirtingų simbolių rinkinys (daug simbolių)
  • Kalba- žodžių rinkinys, sudarytas iš nurodytos abėcėlės simbolių. Gali būti baigtinis arba begalinis.


Automatas

Automatai gali būti deterministiniai arba nedeterministiniai.

Deterministinis baigtinis automatas (DFA)
  • yra tokia perėjimo funkcija
  • - pradinė būsena
Nedeterministinis baigtinis automatas (NFA)- penkių elementų seka (kortelė), kur:
  • - automato būsenų rinkinys
  • - kalbos, kurią supranta automatas, abėcėlė
  • yra pereinamasis santykis, kur yra tuščias žodis. Tai yra, NFA gali pereiti iš būsenos q į būseną p, skirtingai nei DFA, per tuščią žodį, taip pat pereiti iš q į kelias būsenas (kas vėlgi neįmanoma DFA).
  • - pradinių būsenų rinkinys
  • - galutinių būsenų rinkinys.
Žodis automatas skaito baigtinę simbolių eilutę a1,a2,…., an , kur ai ∈ Σ, kuri vadinama įvesties žodžiu.Visų žodžių aibė rašoma kaip Σ*. Gautas žodis Žodį w ∈ Σ* priima automatas, jei qn ∈ F.

Laikoma, kad kalba L skaitoma (priimama) automato M, jei ji susideda iš žodžių w pagal abėcėlę taip, kad jei šie žodžiai įvedami į M, apdorojimo pabaigoje ji patenka į vieną iš priimančių būsenų F:

Paprastai automatas pereina iš būsenos į būseną naudodamas perėjimo funkciją, skaitydamas vieną simbolį iš įvesties. Yra automatų, kurie gali pereiti į naują būseną neskaitydami simbolio. Perėjimo funkcija neskaitant simbolio vadinama -jump (epsilon-jump).

Taikymas

Automatų teorija remiasi visomis skaitmeninėmis technologijomis ir programine įranga, pavyzdžiui, kompiuteris yra ypatingas baigtinių būsenų mašinos praktinio įgyvendinimo atvejis.

Dalis automatų teorijos matematinio aparato yra tiesiogiai naudojama kuriant formaliųjų kalbų, įskaitant programavimo kalbas, lekserius ir analizatorius, taip pat kuriant kompiliatorius ir kuriant pačias programavimo kalbas.

Kitas svarbus automatų teorijos pritaikymas yra matematiškai griežtas problemų sprendžiamumo ir sudėtingumo nustatymas.

Tipiškos užduotys

  • Automatų konstravimas ir minimizavimas- abstraktaus automato sukūrimas iš tam tikros klasės, kuris išsprendžia duotą problemą (priima tam tikrą kalbą), galbūt vėliau sumažinant būsenų skaičių arba perėjimų skaičių.
  • Automatų sintezė- duotų „elementarių automatų“, lygiaverčių tam tikram automatui, sistemos sukūrimas. Toks automatas vadinamas struktūriniu. Jis naudojamas, pavyzdžiui, skaitmeninio sintezėje elektros grandinės ant tam tikro elemento pagrindo.

taip pat žr

  • Siurblys Lemma
  • Abstraktus automatas
  • Žaidimas "Gyvenimas"
  • Minimali automato forma
  • Šenono-Lupanovo teorema

Literatūra

  • Johnas Hopcroftas, Rajeevas Motwani, Jeffrey Ullmanas. Įvadas į automatų teoriją, kalbas ir skaičiavimą. - M.: Williams, 2002. - S. 528. - ISBN 0-201-44124-1.
  • Kasjanovas V. N. Paskaitos apie formaliųjų kalbų teoriją, automatus ir skaičiavimo sudėtingumą. - Novosibirskas: NSU, 1995. - C. 112.

Nuorodos

  • Automatų teorijos taikymas

automatų teorija

A.A. Ožiganovo automatų teorija. Vadovėlis - Sankt Peterburgas: NRU ITMO, 2013. - 84 p. - kopijuoti.

Anotacija:

Šios pamokos tikslas – supažindinti studentus su skaitmeninių automatų sintezės metodais. Pateikiama informacija apie abstrakčius Mealy ir Moore automatus. Straipsnyje nagrinėjami automatų atvaizdavimai lentelėse ir grafikuose, supažindinama su automato atsaku į įvesties žodį ir apibrėžiami lygiaverčiai automatai. Pateikiami automatų tarpusavio ekvivalentinės transformacijos metodai. Pateikiama bendra informacija apie mikroprogramų valdymą, mikroinstrukcijų sampratos, mikrooperacijos, mikroprogramos, mikroprogramų vaizdavimo būdai algoritmų grafinėmis diagramomis (GSA), perėjimų formulės, algoritmų matricos ir loginės diagramos. Pateikiami GSA ženklinimo metodai ir jais remiantis Mealy ir Moore automatų konstravimo taisyklės. Nagrinėjami struktūrinių automatų kanoninės sintezės metodai. Pateikiami struktūrinės automato atminties sintezės pavyzdžiai, pagrįsti D -, T -, RS - ir JK šleifais.

Apibūdinimas:

Vadovas skirtas studentams, besispecializuojantiems informacinių technologijų srityje ir gali būti naudojamas rengiant bakalaurus ir magistrus 230100 „Informatika ir kompiuterių inžinerija“, 231000 „Programinės įrangos inžinerija“ ir specialybės 230101 „Kompiuteriai kompleksai, sistemos ir tinklai“.

Visi aukščiau aptarti įrenginiai priklauso kombinuotų grandinių klasei, ty diskretiesiems įrenginiams be atminties. Kartu su jais įeina skaitmeninės technologijos nuoseklūs automatai, arba, kitaip tariant, kombinacinės grandinės, sujungtos su atminties elementais, išplito.

Pagal terminą mašina pagal abu būsenos signalus galima suprasti kokio nors tikro įrenginio funkcionavimą išorinė aplinka, ir vidinius signalus apie paties automato būseną. Šiuo atžvilgiu kompiuteris gali būti laikomas skaitmenine mašina. Skaitmeninė mašina yra įrenginys, skirtas skaitmeninei informacijai konvertuoti. Kita vertus, pagal terminą mašina galite suprasti kai kurių prietaisų matematinį modelį. Bendroji automatų teorija yra padalinta į dvi dalis: abstrakčiai Ir struktūrinės automatų teorija. Skirtumas tarp jų yra tas, kad abstrakčioji teorija abstrahuojasi tiek nuo paties automato, tiek nuo įvesties ir išvesties signalų struktūros. IN abstrakčioji teorija analizuojami automato perėjimai, veikiami abstrakčių įvesties žodžių, ir ant šių perėjimų suformuoti abstraktūs išvesties žodžiai.

Struktūrinėje teorijoje nagrinėjama tiek paties automato, tiek jo įvesties ir išvesties signalų struktūra, automatų konstravimo iš elementarių automatų metodai, įvesties ir išvesties signalų kodavimo metodai, automato būsenos.

Atsižvelgiant į tai, įprasta atskirti du automatų modelius: struktūrinį ir abstraktų. Teoriškai nagrinėjant automatus naudojamas abstraktus modelis. Struktūrinis modelis naudojamas automato grandinei sukonstruoti iš loginių elementų ir trigerių ir yra skirtas valdymo funkcijai atlikti.

Abstraktus automatas yra matematinis skaitmeninio automato modelis, pateiktas šešių komponentų vektoriumi S=(A,Z,W,d,l,a 1), kur A=(a a ,…,a m ) yra aibė vidines būsenas abstraktus automatas; Z=, į kurią automatas pereis iš būsenos a i veikiamas signalo x j; o išėjimų lentelėje – šį perėjimą atitinkantis išėjimo signalas y g = [ a aš, x j]. Kartais Mealy automatui pateikiama kombinuota perėjimų ir išėjimų lentelė, kai kuriais atvejais tai yra patogiau.

Kombinuota „Mealy“ mašinos perėjimų ir išėjimų lentelė:

Nurodant perėjimo ir išvesties lenteles visiškai aprašomas baigtinio automato veikimas, nes nurodomos ne tik pačios perėjimo ir išvesties funkcijos, bet ir visos trys abėcėlės: įvesties, išvesties ir būsenos abėcėlė. Kadangi Moore mašinoje išėjimo signalą vienareikšmiškai lemia mašinos būsena, jam nurodyti reikia tik vienos lentelės, kuri vadinama Moore mašinos pažymėta pereinamojo laikotarpio lentele.

Pažymėta Moore mašinos perėjimo lentelė:

Šioje lentelėje kiekvienas stulpelis yra priskirtas, išskyrus būseną a i, taip pat išvesties signalas y(t) = (a(t)), atitinkantis šią būseną. Moore mašinos perėjimo lentelė vadinama pažymėta, nes kiekviena būsena yra pažymėta išvesties signalu.

Taikant grafinį metodą, automatas apibrėžiamas naudojant grafiką. Šis metodas pagrįstas nukreiptų sujungtų grafikų naudojimu. Grafų viršūnės atitinka automato būsenas, o lankai – perėjimus tarp jų. Dvi grafiko viršūnės a aš ir a s yra sujungti lanku, nukreiptu iš a aš į a s jei automatas turi perėjimą iš a aš įeinu a s, tai yra a s = ( a aš, x j). Mealy mašinoje lankas pažymėtas įvesties signalu x j, kuris sukėlė perėjimą ir išvesties signalą y g, kuris vyksta pereinant. Apskritimo viduje, žyminčio grafiko viršų, parašyta būsena.

„Mealy“ mašinos grafikas:

Moore automato grafikas

2.3 Daliniai automatai

Inžinerinėje praktikoje dažnai susiduriama su automatais, kurių įėjimais niekada netaikomos kai kurios signalų sekos. Tokios sekos bus vadinamos uždraustais tam tikro automato įvesties žodžiais, o pats automatas – daliniu automatu. Daliniam automatui perėjimo ir išvesties funkcijos apibrėžtos ne visose porose ai, xj. Vietoje neapibrėžtų būsenų ir išvesties signalų dedamas brūkšnys. Sintezės metu dalinis automatas dažniausiai apibrėžiamas iš naujo, kad jo grandinės įgyvendinimas būtų kuo paprastesnis.

Dalinės „Mealy“ mašinos perėjimo ir išvesties lentelės pavyzdys

Iš perėjimo lentelės matyti, kad T-flip-flop turi visą perėjimų ir išėjimų sistemą, nes kiekvienai būsenų porai (0-0, 0-1, 1-0,

1-1) yra įvesties signalas, užtikrinantis perėjimą iš vienos būsenos į kitą. Be to, kiekviena automato būsena pažymėta skirtingu išėjimo signalu. Praktikoje vietoje pažymėtų perėjimų lentelių patogiau naudoti vadinamąsias elementariųjų automatų pereinamąsias matricas.

Perėjimo matrica:

Perėjimo matrica nustato signalų reikšmes elementaraus automato įėjimais, pateikdama kiekvieną iš keturių galimų perėjimų. Čia Q(t) ir Q(t+1) yra automato būsenos atitinkamai momentais t ir t+1. Kadangi T flip-flop turi vieną įvestį, o galimų perėjimų skaičius yra keturi, perėjimų matrica turi keturias eilutes.

Norėdami analitine forma užrašyti T trigerio veikimo dėsnį, naudodami perėjimo matricą sudarysime Veitch diagramą:

Iš diagramos turime:

=> (T(t) + Q(t) ) 2 modas

Kadangi ši formulė sutampa su perjungimo funkcijos modulo du analitiniu žymėjimu, T-flip-flop dažnai vadinamas apvertimu su skaičiavimo įėjimu T, o įvesties signalas T įėjime yra skaičiavimo signalas. Praktikoje be asinchroninio T-flip-flop, kurio veikimą nagrinėjome, naudojamas ir sinchroninis T-flip-flop, kuris, skirtingai nei asinchroninis, keičia savo būsenas tik esant T = 1 ir C. = 1. Jei bent vienas iš šių signalų yra lygus nuliui, trigeris išsaugo savo būseną. Įvestis C vadinama laikrodžio įvestimi.

Kombinuota grandinė, paaiškinanti sinchroninės sistemos veikimą ir paskirtį

T-flip-flop pavaizduoti paveikslėlyje:

2.5 D gaidukas

D trigeris (delsinimo trigeris) yra elementarus Moore automatas, turintis dvi stabilias būsenas ir vieną įvestį D, kad Q(t+1) = D(t). Pavadinimas D-trigeris kilęs iš Angliškas žodis„delay“ – delsimas. Iš apibrėžimo išplaukia, kad trigerio būsena momentu t+1 pakartoja įvesties signalo D(t) reikšmę momentu t (taigi ir vėlavimo trigerio pavadinimas).

D-flip-flop perėjimo matrica:

Asinchroninių ir sinchroninių D-flip-flopų pavadinimai:

Sinchroniniame D trigeryje su C=0 trigeris savo būsenos nekeičia, o esant C=1 veikia taip pat kaip ir asinchroninis, t.

Q(t+1)=D(t)*C(t) v Q(t)*

Asinchroninis D-flip-flop neturi praktinės vertės.

D-trigerio grafikas

2.6 RS šlepetas

RS šleifas yra bistabili Moore mašina, turinti du įėjimus R ir S, kad kai S = 1 ir R = 0, apverstas įgauna 1 būseną, o kai R = 1 ir S = 0 - 0. būsena, priimta flip-flop, įėjimas S vadinamas vienu įėjimu, o įėjimas R vadinamas nuliu.

RS flip-flop perėjimo matrica:

Signalų R=1 ir S=1 derinys yra draudžiamas, todėl perėjimas flip-flop su tokiomis įvesties signalų reikšmėmis nėra apibrėžtas. Trigerio perėjimas iš 0 į 0 galimas dviem įvesties signalų kombinacijomis: R=0, S=0 ir R=1, S=0. Todėl stulpelio R flip-flop perėjimo matricos RS pirmoje eilutėje nustatomas kintamasis b1, kuris gali turėti dvi reikšmes 0 v 1. Panašiai perėjimas iš būsenos 1 į 1 galimas ir su dvi įvesties signalų kombinacijos: R=0, S=0 ir R= ​​0, S=1. Kadangi tokio perėjimo metu signalo reikšmė įėjime S yra abejinga, kintamasis b2 rašomas apatinėje perėjimo matricos eilutėje S stulpelyje. Perėjimo matrica gali būti naudojama RS trigerio grafikui sudaryti.

Automatai, kurie gali pereiti iš vienos būsenos į kitą veikiant kelioms įvesties signalų kombinacijoms, vadinami automatais su pertekline perėjimo sistema. Atleidimas gali būti naudojamas sintezės procese, siekiant supaprastinti grandinę, suteikiant kintamiesiems b1 ir b2 tokias reikšmes, kurios leidžia sumažinti elementų skaičių. Todėl, jei dviejų elementarių automatų grandinės yra lygiavertės sudėtingumo, tada pirmenybė teikiama automatui su dideliu perėjimo sistemos pertekliumi.

Analitine forma užrašykime RS flip-flop veikimo dėsnį, kuriam pagal perėjimo matricą sudarome Veitch diagramą:

2.7 JK šlepetės

JK apverstas yra Moore'o automatas su dviem stabiliomis būsenomis ir dviem įėjimais J ir K, kuris, esant sąlygai J * K = 1, apverčia ankstesnę būseną (ty kai J*K=1, Q(t+1) ) = Q( t)), o kitais atvejais jie veikia pagal trigerio tiesos lentelę RS, o įvestis J yra lygiavertė įėjimui S, o įvestis K lygiavertė įėjimui R. Šis trigeris Nr. ilgiau turi draudžiamą įvesties signalų derinį ir jo tiesos lentelę, tai yra, priklausomybė Q (t+1) = f turi tokią formą:

JK flip-flop tiesos lentelė:

Iš šios lentelės galite sukurti Veitch diagramą Q(t + 1), kuri gali būti naudojama sumažinimui, ir perėjimo matricą:

JK flip-flop perėjimo matrica:

Integrinėje grandinėje naudojami tik laikrodžio (sinchroniniai) trigeriniai JK, kurie, kai C=0, išlaiko savo būseną, o kai C=1 veikia kaip asinchroniniai trigeriniai JK.

2.8 Universalus gaidukas

JK šlepetės priklauso universalių šlepečių kategorijai, nes jos pagrindu, paprastu išoriniu perjungimu, galima sukurti RS-, D- ir T-flip-flop. RS flip-flop gaunamas iš JK šlepetės, tiesiog apribojant įvesties signalų derinį J=K=1, nes šis derinys RS apverstui draudžiamas.

Skaičiavimo šleifas, pagrįstas JK šlepetėmis, gaunamas sujungus įvestis J ir K.

Uždelsimo flip-flop (D-flip-flop) yra sukurtas prijungus keitiklį prie įvesties K, kuri tiekiama tuo pačiu signalu kaip į įėjimą J. Šiuo atveju įėjimas J veikia kaip įėjimas D, o visas įrenginys įgyvendina D. -flip-flop perėjimo lentelė.

Išvada

Šiame darbe buvo aprašyti pagrindiniai automatų veikimo principai. Tuo pačiu metu automatai buvo suskirstyti į abstrakčius ir automatus, naudojamus mikroschemoje. Taip pat automatų teorija yra glaudžiai susijusi su algoritmų teorija.

Studijuoti abstraktūs automatai kaip rezultatas, paskatino aktyvų vystymąsi informatika ir mikroschemų inžinerija, atitinkamai.

Naudotų šaltinių sąrašas

1. Diskretioji matematika. Pamoka. Sayapin A.V., Slivina T.A. SibGAU redakcinis ir leidybos skyrius. Krasnojarskas 2010 163s.

2. Skaitmeninių automatų teorijos paskaitos [ Elektroninis šaltinis]. Paskaitos [Svetainė]. URL: http://www.twirpx.com/file/455856/

Priglobta Allbest.ru

...

Panašūs dokumentai

    Aproksimacijos teorija kaip matematikos šaka, nagrinėjanti matematinių objektų apytikslio atvaizdavimo galimybę. Interpoliacijos daugianario konstravimas. Aproksimacija dalimis daugianario funkcijomis. Programos algoritmas ir jo įgyvendinimas.

    Kursinis darbas, pridėtas 2015-10-18

    Abstrakčių, struktūrinių ir dalinių baigtinių automatų aprašymas. Sinchroninių baigtinių automatų, turinčių įvairių tipų trigerius, veikimas, jų žadinimo signalų apibrėžimas. Kanoninio struktūrinės sintezės metodo pavyzdys. Durų spynos schema.

    pamoka, pridėta 2009-06-07

    Tikimybių teorija – matematikos šaka, tirianti atsitiktinių reiškinių dėsningumus: atsitiktinius įvykius, atsitiktinius dydžius, jų savybes ir operacijas su jais. Tikimybių teorijos uždavinių sprendimo metodai, matematinių lūkesčių ir dispersijos apibrėžimas.

    testas, pridėtas 2012-02-04

    Žaidimo teorija yra matematikos šaka, kurios dalykas yra matematinių priėmimo modelių tyrimas optimalius sprendimus konflikto kontekste. Iteracinis Brown-Robinson metodas. Monotoninis iteracinis algoritmas sprendžiant matricinius žaidimus.

    baigiamasis darbas, pridėtas 2007-08-08

    Grafų teorija kaip diskrečiosios matematikos šaka, tirianti baigtinių aibių savybes su nurodytais ryšiais tarp jų elementų. Pagrindinės grafų teorijos sąvokos. Gretimo ir dažnumo matricos ir jų praktinis naudojimas analizuojant sprendimus.

    santrauka, pridėta 2011-06-13

    Kompiuterinių technologijų tema – problemos, kurias gali išspręsti mašinos. Užduoties sudėtingumo matavimas. Sujungti rūšiavimo algoritmą. Polinominės ir nepolinominės problemos. Nedeterministinio algoritmo samprata. Grafinis vaizdavimas klasifikacija.

    pristatymas, pridėtas 2013-10-22

    Diskrečiosios Furjė transformacijos savybės, pateiktos matematinių formulių pavidalu, labiausiai atitinkančios skaitmeninę informacijos apdorojimo technologiją. Greitojo Furjė transformacijos (FFT) algoritmas, jo svarba programavimui.

    pamoka, pridėta 2014-11-02

    santrauka, pridėta 2011-01-13

    Tam tikros diskrečiosios matematikos dalies tyrimas. 5 užduočių nagrinėjama tema sprendimas su metodiniu aprašymu. Kompiliavimo ir įgyvendinimo metodas tiriamos temos algoritminės programos pavidalu. Programinės įrangos sąsajos kūrimo procedūra ir nurodymai.

    Kursinis darbas, pridėtas 2011-04-27

    Geometrija kaip matematikos šaka, tirianti erdvinius santykius ir formas, taip pat kitus santykius ir formas, savo struktūra panašius į erdvinius. Pagrindiniai šio mokslo formavimosi ir raidos etapai, šiuolaikiniai pasiekimai ir perspektyvos.