Danas ćemo govoriti o mitraljezima, ali ne onim koje vojnici drže u rukama ruska vojska. Govorit ćemo o tako zanimljivom stilu programiranja mikrokontrolera kao što je automatsko programiranje. Tačnije, ovo nije čak ni stil programiranja, već čitav koncept, zahvaljujući kojem programer mikrokontrolera može znatno olakšati svoj život. Zahvaljujući tome mnogi zadaci koji se prezentuju programeru rješavaju se mnogo lakše i jednostavnije, oslobađajući programera od glavobolje. Inače, automatsko programiranje se često naziva SWITCH tehnologija.

Napominjem da je inspiracija za pisanje ovog posta bila serija članaka o SWITCH tehnologiji Vladimir Tatarčevski. Serija članaka se zove “Korišćenje SWITCH tehnologije u razvoju aplikativnog softvera za mikrokontrolere.” Tako da ću u ovom članku pokušati da dam uglavnom primer radnog koda i njegov opis.

Inače, planirao sam seriju članaka posvećenih programiranju, u kojima ću detaljno razmotriti tehnike programiranja za AVR mikrokontrolere, Ne propustite…. Pa, idemo!

Program dosledno izvršava komande koje je dodelio programer. Za redovno kompjuterski program Sasvim je normalno kada je program završio svoje izvršavanje i zaustavio svoje izvršavanje, dok se rezultati svog rada prikazuju na monitoru.

Program mikrokontrolera ne može jednostavno završiti svoje izvršavanje. Zamislite samo da ste uključili plejer ili kasetofon. Pritisnuli ste dugme za napajanje, odabrali željenu pesmu i uživali u muzici. Međutim, kada je muzika prestala da vibrira bubnu opnu vašeg uha, plejer se ukočio i nikako nije reagovao na pritiskanje dugmadi, a još manje na vaš ples s tamburom.

Šta nije u redu s tim? Sve je u redu - kontroler, onaj u dubini vašeg plejera, jednostavno je završio sa izvršavanjem svog programa. Vidite, nekako je nezgodno.

Dakle, odavde zaključujemo da program za mikrokontroler jednostavno ne bi trebao stati. U suštini, trebalo bi da bude beskrajni ciklus- samo u ovom slučaju naš igrač bi radio ispravno. Zatim ću vam pokazati koji dizajni postoje. programski kod za mikrokontrolere, to nisu čak ni dizajni, već neki stilovi programiranja.

Stilovi programiranja.

“Stilovi programiranja” zvuči nekako neshvatljivo, ali dobro. Šta hoću ovim da kažem?Zamislimo da se osoba nikada ranije nije bavila programiranjem, odnosno da je totalni noob.

Ova osoba je pročitala mnogo knjiga o programiranju i proučila sve osnovne konstrukcije jezika.Prikupljao je informacije malo po malo, jer je sada pristup informacijama neograničen. Sve je to dobro, ali kako će izgledati njegovi prvi programi? Čini mi se da neće filozofirati, već će ići putem od jednostavnog do složenog.

Dakle, ovi stilovi su koraci koji vode od jednostavnog nivoa do složenijeg, ali istovremeno i efikasnijeg.

U početku nisam razmišljao ni o jednom karakteristike dizajna programe. Jednostavno sam formirao logiku programa - nacrtao dijagram toka i napisao kod. Zbog toga sam stalno naletao na grabulje. Ali ovo je bio prvi put kada nisam brinuo i koristio sam stil “simple looping”, zatim sam počeo da koristim prekide, onda su bile automatske mašine i idemo...

1. Jednostavno petljanje. U ovom slučaju, program se vrti bez ikakvih trikova, a to ima svoje prednosti i nedostatke. Jedina prednost je jednostavnost pristupa, ne morate smišljati lukave dizajne, pišete kako mislite (postupno kopajući sebi grob).

Void main(void) ( initial_AL(); //inicijalizacija perifernih uređaja while(1) ( Lds_BLINK(); //funkcija LED bljeskalica signal_on(); //funkcija za uključivanje signala signal_off(); //funkcija za isključivanje signala l=button(); //promenljiva odgovorna za pritiskanje tastera switch(l) //U zavisnosti od vrednosti varijable, izvodi se jedna ili druga radnja ( slučaj 1: ( Deistvie1(); //Umesto funkcije može postojati uslovni operator Deistvie2 (); //ili još nekoliko grana prebacite slučaj Deistvie3(); Deistvie4(); Deistvie5(); ); slučaj 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ) ; . . . . . . ) ) )

Radna tačka programa se pomiče redom. U ovom slučaju, sve akcije, uslovi i ciklusi se izvršavaju uzastopno. Kod počinje da se usporava, morate umetnuti mnogo dodatnih uslova, što komplikuje percepciju.

Sve ovo uvelike zbunjuje program, čineći kod spletom uslova. Kao rezultat, ovom kodu se ništa ne može dodati ili oduzeti; on postaje kao monolitni komad. Naravno, kada volumen nije veliki, kod se može mijenjati, ali što dalje ide, postaje sve teži.

Koristeći ovaj pristup, napisao sam nekoliko programa, nisu bili veliki i prilično funkcionalni, ali jasnoća je ostavljala mnogo željenog. Da bih dodao neki novi uslov, morao sam da kopam po celom kodu, jer je sve bilo povezano. To je izazvalo mnogo grešaka i glavobolja. Kompajler je opsovao najbolje što je mogao, otklanjanje grešaka u takvom programu pretvorilo se u pakao.

2. Petlja + prekidi.

Beskonačni ciklus kočenja možete djelomično riješiti korištenjem prekida. Prekidi pomažu da se izađe iz začaranog kruga, pomažu da se ne propusti važan događaj i dodaju dodatnu funkcionalnost (prekidi od tajmera, eksterni prekidi).

Recimo da možete koristiti prekid za obradu dugmadi ili praćenje važnog događaja. Kao rezultat, program postaje vizualniji, ali ne manje zbunjujući.

Nažalost, prekidanje vas neće spasiti od nereda u koji se program pretvara. Nemoguće je podijeliti na dijelove ono što je jedinstvena cjelina.

3. Automatsko programiranje.

Evo nas glavna tema ovog člana. Programiranje u mašinama konačnog stanja eliminira nedostatke koji su inherentni u prva dva primjera. Program postaje jednostavniji i lakši za modifikovanje.

Program napisan automatskim stilom sličan je prekidaču koji se, ovisno o uvjetima, prebacuje u jedno ili drugo stanje. Broj stanja je inicijalno poznat programeru.

Grubo govoreći, to je kao prekidač za svjetlo. Postoje dva stanja uključena i isključena, i dva stanja uključena i isključena. Pa, prvo prvo.

Implementacija multitaskinga u switch tehnologiji.

Mikrokontroler je sposoban da kontroliše opterećenje, trepereće LED diode, prati pritisak na tastere i još mnogo toga. Ali kako sve to učiniti u isto vrijeme? Postoji mnogo rješenja za rješavanje ovog problema. Najjednostavniji od njih koji sam već spomenuo je upotreba prekida.

Tokom rada programa, kada dođe do prekida, kontroler se odvlači od izvršavanja programskog koda i nakratko izvršava drugi dio programa za koji je prekid odgovoran. Prekid će proraditi, tada će radna točka programa nastaviti od tačke u kojoj je kontroler prekinut prekidom (sama riječ označava da je kontroler prekinut).

Drugi način implementacije multitaskinga je korištenje operativni sistemi. Da, zaista, već su se počeli pojavljivati ​​mali OS-ovi, koji se mogu koristiti na kontroleru male snage. Ali često se ova metoda pokaže pomalo suvišnom. Uostalom, zašto trošiti resurse kontrolora nepotrebnim radom kada možete proći uz male troškove.

U programima napisanim tehnologijom switch-a, slična "iluzija" multitaskinga dobija se zahvaljujući sistemu za razmenu poruka. Napisao sam "iluziju" jer je to zapravo slučaj, jer program fizički ne može istovremeno izvršiti različite dijelove koda. Govoriću o sistemu za razmenu poruka malo dalje.

Sistem za razmenu poruka.

Možete riješiti brojne procese i stvoriti iluziju multitaskinga koristeći sistem za razmjenu poruka.

Recimo da nam je potreban program u kojem se LED dioda uključuje. Ovdje imamo dvije mašine, nazovimo ih LEDON - mašina odgovorna za uključivanje LED-a i LEDOFF mašina - mašina odgovorna za gašenje LED-a.

Svaka od mašina ima dva stanja, odnosno mašina može biti u aktivnom stanju ili u neaktivnom stanju, kao prekidač ili uključen ili isključen.

Kada je jedna mašina aktivirana, LED lampica svetli, kada je druga aktivirana, LED se gasi. Pogledajmo mali primjer:

Int main(void) ( INIT_PEREF(); //inicijalizacija perifernih uređaja (LED) InitGTimers(); //inicijalizacija tajmera InitMessages(); //inicijalizacija mehanizma za obradu poruka InitLEDON(); //inicijalizacija LEDON mašine InitLEDOFF(); // inicijalizacija LEDOFF automata SendMessage(MSG_LEDON_ACTIVATE); //aktiviraj LEDON sei(); //Omogući prekida //Glavna petlja programa while(1) ( ProcessLEDON(); //iteracija LEDON automat ProcessLEDOFF(); //iteracija LEDOFF automata ProcessMessages (); //obrada poruke ); )

U redovima 3-7 se dešavaju razne inicijalizacije, tako da nas ovo sada ne zanima. Ali onda se događa sljedeće: prije pokretanja glavne petlje (while(1)), šaljemo poruku mašini

Pošalji poruku(MSG_LEDON_ACTIVATE)

odgovoran za osvjetljavanje LED dioda. Bez ovog malog koraka, naš organ neće raditi. Zatim, glavna beskonačna while petlja obavlja glavni posao.

Mala digresija:

Poruka ima tri stanja. Naime, stanje poruke može biti neaktivno, postavljeno ali neaktivno i aktivno stanje.

Ispostavilo se da je poruka u početku bila neaktivna, a kada smo poslali poruku, dobila je status „instalirana, ali neaktivna“. A ovo nam daje sljedeće. Kada se program izvršava uzastopno, LEDON mašina ne prima poruku. Pojavljuje se iteracija LEDON mašine u stanju mirovanja u kojoj poruka jednostavno ne može biti primljena. Pošto poruka ima status „instaliran, ali neaktivan“, program nastavlja sa izvršavanjem.

Nakon što su sve mašine u stanju mirovanja, na red dolazi funkcija ProcessMessages(). Ova funkcija se uvijek postavlja na kraj petlje, nakon što su sve iteracije automata završene. Funkcija ProcessMessages() jednostavno premješta poruku iz "podešenog, ali neaktivnog" stanja u "aktivno" stanje.

Kada beskonačna petlja završi drugi krug, slika postaje potpuno drugačija. Iteracija ProcessLEDON mašine više neće biti u stanju mirovanja. Mašina će moći primiti poruku, preći u upaljeno stanje i također poslati poruku zauzvrat. Biće adresiran na LEDOFF mašinu i životni ciklus poruke će se ponavljati.

Želio bih napomenuti da se poruke koje imaju "aktivno" stanje uništavaju kada naiđu na funkciju ProcessMessages. Dakle, poruku može primiti samo jedna mašina. Postoji još jedna vrsta poruka - emitovane poruke, ali ih neću razmatrati; one su također dobro pokrivene u člancima Tatarčevskog.

Tajmeri

Uz pomoć ispravne organizacije razmjene poruka, možemo kontrolirati redoslijed rada mašina konačnih stanja, ali to ne možemo učiniti samo s porukama.

Vjerovatno ste primijetili da prethodni fragment programa dat kao primjer neće raditi kako je predviđeno. Mašine će razmjenjivati ​​poruke, LED diode će se prebacivati, ali mi to nećemo vidjeti. Videćemo samo slabo osvetljen LED.

To je zato što nismo razmišljali o tome kako pravilno rješavati kašnjenja. Uostalom, nije nam dovoljno da naizmjenično palimo i gasimo LED diode, LED mora ostati u svakom stanju, recimo na sekundu.

Algoritam će biti sljedeći:

Možete kliknuti za povećanje

Zaboravio sam da dodam na ovoj blok dijagramu da kada tajmer otkucava, naravno da se izvodi radnja - paljenje LED-a ili gašenje.

1. U stanje ulazimo prihvatanjem poruke.

2. Provjeravamo očitanja tajmera/brojala, ako je brojač dostigao, onda izvršavamo akciju, u suprotnom jednostavno šaljemo sebi poruku.

3. Pošaljite poruku sledećoj mašini.

4. Izađite

U sljedećem unosu sve se ponavlja.

Program na SWITCH tehnologiji. Tri koraka.

Hajde da napišemo program u konačnim mašinama, a za to ćemo morati da uradimo samo tri jednostavnim koracima. Program će biti jednostavan, ali vrijedi početi s jednostavnim stvarima. Odgovaraće nam program sa prekidačem LED. Ovo je veoma dobar primjer, pa da ne izmišljamo ništa novo.

Program ću sastaviti na SI jeziku, ali to uopće ne znači da u konačnim mašinama trebate pisati samo u C; sasvim je moguće koristiti bilo koji drugi programski jezik.

Naš program će biti modularan i stoga će biti podijeljen u nekoliko datoteka. Imaćemo sledeće module:

• Modul glavne programske petlje sadrži fajlove leds_blink.c, HAL.c, HAL.h
• Tajmer modul sadrži datoteke timers.c, timers.h
• Modul za obradu poruka sadrži datoteke messages.c, messages.h
  
• Modul mašine 1 sadrži datoteke ledon.c, ledon.h
• Modul mašine 2 sadrži fajlove ledoff.c, ledoff .h

Korak 1.

Kreiramo projekat i odmah povezujemo fajlove naših statičkih modula sa njim: timers.c, timers.h, messages.c, messages.h.

Datoteka leds_blink.c modula glavne programske petlje.

#include "hal.h" #include "messages.h" //modul za obradu poruka #include "timers.h" //tajmer modul //Timer prekida //############# # ################################################## ############################ ISR(TIMER0_OVF_vect) // skače duž vektora prekida (prebacivanje brojača T0 tajmera) ( ProcessTimers(); //Upravljač prekida tajmera) //########################################## # ################################################# int main(void) ( INIT_PEREF(); //inicijalizacija perifernih uređaja (LED) InitGTimers(); //inicijalizacija tajmera InitMessages(); //inicijalizacija mehanizma za obradu poruka InitLEDON(); //inicijalizacija LEDON mašine InitLEDOFF (); StartGTimer( TIMER_SEK); //Pokreni tajmer SendMessage(MSG_LEDON_ACTIVATE); //aktiviraj automat FSM1 sei(); //Omogući prekide //Glavna petlja programa while(1) ( ProcessLEDON(); // iteracija automata LEDON ProcessLEDOFF(); ProcessMessages( ); //obrada poruke ); )

Prvi redovi povezuju preostale module sa glavnim programom. Ovdje vidimo da su modul tajmera i modul za obradu poruka povezani. Sljedeći u tekstu programa je vektor prekida prekoračenja.

Može se reći da glavni program počinje linijom int main (void). I počinje sa inicijalizacijom svega. Ovdje inicijaliziramo periferiju, odnosno postavljamo početne vrijednosti za ulazne/izlazne portove komparatora i sve ostale sadržaje kontrolera. Sve ovo radi funkcija INIT_PEREF; pokrećemo je ovdje, iako je njeno glavno tijelo u hal.c datoteci.

Zatim vidimo inicijalizaciju tajmera, modul za obradu poruka i inicijalizaciju automata. Ovdje se i ove funkcije jednostavno pokreću, iako su same funkcije zapisane u fajlovima njihovih modula. Pogledajte kako je zgodno. Glavni tekst programa ostaje lak za čitanje i nije pretrpan suvišnim kodom koji će vam slomiti noge.

Glavne inicijalizacije su gotove, sada trebamo pokrenuti glavnu petlju. Da bismo to učinili, šaljemo početnu poruku, a također navijamo sat - pokrećemo mjerač vremena.

StartGTimer(TIMER_SEK); //Pokreni tajmer SendMessage(MSG_LEDON_ACTIVATE); //aktiviraj stroj FSM1

A glavni ciklus, kao što sam već rekao, izgleda vrlo jednostavno. Zapisujemo funkcije svih mašina, jednostavno ih upisujemo u kolonu, bez pridržavanja redosleda. Ove funkcije su rukovaoci automatima i nalaze se u modulima automata. Ovu automatsku piramidu upotpunjuje funkcija modula za obradu poruka. Naravno, to sam vam već rekao ranije kada smo se bavili sistemom za slanje poruka. Sada možete vidjeti kako izgledaju još dvije datoteke modula glavnog ciklusa programa

Hal.h je datoteka zaglavlja modula glavne petlje programa.

#ifndef HAL_h #defini HAL_h #include #include //Standardna biblioteka uključujući prekide #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //komparator #define ViklKomparator 1<

Kao što ste možda primijetili, ova datoteka sama po sebi ne sadrži niti jednu liniju izvršnog koda - sve su to zamjene makroa i povezivanje biblioteka. Posjedovanje ove datoteke samo olakšava život, poboljšava vidljivost.

Ali Hal.c datoteka je već izvršna datoteka, i kao što sam već spomenuo, sadrži razne periferne inicijalizacije.

#include "hal.h" void INIT_PEREF(void) ( //Inicijalizacija I/O portova //############################ ### ################################################ ### ##### Komparator = ViklKomparator; //inicijalizacija komparatora - isključivanje DDRD = 1<

Pa, pokazao sam modul glavnog ciklusa programa.Sada ostaje samo da napravimo zadnji korak, treba da napišemo module samih automata.

Korak 3.

Sve što treba da uradimo je da napišemo module za mašine konačnog stanja, u našem slučaju LEDON mašinu i LEDOFF mašinu. Za početak ću dati tekst programa za automatski uređaj koji pali LED, fajl ledon.c.

//datoteka ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; // varijabla stanja void InitLEDON(void) ( ledon_state=0; //ovdje možete inicijalizirati druge //automatske varijable ako su dostupne) void ProcessLEDON(void) ( switch(ledon_state) ( case 0: //neaktivno stanje if(GetMessage ( MSG_LEDON_ACTIVATE)) //ako postoji poruka, ona će biti prihvaćena ( //i tajmer će biti provjeren if(GetGTimer(TIMER_SEK)==one_sek) //ako je tajmer otkucao 1 sekundu, onda se izvrši ( StopGTimer(TIMER_SEK) ); PORTD = 1<

Ovdje se u prvim redovima, kao i uvijek, povezuju biblioteke i deklariraju varijable. Zatim imamo funkcije koje smo već upoznali. Ovo je funkcija inicijalizacije automata InitLEDON i funkcija samog rukovaoca automata ProcessLEDON.

U tijelu rukovatelja, funkcije iz modula tajmera i modula poruka su već obrađene. A logika same mašine napravljena je na osnovu dizajna kućišta prekidača. I ovdje možete primijetiti da se rukovanje strojem također može zakomplikovati dodavanjem nekoliko prekidača za slučaj.

Datoteka zaglavlja za mašinu će biti još jednostavnija:

//datoteka fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcesLEDON(neispravan); #endif

Ovdje uključujemo datoteku za povezivanje hal.h i također ukazujemo na prototipove funkcija.

Fajl odgovoran za gašenje LED-a će izgledati skoro isto samo u zrcalnoj slici, tako da ga neću prikazati ovdje - nerado sam :)

Sve datoteke projekta možete preuzeti sa ovog linka ====>>> VEZA.

Postoje samo tri koraka i naš program je dobio gotovu formu, što znači da je moja današnja misija završena i vrijeme je da je završim. Čini mi se da će vam informacije navedene u ovom članku biti vrlo korisne. Ali stvarnu korist će donijeti samo kada ovo znanje primijenite u praksi.

Inače, isplanirao sam niz zanimljivih projekata koji će biti posebno zanimljivi, pa svakako pretplatite se na nove članke . Također planiram poslati dodatne materijale, tako da se mnogi već pretplate preko glavne stranice stranice. Također se možete pretplatiti ovdje.

E, sad stvarno imam sve, pa ti zelim puno srece, dobro raspolozenje i vidimo se opet.

Od n/a Vladimir Vasiliev

Teorija automata

Definicija mašine i njene sorte. Tabele i grafikoni prijelaza i izlaza. Subautomatske mašine. Teorema redukovanog automata

Operacije sa mašinama

Pretvaranje Mealy mašine u Moore mašinu i Moore mašine u Mealy mašinu. Ekvivalencija automata. Razlikovanje stanja automata. Minimizacija automata. Sinteza automata. Mašine za prepoznavanje

Automatska mašina je sistem mehanizama i uređaja u kojima su procesi prijema, pretvaranja i prenosa energije, materijala i informacija potpuno automatizovani. Termin „automatska mašina“ koristi se u dva aspekta:

1) tehnički,

2) matematički.

U matematičkom pristupu, automat se shvata kao matematički model tehničkog uređaja koji mora imati ulaze, interna stanja i izlaze. Ne bi trebalo biti informacija o detaljima strukture uređaja.

U tehničkom pristupu pod mašinom se podrazumeva sasvim realan uređaj, na primer telefonska govornica, automat itd. U ovom slučaju, naravno, poznati su detalji unutrašnje strukture uređaja.

Poseban i važan slučaj automata je digitalni automat (DA), u kojem su procesi prijema, pretvaranja, pohranjivanja i izdavanja digitalnih informacija potpuno automatizirani.

Sa stanovišta DA signala, korisno je definirati sistem koji može primati ulazne signale, pod njihovim utjecajem, prelaziti iz jednog stanja u drugo, održavati ga do dolaska sljedećeg ulaznog signala i proizvoditi izlazne signale.

DA se smatra konačnim ako su skupovi ulaznih signala X, stanja S i izlaznih signala Y. Konačna mašina može biti povezana sa uređajem kao što je računar. Računar obrađuje ulazne ulazne podatke u izlazne podatke (rezultat), ali ovaj rezultat odgovara ne samo ulaznim podacima, već i trenutnom stanju računara, tj. podaci koji se pohranjuju u memoriji računala, na primjer, rezultati prethodnih proračuna, računski programi.

Rad ciljne publike odvija se u automatskom vremenu, određenom brojem perioda prijema ulaznih signala.

Apstraktni automat je matematički model diskretnog uređaja koji ima jedan ulazni kanal, koji prima nizove simbola nekog jezika, jedan izlazni kanal iz kojeg se preuzimaju nizovi simbola nekog drugog jezika i koji je u svakom trenutku u nekom stanju. diskretnog vremena. Grafički, apstraktni automat je predstavljen na Sl.

Riječi ulaznog jezika mogu se predstaviti simbolima skupa X=(x 1 ,x 2 ,...x n ), koji se naziva ulazna abeceda, a riječi izlaznog jezika su simboli skupa Y=(y 1 ,y 2 ,...y p ), koji se naziva izlazna abeceda. Skup stanja automata S=(s 1 ,s 2 ,...s m ) se naziva abeceda država.

Koncept stanje mašine koristi se za opisivanje sistema čiji izlazni signali ne zavise samo od ulaznih signala u datom trenutku, već i od neke prethodne istorije, tj. signale koji su prethodno primljeni na ulazima sistema. Stoga se digitalni automati odnose na sekvencijalna kola koja, kao što je već napomenuto, imaju memoriju. Koncept stanja automata odgovara nekom sjećanju na prošlost, pa uvođenje ovog koncepta omogućava da se vrijeme eliminira kao eksplicitna varijabla i da se rezultati izraze kao funkcija stanja i ulaza.

Rad apstraktnog automata treba posmatrati u odnosu na specifične vremenske intervale, jer svaki diskretni interval tće odgovarati njegovom izlaznom signalu y(t). Shodno tome, rad mašine se razmatra kroz diskretne vremenske intervale konačnog trajanja. U apstraktnoj teoriji digitalnih automata, vjeruje se da ulazni signali djeluju na sinhroni automat na početku svakog i- taj interval (kvant) vremena dodeljen odgovarajućim sinhronizacionim impulsom (ciklusom), a promena unutrašnjih stanja mašine se dešava u vremenskim intervalima između susednih sinhronizacionih impulsa, kada nema uticaja ulaznih signala.

Koncept “stanja” se koristi za uspostavljanje funkcionalne zavisnosti simbola i/ili reči izlaznog jezika koje generiše mašina o simbolima i/ili rečima ulaznog jezika kada mašina implementira dati algoritam. Za svako stanje automata sOS i za svaki simbol xOX u trenutku diskretnog vremena [t], na izlazu uređaja se generiše simbol yOY. Ova zavisnost je određena izlaznom funkcijom automata j. Za svako trenutno stanje automata sOS i za svaki simbol xOX u trenutku diskretnog vremena [t], automat prelazi u sljedeće stanje sOS. Ova zavisnost je određena tranzicijskom funkcijom automata y. Rad automata sastoji se od generisanja dva niza: niza narednih stanja automata (s 1[ s 2 s 3 ...) i niza izlaznih simbola (y 1 y 2 y 3 ...), koji se za niz simbola (x 1 x 2 x 3...) odvijaju u trenucima diskretnog vremena t = 1,2,3,.... U pravougaonim zagradama označavaju trenutke diskretnog vremena, koji se inače nazivaju takt ciklusa , u zagradama - nizovi znakova abecede X, Y i S.

Dakle, matematički model konačnog automata je troosnovna algebra, čiji su nosioci tri skupa X, Y i S, a operacije su dvije funkcije j i y.

U ovom članku, izraz „mašina konačnog stanja“ odnosi se na algoritam koji može biti u jednom od malog broja stanja. “State” je određeni uvjet koji definira datu vezu između ulaznih i izlaznih signala, kao i ulaznih signala i kasnijih stanja. Inteligentni čitalac će odmah primetiti da su mašine konačnog stanja opisane u ovom članku Mealy mašine. Mealy mašina je mašina konačnog stanja u kojoj su izlazi funkcije trenutnog stanja i ulaznog signala, za razliku od Moore mašine gde su izlazi funkcije samo stanja. U oba slučaja, naknadno stanje je funkcija trenutnog stanja i ulaznog signala.

Pogledajmo primjer jednostavnog konačnog stroja. Zamislite da u tekstualnom nizu trebate prepoznati niz znakova “//”. Slika 1 pokazuje kako se to radi pomoću državnog stroja. Prvo pojavljivanje kose crte ne proizvodi izlazni signal, ali uzrokuje da mašina pređe u drugo stanje. Ako u drugom stanju mašina ne pronađe kosu crtu, vraća se na prvo, jer zahtijeva prisustvo 2 kose crte u nizu. Ako se pronađe druga kosa crta, mašina izdaje signal „spreman“.

Saznajte šta je potrebno kupcu.

Kreirajte dijagram tranzicije stanja

Kodirajte "kostur" državnog stroja bez detalja o operacijama grananja.

Provjerite funkcioniraju li prijelazi ispravno.

Budite konkretni o detaljima tranzicije.

Uradite test.

Primjer državnog stroja

Pogledajmo zanimljiviji primjer državnog stroja - programa koji kontrolira uvlačenje i izvlačenje stajnog trapa aviona. Iako većina aviona ovu proceduru izvodi pomoću elektro-hidrauličkog upravljačkog mehanizma (jednostavno zato što nema kompjutera na brodu), u nekim slučajevima, kao što su bespilotne letjelice, vrijedi koristiti softversko upravljanje.

Prvo, pogledajmo opremu. Stajni trap aviona se sastoji od nosnog trapa, glavnog lijevog stajnog trapa i glavnog desnog stajnog trapa. Pokreću ih hidraulični mehanizam. Hidraulična pumpa na električni pogon dovodi pritisak do pogonskog aktuatora. Pomoću softvera pumpa se uključuje ili isključuje. Računar podešava položaj ventila za smjer - "dolje" ili "gore" - kako bi omogućio pritisak da podigne ili spusti stajni trap. Svaki od nosača šasije ima granični prekidač: jedan od njih se zatvara ako je šasija podignuta, a druga - ako je zaključana u donjem položaju. Da bi se utvrdilo da li je avion na zemlji, granični prekidač na nosnom nosaču se zatvara kada je težina aviona na nosnom zupčaniku. Komande pilota sastoje se od gornjeg/donjeg kraka stajnog trapa i tri svjetla (po jedno za svaku nogu) koja se mogu isključiti, zelena (donji položaj) ili crvena (položaj za kretanje).

Sada pređimo na razvoj mašine konačnog stanja. Prvi i najteži korak je razumjeti stvarna očekivanja kupaca. Jedna od prednosti konačnog automata je to što primorava programera da razmisli o svim mogućim slučajevima i kao rezultat toga dobije sve potrebne informacije od korisnika. Zašto ovo smatram najtežom fazom? I koliko puta vam je dat opis zadatka sličan ovome: nemojte uvlačiti stajni trap ako je avion na zemlji.

Naravno, ovo je važno, ali kupac vjeruje da se tu sve završava. Šta je sa ostalim slučajevima? Da li je dovoljno uvući stajni trap u trenutku kada avion poleti sa zemlje? Šta ako se avion odbije na neravninu na pisti? Šta ako pilot prilikom parkiranja pomakne ručicu mjenjača u gornji položaj i kao rezultat toga počne da polijeće? Da li u ovom slučaju treba podići stajni trap?

Jedna od prednosti razmišljanja u terminima državnog stroja je da možete brzo nacrtati dijagram prijelaza stanja na projekcijskoj ploči, točno ispred kupca, i proći kroz cijeli proces s njim. Prihvaćena je sljedeća oznaka za prijelaz stanja: “događaj koji je izazvao prijelaz”/”izlazni signal kao rezultat prijelaza”. Da smo razvili samo ono što je kupac prvobitno tražio („ne uvlačite stajni trap ako je avion na zemlji“), tada bismo dobili mašinu prikazanu na slici 2.

Kada kreirate dijagram prijelaza stanja (ili bilo koji drugi algoritam), imajte na umu sljedeće:

Računari rade veoma brzo u poređenju sa mehaničkom opremom

Mašinski inženjer koji objašnjava šta treba da se uradi možda ne zna toliko o kompjuterima i algoritmima kao vi. I ovo je također pozitivna stvar, inače ne biste bili potrebni!

Kako će se vaš program ponašati ako se pokvari mehanički ili električni dio?

Državna mašina zasnovana na tome šta korisnik zapravo zahteva je prikazana na slici 3. Ovde želimo da sprečimo da se stajni trap aviona uvuče dok se definitivno ne nađe u vazduhu. Da biste to učinili, nakon otvaranja prekidača za slijetanje, mašina čeka nekoliko sekundi. Takođe želimo da odgovorimo na uzdižuću ivicu pilotove poluge, a ne na nivo, što će izbeći probleme ako neko pomeri ručicu dok je avion u parku. Uvlačenje ili izvlačenje stajnog trapa traje nekoliko sekundi, a moramo biti spremni na situaciju da će se pilot tokom ove operacije predomisliti i pomjeriti ručicu u suprotnom smjeru. Takođe imajte na umu da ako avion ponovo sleti dok smo u stanju "Čekamo polijetanje", tajmer će se ponovo pokrenuti i stajni trap će se povući samo ako je avion u zraku 2 sekunde.

Implementacija konačnog automata

Listing 1 je moja implementacija državnog stroja prikazanog na slici 3. Hajde da razgovaramo o nekim detaljima koda.

/*listing 1*/

typedef enum(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) Vrsta_stanja;

/*Ovaj niz sadrži pokazivače na funkcije pozvane u određenim stanjima*/

void(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

State_Type curr_state;

InitializeLdgGearSM();

/*Srce mašine je ova beskrajna petlja. Funkcija odgovara

Trenutno stanje, pozvano jednom po iteraciji */

dok (1) {

state_table();

DecrementTimer();

void InitializeLdgGearSM( void )

curr_state = GEAR_DOWN;

/*Zaustavljanje opreme, gašenje svjetla itd.*/

void GearDown( void )

/* Prelazak u stanje čekanja ako je avion

Nije na zemlji i dobio komandu za podizanje stajnog trapa*/

ako((ručica_mjenjača == GORE) && (prethodna_poluga_mjenjača == DOLJE) && (prekidač za čučanj == GORE)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

void RaisingGear( void )

ako((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/*Ako je pilot promijenio odluku, idi u stanje "spušteni stajni trap"*/

ako(ručica mjenjača == DOLJE) (

curr_state = LOWERING_GEAR;

void GearUp( void )

/*ako je pilot pomerio ručicu u položaj „dole“,

Idemo u stanje "spuštanje stajnog trapa"*/

ako(ručica mjenjača == DOLJE) (

curr_state = LOWERING_GEAR;

void WtgForTakeoff( void )

/* Pričekajte prije podizanja stajnog trapa.*/

ako(tajmer<= 0.0) {

curr_state = RAISING_GEAR;

/*Ako smo se ponovo dodirnuli ili se pilot predomislio, počnite iznova*/

ako((squat_switch == DOLJE) || (ručica mjenjača == DOLJE)) (

curr_state = GEAR_DOWN;

/* Ne želim da tražim da ponovo prebaci polugu

Ovo je bio samo odskok.*/

prev_gear_lever = DOLJE;

void Spuštanja ( void )

ako(ručica mjenjača == GORE) (

curr_state = RAISING_GEAR;

ako((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

Prvo, možete primijetiti da je funkcionalnost svakog stanja implementirana posebnom C funkcijom. Naravno, bilo bi moguće implementirati automat koristeći naredbu switch sa posebnim velikim slovima za svako stanje, ali to može dovesti do veoma dugačke funkcije (10-20 linija koda po stanju za svako od 20-30 stanja) . Ovo također može dovesti do grešaka ako promijenite kod u završnim fazama testiranja. Možda nikada niste zaboravili izjavu o prekidu na kraju predmeta, ali takvi slučajevi su mi se desili. Kod za jedno stanje nikada neće završiti u kodu za drugo ako imate zasebnu funkciju za svako stanje.

Da izbjegnem korištenje naredbe switch, koristim niz pokazivača na funkcije stanja i proglašavam varijablu koja se koristi kao indeks niza tipa enum.

Radi jednostavnosti, I/O hardver odgovoran za očitavanje stanja prekidača, uključivanje i isključivanje pumpi, itd. je predstavljen kao jednostavne varijable. Pretpostavlja se da su ove varijable "magične adrese" povezane sa hardverom nevidljivim sredstvima.

Druga očigledna stvar je da kod u ovom trenutku zapravo nije bitan. On jednostavno prelazi iz jednog stanja u drugo. Ovo je važan međukorak i ne treba ga zanemariti. Usput, bilo bi lijepo dodati naredbe za ispis između direktiva uvjetne kompilacije (#ifdef DEBUG .. #endif) koje bi ispisivale trenutno stanje i vrijednosti ulaznih signala.

Ključ uspjeha leži u kodu koji uzrokuje tranziciju stanja, tj. utvrđuje da je došlo do unosa podataka.

Ako kod ispravno prođe kroz sva stanja, sljedeći korak je pisanje “ispunjavanja” koda, odnosno tačno ono što proizvodi izlazni signal. Zapamtite da svaki prijelaz ima ulazni signal (događaj koji ga je izazvao) i izlazni signal (hardverski I/O uređaj, kao u našem primjeru). Često je korisno ovo uhvatiti u obliku tablice prijelaza stanja.

U tabeli prijelaza stanja postoji jedan red po prijelazu stanja.

Kada kodirate državni stroj, pokušajte očuvati njegovu snagu—jasnu korespondenciju između zahtjeva korisnika i koda. Možda će biti potrebno sakriti hardverske detalje u drugom funkcionalnom sloju, na primjer, kako bi kod državnog stroja izgledao što je više moguće kao tablica prijelaza stanja i dijagram prijelaza stanja. Ova simetrija pomaže u sprečavanju grešaka i objašnjava zašto su državne mašine tako važan deo arsenala programera ugrađenih sistema. Naravno, isti efekat možete postići sa potvrdnim okvirima i beskonačnim brojem ugniježđenih if naredbi, ali to bi otežalo praćenje koda i upoređivanje sa željama korisnika.

Isječak koda u Listingu 2 proširuje funkciju RaisingGear(). Imajte na umu da kod za funkciju RaisingGear() ima za cilj da ogleda 2 reda prijelazne tablice za stanje Raising Gear.

void RaisingGear( void )

/*Nakon što su svi prekidači podignuti, idemo u stanje "podignuto šasije"*/

ako((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

pump_motor = OFF;

gear_lights = GASI;

curr_state = GEAR_UP;

/*Ako se pilot predomisli, počnite da uvlačite stajni trap*/

ako(ručica mjenjača == DOLJE) (

pump_direction = DOLJE;

curr_state = GEAR_LOWERING;

Ne zaboravite da izbjegavate latentna stanja. Skriveno stanje nastaje kada, iz lijenosti, pokušate dodati uvjetno podstanje umjesto da dodate određeno stanje. Na primjer, ako vaš kod obrađuje isti ulazni signal na različite načine (tj. pokreće različite prijelaze stanja) ovisno o načinu rada, onda je to skriveno stanje. U ovom slučaju, pitao bih se da li ovo stanje treba podijeliti na dva? Korištenje skrivenih stanja negira korist korištenja državnog stroja.

Kao praksa, možete produžiti mašinu stanja koju smo upravo pogledali dodavanjem vremenskog ograničenja ciklusu uvlačenja ili produženja stajnog trapa, jer... Mašinski inženjer ne želi da hidraulična pumpa radi duže od 60 sekundi. Ako se ciklus završi, pilot mora biti upozoren uključivanjem zelenog i crvenog svjetla i mora moći ponovo pomaknuti ručicu da pokuša ponovo. Takođe biste mogli da pitate hipotetičkog mašinskog inženjera kakav je efekat promene smera pumpe dok ona radi na pumpu, jer se to dešava u dva slučaja kada se pilot predomisli. Naravno, mehaničar će reći da je negativan. Kako biste onda modificirali državni stroj da brzo zaustavi pumpu prilikom promjene smjera?

Testiranje državnog stroja

Ljepota algoritama kodiranja kao državnih mašina je u tome što se plan testiranja gotovo automatski piše sam. Sve što trebate učiniti je proći kroz svaku tranziciju stanja. Obično to radim s markerom u ruci, precrtavajući strelice na dijagramu prijelaza stanja dok prolaze test. Ovo je dobar način da se izbjegnu "skrivena stanja" - ona se češće propuštaju u testovima nego specifična stanja.

Za to je potrebno znatno strpljenje i puno kafe, jer čak i državni stroj srednje veličine može imati do 100 različitih prijelaza. Inače, broj tranzicija je odličan način za mjerenje složenosti sistema. Potonje je određeno zahtjevima korisnika, a državni stroj čini obim testiranja očiglednim. Uz manje organiziran pristup, količina potrebnog testiranja može biti jednako impresivna, ali to jednostavno nećete znati.

Vrlo je zgodno koristiti ispisne izjave u svom kodu koje prikazuju trenutno stanje i vrijednosti ulaznih i izlaznih signala. Ovo vam omogućava da lako uočite šta Zlatno pravilo testiranja softvera izražava: proverite da li program radi ono što je namenjen i da ne radi ništa nepotrebno. Drugim riječima, da li dobijate samo rezultate koje očekujete, i šta se još dešava osim toga? Postoje li "teški" prijelazi stanja, tj. stanja koja nasumično prolaze samo za jedno ponavljanje petlje? Da li se rezultati mijenjaju kada to ne očekujete? U idealnom slučaju, izlaz vaših printf-ova trebao bi primjetno nalikovati tablici prijelaza stanja.

Konačno – a ovo se odnosi na bilo koji ugrađeni softver, a ne samo na softver baziran na državnom stroju – budite vrlo oprezni kada prvi put pokrenete softver na stvarnom hardveru. Vrlo je lako pogrešiti polaritet signala - "Oh, mislio sam da 1 znači da stajni trap gore, a 0 da je stajni trap spušten." U mnogim slučajevima, moj hardverski asistent bi koristio privremeni "pileći prekidač" da zaštiti vrijedne komponente sve dok ne bude siguran da moj softver pokreće stvari u pravom smjeru.

Pokreni

Kada se ispune svi zahtjevi korisnika, mogu pokrenuti državni stroj slične složenosti za nekoliko dana. Gotovo uvijek mašine rade ono što ja želim. Najteže je, naravno, shvatiti tačno šta kupac želi i uveriti se da sam kupac zna šta želi. Ovo poslednje traje mnogo duže!

Martin Gomez je programer u Laboratoriji za primijenjenu fiziku na Univerzitetu Johns Hopkins. Bavi se razvojem softvera za podršku letovima istraživačkih svemirskih letjelica. Radio je u oblasti razvoja ugrađenih sistema 17 godina. Martin je diplomirao vazduhoplovstvo i magistrirao elektrotehniku ​​na Univerzitetu Cornell.

Članak govori o jednostavnim mašinama konačnih stanja i njihovoj implementaciji u C++ koristeći konstrukcije prekidača, runtime tablice i Boost Statechart biblioteku.

Uvod

Grubo rečeno, mašina konačnog stanja je očima korisnika crna kutija u koju se nešto može prenijeti i odatle primiti. Ovo je veoma zgodna apstrakcija koja vam omogućava da sakrijete složeni algoritam, a mašine sa konačnim stanjem su takođe veoma efikasne.

Konačne mašine su prikazane u obliku dijagrama koji se sastoje od stanja i prelaza. Dozvolite mi da objasnim jednostavnim primjerom:

Kao što ste verovatno pretpostavili, ovo je dijagram stanja sijalice. Početno stanje je označeno crnim krugom, prelazi strelicama, neke strelice su označene - to su događaji nakon kojih mašina prelazi u drugo stanje. Dakle, odmah iz početnog stanja, nalazimo se u tom stanju Light Off- lampa ne pali. Ako pritisnete dugme, mašina će promeniti svoje stanje i pratiti označenu strelicu Pritisnite dugme, u stanju Light On- lampa je upaljena. Možete preći iz ovog stanja, ponovo prateći strelicu, nakon pritiska na dugme, u stanje Light Off.

Prijelazni stolovi također se široko koriste:

Praktična primjena automatskih mašina

Konačne mašine se široko koriste u programiranju. Na primjer, vrlo je zgodno zamisliti rad uređaja u obliku automatske mašine. Ovo će učiniti kod jednostavnijim i lakšim za eksperimentiranje i održavanje.

Takođe, mašine konačnih stanja se koriste za pisanje svih vrsta parsera i analizatora teksta; uz njihovu pomoć možete efikasno tražiti podstringove; regularni izrazi se takođe prevode u konačnu mašinu.

Na primjer, implementiraćemo automat za brojanje brojeva i riječi u tekstu. Za početak, složimo se da će se broj smatrati nizom brojeva od 0 do 9 proizvoljne dužine, okružen razmakom (razmak, tabulator, pomak reda). Riječ će se smatrati nizom proizvoljne dužine koji se sastoji od slova i također je okružen razmacima.

Pogledajmo dijagram:

Iz početnog stanja dolazimo do stanja Počni. Provjeravamo trenutni znak, a ako je slovo, onda idemo u stanje Riječ duž strelice označene kao Pismo. Ovo stanje pretpostavlja da trenutno razmatramo riječ; analiza daljnjih simbola će ili potvrditi ovu pretpostavku ili je opovrgnuti. Dakle, uzmite u obzir sljedeći znak, ako je slovo, onda se stanje ne mijenja (obratite pažnju na kružnu strelicu označenu kao Pismo). Ako znak nije slovo, već odgovara razmaku, to znači da je pretpostavka bila tačna i da smo pronašli riječ (pratimo strelicu Prostor u državi Počni). Ako znak nije ni slovo ni razmak, onda smo pogriješili u pretpostavci i niz koji razmatramo nije riječ (prati strelicu Nepoznato u državi Skip).

U stanju Skip mi smo tamo dok se ne naiđe na razmak. Nakon što se otkrije praznina, pratimo strelicu Prostor u državi Počni. Ovo je neophodno da biste u potpunosti preskočili red koji ne odgovara našem obrascu pretraživanja.

Nakon ulaska u državu Počni, ciklus pretraživanja se ponavlja od početka. Grana za prepoznavanje brojeva slična je grani za prepoznavanje riječi.

Automatski pomoću instrukcija za prebacivanje

Prva su moguća stanja:

Nakon toga iterujemo preko reda, ubacujući trenutni simbol u mašinu. Sam automat je instrukcija prekidača koja prvo vrši prijelaz na dio trenutnog stanja. Unutar sekcije nalazi se if-else konstrukcija, koja, u zavisnosti od događaja (dolaznog simbola), menja trenutno stanje:

const size_t dužina = text.length(); for (size_t i = 0 ; i ! = dužina; ++ i) ( const char struja = tekst[ i] ; prekidač (stanje) ( case State_Start: if (std:: isdigit (trenutna) ) ( state = State_Number; ) inače if (std:: isalpha (trenutno) ) ( stanje = State_Word; ) break ; case State_Number: if (std:: isspace (trenutno) ) (

Ovdje gledamo dijagram - trenutno stanje Broj, događaj Prostor(naiđe se na razmak), što znači da je broj pronađen:

PronađeniBroj() ; stanje = Start_state; ) else if (! std::isdigit(current)) (stanje = State_Skip; ) break; case State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (trenutni) ) ( state = State_Skip; ) break ; case State_Skip: if (std::isspace (trenutni) ) (stanje = State_Start; ) break ; ) )

rezultat:

Visoka efikasnost

Lakoća implementacije za jednostavne algoritme

- Teško za održavanje

Runtime Interpretation

Ideja ovog pristupa je jednostavna - potrebno je kreirati prijelaznu tablicu, popuniti je, a zatim, kada se dogodi neki događaj, pronaći sljedeće stanje u tablici i izvršiti prijelaz:

enum Događaji (Event_Space, Event_Digit, Event_Letter, Event_Unknown ) ; void ProcessEvent(Događaji događaj) ; ... struct Transition (Stanje BaseState_; Događaji Događaj_; State TargetState_; ) ; void AddTransition(State fromState, Events event, States to State) ; ...typedef std::vector< transition>TransitionTable; TransitionTable Transitions_; State CurrentState_;

Popunjavanje tabele:

AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(broj_stanje, prostor_događaja, početak_stanje) ; AddTransition(broj_stanje, slovo_događaja, preskakanje stanja) ; AddTransition(State_Number, Event_Unknown, State_Skip) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

Ispostavilo se sasvim jasno. Cena za jasnoću će biti sporiji rad mašine, što, međutim, često nije bitno.

Kako bi mašina, kada se dogode određeni događaji, mogla obavijestiti neki kod, možete ga dodati u strukturu s informacijama o tranziciji ( Tranzicija) pokazivač funkcije ( Akcija), koji će se zvati:

typedef void (DynamicMachine::* Akcija) () ; struct Transition (Stanje BaseState_; Događaji Event_; State TargetState_; Action Action_; ) ; ... void AddTransition(State fromState, Events event, States toState, Action action) ; ...AddTranzition(State_Number, Event_Space, State_Start, & DynamicMachine::FoundNumber) ;

rezultat:

Fleksibilnost i vidljivost

Lakše za održavanje

- Niže performanse u poređenju sa blokovima prekidača

Tumačenje vremena izvršenja. Optimizacija brzine

Da li je moguće spojiti vidljivost sa brzinom? Malo je vjerovatno da će biti moguće napraviti automatsku mašinu jednako efikasnom kao automatska mašina zasnovana na blokovima prekidača, ali je moguće zatvoriti jaz. Da biste to učinili, morate napraviti matricu iz tablice, tako da za dobivanje informacija o tranziciji ne morate pretraživati, već napraviti odabir prema stanju i broju događaja:

Rezultat se postiže na račun potrošnje memorije.

rezultat:

Fleksibilnost, vidljivost

Efektivno

- Potrošnja memorije (najvjerovatnije beznačajna)

Boost Statechart

Razgovarali smo o nekoliko načina da sami implementirate državni stroj. Za promenu, predlažem da razmotrimo biblioteku za pravljenje mašina iz Boosta. Ova biblioteka je veoma moćna; ponuđene mogućnosti vam omogućavaju da izgradite veoma složene mašine konačnog stanja. Pogledaćemo to prilično brzo.

Dakle, prvo definišemo događaje:

imenski prostor Događaji ( struct Digit : boost::statechart::event< Digit>( ) ; struct Letter : boost::statechart::event< Letter>( ) ; struct Space: boost::statechart::event< Space>( ) ; struct Nepoznato : boost::statechart::event< Unknown> { } ; }

Sama mašina (imajte na umu da je drugi parametar šablona početno stanje):

struct Machine: boost::statechart::state_machine< Machine, States:: Start > { } ;

I same države. Unutar stanja potrebno je odrediti tip koji opisuje prelaze ( reakcije), a ako postoji nekoliko prijelaza, navedite ih na popisu tipova boost::mpl::list. Drugi parametar šablona jednostavno_stanje– tip koji opisuje mašinu. Prijelazi su opisani parametrima prijelaznog šablona, ​​par Događaj - Sljedeće stanje:

imenski prostor države ( struct Start : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reakcije; ) ; struct Number : boost::statechart::simple_state< Number, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Letter , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reakcije; ) ; struct Word: boost::statechart::simple_state< Word, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Digit , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reakcije; ) ; struct Skip: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >reakcije; ) ; )

Mašina je napravljena, ostaje samo da je inicijalizirate i možete je koristiti:

Strojna mašina; machine.initiate(); ...machine.process_event(Događaji::Space());

rezultat:

Fleksibilnost, proširivost

- Efikasnost

Performanse

Napisao sam testni program da provjerim performanse izgrađenih mašina. Proveo sam ~17 MB teksta kroz mašine. Evo rezultata trčanja:

Učitavanje teksta Dužina teksta: 17605548 bajtova 0,19 s Pokrenute riječi BoostMachine: 998002, brojevi: 6816 0,73 s Pokrenute riječi DynamicMachine: 998002, brojevi: 6816 0,56 s: Pokrenute riječi za Machine: 998002 .29 s Pokretanje SimpleMachine Words: 998002, brojevi : 6816 0,20 s

Šta je ostalo neispitano

Ostalo je još nekoliko implementacija mašina konačnog stanja koje je ostalo nepokriveno (preporučujem http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml i http://www.rsdn.ru/article/alg/FiniteStateMachine.xml) , generatori koji grade mašine iz opisa, biblioteka Meta State Machine iz Boost verzije 1.44.0, kao i formalni opisi mašina konačnih stanja. Radoznali čitalac može se sam upoznati sa svim navedenim.

Teorija automata je grana diskretne matematike koja proučava modele konvertora diskretnih informacija. Takvi pretvarači su i stvarni uređaji (računari, živi organizmi) i imaginarni uređaji (aksiomatske teorije, matematičke mašine). U suštini, mašina konačnog stanja može se okarakterisati kao uređaj M , koji ima ulazne i izlazne kanale, iu svakom od diskretnih trenutaka vremena, koji se nazivaju momenti sata, nalazi se u jednom od konačnih stanja.

Po ulaznom kanalu u svakom trenutku vremena t =1, 2, ... uređaju M dolaze ulazni signali (iz nekog konačnog skupa signala). Zakon promjene stanja u sljedećem trenutku postavlja se ovisno o ulaznom signalu i stanju uređaja u trenutnom trenutku. Izlazni signal zavisi od stanja i ulaznog signala u trenutnom vremenu (slika 1).

Mašina konačnog stanja je matematički model stvarnih diskretnih uređaja za obradu informacija.

Državni stroj zove sistem A= (X , Q , Y ,  ,  ), Gdje X , Q , Y su proizvoljni neprazni konačni skupovi, i  I  - funkcije, od kojih:

gomila X ={a 1 , ..., a m ) se zove ulazna abeceda , a njegovi elementi su ulazni signali , njihove sekvence su u uobičajenim riječima ;

gomila Q ={q 1 , ..., q n ) se zove mnoge države automat, i njegovi elementi - države ;

gomila Y ={b 1 , ..., b str ) se zove izlazna abeceda , njegovi elementi su izlazni signali , njihove sekvence su izlazne riječi ;

funkcija  : X  Q Q pozvao tranzicijska funkcija ;

funkcija  :X  Q Y pozvao izlazna funkcija .

dakle,  (x , q )Q ,  (x , q )Y za  x X , q Q .

Mašina konačnog stanja povezana je sa imaginarnim uređajem koji radi na sljedeći način. Može biti u jednoj od mnogih država Q , percipiraju signale iz raznih X i izdaju signale od raznih Y .

2. Metode za specificiranje konačnog stroja

Postoji nekoliko ekvivalentnih načina za definiranje apstraktnih automata, među kojima se mogu imenovati tri: tabelarni , geometrijski I funkcionalan .

2.1 Tabelarni zadatak mašine

Iz definicije automata proizilazi da se uvijek može specificirati pomoću tabele sa dva ulaza koja sadrže T linije i P kolone, gdje na raskrsnici kolone q i žice A su vrijednosti funkcije  (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. Određivanje automata pomoću Mooreovog dijagrama

Drugi način definiranja konačnog stroja je grafički, odnosno korištenje grafa. Automat je prikazan kao označeni usmjereni graf G(Q , D ) sa mnogo vrhova Q i mnogo lukova D ={(q j ,  (a i , q j ))| q j Q , a i X ), dok je luk ( q j ,  (a i , q j )) je označen sa parom ( a i ,  (a i , q j )). Dakle, ovom metodom, stanja mašine su prikazana kružićima u kojima su ispisani simboli stanja q j (j = 1, …, n ). Iz svakog kruga se izvodi T strelice (orijentisani rubovi) jedan prema jedan koji odgovaraju znakovima ulazne abecede X ={a 1 , ..., a m ). Strelica koja odgovara slovu a i X i napuštaju krug q j Q , pripisuje se paru ( a i ,  (a i , q j )), a ova strelica vodi do odgovarajućeg kruga  (a i , q j ).

Rezultirajući crtež se zove automatski graf ili, Mooreov dijagram . Za ne baš složene mašine, ova metoda je vizualnija od tabelarni.