Dnes bude řeč o kulometech, ale ne o těch, které vojáci drží v rukou ruská armáda. Budeme mluvit o tak zajímavém stylu programování mikrokontrolérů, jako je automatické programování. Přesněji se ani nejedná o programovací styl, ale o celý koncept, díky kterému si programátor mikrokontrolérů může výrazně usnadnit život. Díky tomu je mnoho úloh předkládaných programátorovi vyřešeno mnohem snadněji a jednodušeji, což programátora zbavuje bolestí hlavy. Mimochodem, automatické programování se často nazývá Technologie SWITCH.

Rád bych poznamenal, že inspirací k napsání tohoto příspěvku bylo série článků o technologii SWITCH Vladimír Tatarchevskij. Série článků se jmenuje „Využití technologie SWITCH při vývoji aplikačního softwaru pro mikrokontroléry.“ V tomto článku se tedy pokusím především uvést příklad fungujícího kódu a jeho popis.

Mimochodem, naplánoval jsem sérii článků věnovaných programování, ve kterých se budu podrobně zabývat programovacími technikami pro mikrokontroléry AVR, Nenechte si ujít…. No, pojďme!

Program důsledně provádí příkazy přidělené programátorem. Pro pravidelné počítačový program Je zcela normální, když program dokončil své provádění a zastavil své provádění, zatímco výsledky své práce zobrazuje na monitoru.

Program mikrokontroléru nemůže jednoduše dokončit své provádění. Jen si představte, že jste zapnuli přehrávač nebo magnetofon. Stiskli jste vypínač, vybrali požadovanou skladbu a užili si hudbu. Když však hudba přestala vibrovat bubínkem vašeho ucha, přehrávač zamrzl a nijak nereagoval na mačkání tlačítek, tím méně na váš tanec s tamburínou.

Co je na tom špatné? Vše je v pořádku – ovladač, ten v hloubi vašeho přehrávače, prostě dokončil svůj program. Vidíte, je to nějak nepohodlné.

Odtud tedy docházíme k závěru, že program pro mikrokontrolér by se prostě neměl zastavit. V podstatě by to tak mělo být nekonečný koloběh- pouze v tomto případě by náš přehrávač fungoval správně. Dále vám ukážu, jaké návrhy existují. programový kód u mikrokontrolérů to ani nejsou návrhy, ale nějaké styly programování.

Styly programování.

„Styly programování“ zní nějak nesrozumitelně, ale ouha. Co tím chci říct? Představme si, že člověk nikdy předtím neprogramoval, to znamená, že je totální noob.

Tato osoba přečetla mnoho knih o programování a prostudovala všechny základní konstrukce jazyka.Sbíral informace kousek po kousku, protože přístup k informacím je nyní neomezený. To je všechno v pořádku, ale jak budou vypadat jeho první programy? Zdá se mi, že nebude filozofovat, ale půjde cestou od jednoduchého ke složitému.

Tyto styly jsou tedy kroky vedoucí od jednoduché úrovně ke složitější, ale zároveň efektivnější.

Zpočátku jsem o žádném nepřemýšlel Designové vlastnosti programy. Jednoduše jsem vytvořil logiku programu - nakreslil vývojový diagram a napsal kód. Proto jsem pořád narážel na hrábě. Ale bylo to poprvé, kdy jsem se nebál a použil styl „jednoduché smyčky“, pak jsem začal používat přerušení, pak byly automaty a jedeme...

1. Jednoduchá smyčka. V tomto případě se program zacyklí bez jakýchkoliv triků, a to má své klady i zápory. Jedinou výhodou je jednoduchost přístupu, nemusíte vymýšlet mazané návrhy, píšete, jak myslíte (postupně si kopete hrob).

Void main(void) ( initial_AL(); //inicializace periferií while(1) ( Leds_BLINK(); //funkce LED blikač signal_on(); //funkce pro zapnutí signálu signal_off(); //funkce pro vypnutí signálu l=button(); //proměnná zodpovědná za stisknutí tlačítek switch(l) //V závislosti na hodnotě proměnné se provede jedna nebo druhá akce (případ 1: ( Deistvie1(); //Místo funkce může existovat podmíněný operátor Deistvie2 (); //nebo několik dalších větví přepnout případ Deistvie3(); Deistvie4(); Deistvie5(); ); případ 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ) ;.......))))

Pracovní bod programu se pohybuje v pořadí. V tomto případě se všechny akce, podmínky a cykly provádějí postupně. Kód se začne zpomalovat, musíte vložit spoustu podmínek navíc, a tím komplikovat vnímání.

To vše program značně mate, takže kód je spleť podmínek. Výsledkem je, že z tohoto kódu nelze nic přidat ani odebrat, stává se jako monolitický kus. Samozřejmě, když objem není velký, kód lze upravit, ale čím dále, tím je to obtížnější.

Pomocí tohoto přístupu jsem napsal několik programů, nebyly velké a docela funkční, ale srozumitelnost zůstala velmi potřebná. Abych přidal nějakou novou podmínku, musel jsem se prohrabat celým kódem, protože všechno bylo svázané. To způsobilo spoustu chyb a bolesti hlavy. Kompilátor nadával, jak mohl, odladění takového programu se změnilo v peklo.

2. Smyčka + přerušení.

Nekonečný brzdný cyklus můžete částečně vyřešit pomocí přerušení. Přerušení pomáhají vymanit se ze začarovaného kruhu, pomáhají nezmeškat důležitou událost a přidávají další funkce (přerušení od časovačů, externí přerušení).

Řekněme, že můžete přerušení použít ke zpracování tlačítek nebo sledování důležité události. V důsledku toho se program stává vizuálnějším, ale ne méně matoucím.

Přerušení vás bohužel nezachrání od nepořádku, do kterého se program promění. Není možné rozdělit na části to, co je jediným celkem.

3. Automatické programování.

Tady se dostáváme hlavní téma tohoto článku. Programování v konečných automatech odstraňuje nevýhody spojené s prvními dvěma příklady. Program se stává jednodušším a snadno upravitelný.

Program napsaný automatickým stylem je podobný přepínači, který se v závislosti na podmínkách přepne do jednoho nebo druhého stavu. Počet stavů je programátorovi zpočátku znám.

Zhruba řečeno, je to jako vypínač. Existují dva stavy zapnuto a vypnuto a dvě podmínky zapnuto a vypnuto. No, první věci.

Implementace multitaskingu v technologii switchů.

Mikrokontrolér je schopen ovládat zátěž, blikat LED diody, sledovat stisk kláves a mnoho dalšího. Ale jak to všechno udělat zároveň? Existuje mnoho řešení, jak tento problém vyřešit. Nejjednodušší z nich, které jsem již zmínil, je použití přerušení.

Během provozu programu, když dojde k přerušení, je kontrolér odveden od provádění programového kódu a krátce provede další část programu, za kterou je přerušení odpovědné. Přerušení bude fungovat, pak bude pracovní bod programu pokračovat od bodu, kde byl regulátor přerušením přerušen (samotné slovo znamená, že regulátor je přerušen).

Dalším způsobem, jak implementovat multitasking, je použití operační systémy. Ano, skutečně se již začaly objevovat malé OS, které lze použít na nízkoenergetickém ovladači. Často se ale tato metoda ukáže jako poněkud nadbytečná. Koneckonců, proč plýtvat zdroji ovladače zbytečnou prací, když si vystačíte s malými náklady.

V programech napsaných pomocí technologie switch je podobná „iluze“ multitaskingu získána díky systému zpráv. Napsal jsem „iluzi“, protože to tak ve skutečnosti je, protože program fyzicky nemůže provádět různé části kódu současně. O systému zpráv budu mluvit trochu dále.

Systém zpráv.

Pomocí systému zpráv můžete vyřešit mnoho procesů a vytvořit iluzi multitaskingu.

Řekněme, že potřebujeme program, ve kterém se LED spíná. Zde máme dva stroje, říkejme jim LEDON - stroj zodpovědný za rozsvícení LED a stroj LEDOFF - stroj zodpovědný za vypnutí LED.

Každý ze strojů má dva stavy, to znamená, že stroj může být v aktivním stavu nebo v neaktivním stavu, jako je zapnutí nebo vypnutí.

Když je jeden stroj aktivován, LED se rozsvítí, když je aktivován druhý, LED zhasne. Podívejme se na malý příklad:

Int main(void) ( INIT_PEREF(); //inicializace periferií (LED) InitGTimers(); //inicializace časovačů InitMessages(); //inicializace mechanismu zpracování zpráv InitLEDON(); //inicializace stroje LEDON InitLEDOFF(); // inicializace automatu LEDOFF SendMessage(MSG_LEDON_ACTIVATE); //aktivace LEDON sei(); //Povolení přerušení //Hlavní smyčka programu while(1) ( ProcessLEDON(); //iterace Automat LEDON ProcessLEDOFF(); //iterace automatu LEDOFF ProcessMessages (); //zpracování zpráv ); )

V řádcích 3-7 dochází k různým inicializacím, takže nás to nyní nijak zvlášť nezajímá. Pak se ale stane následující: před spuštěním hlavní smyčky (while(1)) odešleme zprávu do stroje

Odeslat zprávu (MSG_LEDON_ACTIVATE)

zodpovědný za rozsvícení LED. Bez tohoto malého krůčku náš orgán nebude fungovat. Dále hlavní nekonečná smyčka while vykoná hlavní práci.

Malá odbočka:

Zpráva má tři stavy. Konkrétně stav zprávy může být neaktivní, nastavený, ale neaktivní a aktivní stav.

Ukázalo se, že zpráva byla zpočátku neaktivní, když jsme zprávu odeslali, obdržela stav „nainstalovaná, ale neaktivní“. A to nám dává následující. Když je program spouštěn postupně, stroj LEDON zprávu neobdrží. Nastane nečinná iterace stroje LEDON, ve které zprávu jednoduše nelze přijmout. Protože zpráva má stav „nainstalováno, ale neaktivní“, program pokračuje ve svém provádění.

Poté, co jsou všechny stroje nečinné, přichází řada na funkci ProcessMessages(). Tato funkce je vždy umístěna na konec cyklu, po dokončení všech iterací automatů. Funkce ProcessMessages() jednoduše přesune zprávu ze stavu „set but inactive“ do stavu „active“.

Když nekonečná smyčka dokončí druhé kolo, obraz se úplně změní. Iterace stroje ProcessLEDON již nebude nečinná. Stroj bude schopen přijmout zprávu, přejít do rozsvíceného stavu a také zprávu odeslat. Bude adresováno stroji LEDOFF a životní cyklus zprávy se budou opakovat.

Chtěl bych poznamenat, že zprávy, které mají stav „aktivní“, jsou zničeny, když narazí na funkci ProcessMessages. Zprávu tedy může přijmout pouze jeden stroj. Existuje další typ zpráv - vysílané zprávy, ale nebudu je zvažovat; jsou také dobře pokryty v článcích Tatarchevského.

Časovače

Pomocí správné organizace výměny zpráv můžeme řídit pořadí činnosti konečných automatů, ale nemůžeme to dělat pouze pomocí zpráv.

Pravděpodobně jste si všimli, že předchozí fragment programu uvedený jako příklad nebude fungovat tak, jak bylo zamýšleno. Stroje si vymění zprávy, LED diody se přepnou, ale my to neuvidíme. Uvidíme pouze slabě svítící LED.

Je to proto, že jsme nepřemýšleli, jak správně zvládnout zpoždění. Nestačí nám totiž střídavě rozsvěcet a zhasínat LED, LEDka musí v každém stavu setrvat, řekněme vteřinu.

Algoritmus bude následující:

Kliknutím zvětšíte

K tomuto blokovému schématu jsem zapomněl dodat, že po odtiknutí časovače se samozřejmě provede akce - rozsvícení LED nebo zhasnutí.

1. Do stavu vstupujeme přijetím zprávy.

2. Zkontrolujeme odečty časovače/počítadla, pokud počet dosáhl, pak provedeme akci, jinak jednoduše pošleme zprávu sami sobě.

3. Odešlete zprávu dalšímu počítači.

4. Konec

V dalším vstupu se vše opakuje.

Program na technologii SWITCH. Tři kroky.

Napišme program v konečných automatech a k tomu budeme potřebovat pouze tři jednoduché kroky. Program bude jednoduchý, ale vyplatí se začít s jednoduchými věcmi. Vyhovovat nám bude program se spínací LED. Toto je velmi dobrý příklad, tak nevymýšlejme nic nového.

Program sestavím v jazyce SI, ale to vůbec neznamená, že v konečných automatech musíte psát pouze v C, je docela možné použít jakýkoli jiný programovací jazyk.

Náš program bude modulární, a proto bude rozdělen do několika souborů. Budeme mít následující moduly:

• Modul hlavní programové smyčky obsahuje soubory leds_blink.c, HAL.c, HAL.h
• Modul časovače obsahuje soubory timers.c, timers.h
• Modul zpracování zpráv obsahuje soubory messages.c, messages.h
  
• Modul stroje 1 obsahuje soubory ledon.c, ledon.h
• Modul stroje 2 obsahuje soubory ledoff.c, ledoff .h

Krok 1.

Vytvoříme projekt a ihned k němu připojíme soubory našich statických modulů: timers.c, timers.h, messages.c, messages.h.

Soubor leds_blink.c modulu hlavní programové smyčky.

#include "hal.h" #include "messages.h" //modul zpracování zpráv #include "timers.h" //modul časovačů //Přerušení časovače //############# # ################################################# # ############################ ISR(TIMER0_OVF_vect) // skok podél vektoru přerušení (přetečení časovače čítače T0) ( ProcessTimers(); //Obsluha přerušení časovače) //######################################## # ################################################# int main(void) ( INIT_PEREF(); //inicializace periferií (LED) InitGTimers(); //inicializace časovačů InitMessages(); //inicializace mechanismu zpracování zpráv InitLEDON(); //inicializace stroje LEDON InitLEDOFF (); StartGTimer( TIMER_SEK); //Spuštění časovače SendMessage(MSG_LEDON_ACTIVATE); //aktivace automatu FSM1 sei(); //Povolení přerušení //Hlavní smyčka programu while(1) ( ProcessLEDON(); // iterace automatu LEDON ProcessLEDOFF(); ProcessMessages( ); //zpracování zpráv; )

První řádky spojují zbývající moduly s hlavním programem. Zde vidíme, že modul časovače a modul zpracování zpráv jsou propojeny. Další v textu programu je vektor přerušení přetečení.

O hlavním programu lze říci, že začíná řádkem int main (void). A začíná to inicializací všeho. Zde inicializujeme periferie, to znamená, že nastavíme počáteční hodnoty pro vstupní/výstupní porty komparátoru a veškerý další obsah řadiče. To vše dělá funkce INIT_PEREF, spustíme ji zde, ačkoli její hlavní tělo je v souboru hal.c.

Dále vidíme inicializaci časovačů, modul zpracování zpráv a inicializaci automatů. Zde se tyto funkce také jednoduše spouštějí, ačkoli samotné funkce jsou zapsány v souborech jejich modulů. Podívejte se, jak je to pohodlné. Hlavní text programu zůstává dobře čitelný a není zahlcen nadbytečným kódem, ze kterého se vám budou podlamovat nohy.

Hlavní inicializace jsou u konce, nyní musíme spustit hlavní smyčku. Za tímto účelem odešleme úvodní zprávu a také natáhneme hodinky - spustíme časovač.

StartGTimer(TIMER_SEK); //Spuštění časovače SendMessage(MSG_LEDON_ACTIVATE); //aktivace stroje FSM1

A hlavní cyklus, jak jsem již řekl, vypadá velmi jednoduše. Zapisujeme funkce všech strojů, jednoduše je zapisujeme do sloupce, aniž bychom dodržovali pořadí. Tyto funkce jsou manipulátory automatů a jsou umístěny v modulech automatů. Tuto automatickou pyramidu doplňuje funkce modulu zpracování zpráv. Samozřejmě jsem vám to řekl již dříve, když jsme řešili systém odesílání zpráv. Nyní můžete vidět, jak vypadají další dva soubory modulu hlavního cyklu programu

Hal.h je hlavičkový soubor modulu hlavní smyčky programu.

#ifndef HAL_h #define HAL_h #include #zahrnout //Standardní knihovna včetně přerušení #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

Jak jste si možná všimli, tento soubor ze své podstaty neobsahuje jediný řádek spustitelného kódu – jsou to všechny substituce maker a propojující knihovny. S tímto souborem je život velmi snadný, zlepšuje viditelnost.

Ale soubor Hal.c je již spustitelný soubor a jak jsem již zmínil, obsahuje různé periferní inicializace.

#include "hal.h" void INIT_PEREF(void) ( //Inicializace I/O portů //############################ ### ############################################### ### ##### Komparátor = ViklKomparator; //inicializace komparátoru - vypnutí DDRD = 1<

No, ukázal jsem modul hlavního cyklu programu.Nyní zbývá udělat poslední krok, musíme napsat moduly samotných automatů.

Krok 3

Jediné, co musíme udělat, je napsat moduly pro konečné automaty, v našem případě stroj LEDON a stroj LEDOFF. Pro začátek uvedu text programu pro automatické zařízení, které svítí LED, soubor ledon.c.

//soubor ledon.c #include "ledon.h" #include "times.h" #include "messages.h" unsigned char ledon_state; //stavová proměnná void InitLEDON(void) ( ledon_state=0; //zde můžete inicializovat další //automatické proměnné, pokud jsou k dispozici) void ProcessLEDON(void) ( switch(ledon_state) ( případ 0: //neaktivní stav if(GetMessage ( MSG_LEDON_ACTIVATE)) //pokud je zde zpráva, bude přijata ( //a časovač bude zkontrolován, pokud(GetGTimer(TIMER_SEK)==one_sek) //pokud časovač dosáhl 1 sekundy, pak spusťte ( StopGTimer(TIMER_SEK ); PORTD = 1<

Zde se v prvních řádcích jako vždy propojují knihovny a deklarují proměnné. Dále máme funkce, se kterými jsme se již setkali. Toto je inicializační funkce automatu InitLEDON a funkce samotného ovladače automatu ProcessLEDON.

V těle handleru jsou již zpracovány funkce z modulu časovače a modulu zpráv. A logika samotného stroje je vytvořena na základě konstrukce rozvaděče. A zde si můžete všimnout, že ovládání stroje může být také komplikované přidáním několika přepínačů.

Soubor záhlaví pro stroj bude ještě jednodušší:

//soubor fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

Zde zahrneme propojovací soubor hal.h a také označujeme funkční prototypy.

Soubor zodpovědný za vypnutí LED bude vypadat téměř stejně pouze v zrcadlovém obraze, takže ho zde nebudu zobrazovat - zdráhám se :)

Všechny soubory projektu si můžete stáhnout z tohoto odkazu ====>>> ODKAZ.

Jsou to jen tři kroky a náš program má hotovou podobu, což znamená, že moje dnešní mise skončila a je čas to zabalit. Zdá se mi, že informace uvedené v tomto článku pro vás budou velmi užitečné. Skutečný užitek ale přinese až tehdy, když tyto znalosti uplatníte v praxi.

Mimochodem, naplánoval jsem řadu zajímavých projektů, které budou obzvlášť zajímavé, tak určitě přihlásit k odběru nových článků . Plánuji také rozesílat další materiály, takže mnozí se již přihlašují přes hlavní stránku webu. Můžete se také přihlásit k odběru zde.

No a teď už mám opravdu všechno, tak přeji hodně štěstí, skvělou náladu a zase na viděnou.

Od n/a Vladimír Vasiliev

Teorie automatů

Definice stroje a jeho rozmanitost. Tabulky a grafy přechodů a výstupů. Sub-automatické stroje. Věta o redukovaném automatu

Operace se stroji

Převod stroje Mealy na stroj Moore a stroje Moore na stroj Mealy. Ekvivalence automatů. Rozlišení stavů automatů. Minimalizace automatů. Syntéza automatů. Rozpoznávací stroje

Automat je systém mechanismů a zařízení, ve kterém jsou procesy příjmu, přeměny a přenosu energie, materiálů a informací plně automatizovány. Termín „automatický stroj“ se používá ve dvou aspektech:

1) technický,

2) matematické.

Automat je v matematickém přístupu chápán jako matematický model technického zařízení, které musí mít vstupy, vnitřní stavy a výstupy. Neměly by existovat žádné informace týkající se podrobností o struktuře zařízení.

V technickém pojetí se strojem rozumí velmi reálné zařízení, například telefonní budka, prodejní automat atd. V tomto případě jsou samozřejmě známy detaily vnitřní struktury zařízení.

Zvláštním a důležitým případem automatu je digitální automat (DA), ve kterém jsou procesy příjmu, konverze, ukládání a vydávání digitálních informací plně automatizovány.

Z hlediska DA signálů je užitečné definovat systém, který dokáže přijímat vstupní signály pod jejich vlivem přecházet z jednoho stavu do druhého, udržovat jej do příchodu dalšího vstupního signálu a produkovat výstupní signály.

DA je považován za konečný, pokud jsou konečné sady vstupních signálů X, stavů S a výstupních signálů Y. Konečný automat může být spojen se zařízením, jako je počítač. Počítač zpracuje příchozí vstupní data na výstupní data (výsledek), ale tento výsledek odpovídá nejen vstupním datům, ale i aktuálnímu stavu počítače, tzn. data, která jsou uložena v paměti počítače, například výsledky předchozích výpočtů, výpočetní programy.

Práce cílového publika se provádí v automatickém čase, určeném počtem period příjmu vstupních signálů.

Abstraktní automat je matematický model diskrétního zařízení, které má jeden vstupní kanál, který přijímá sekvence symbolů jazyka, jeden výstupní kanál, ze kterého se berou sekvence symbolů jiného jazyka, a je v každém okamžiku v nějakém stavu. diskrétního času. Graficky je abstraktní automat představen na Obr.

Slova vstupního jazyka mohou být reprezentována symboly množiny X=(x 1 ,x 2 ,...x n ), která je tzv. vstupní abeceda, a slova výstupního jazyka jsou symboly množiny Y=(y 1 ,y 2 ,...y p ), která se nazývá výstupní abeceda. Množina stavů automatu S=(s 1 ,s 2 ,...s m ) se nazývá abeceda států.

Pojem stav stroje se používá k popisu systémů, jejichž výstupní signály závisí nejen na vstupních signálech v daném čase, ale také na nějaké předchozí historii, tzn. signály, které byly dříve přijímány na systémových vstupech. Proto digitální automaty odkazují na sekvenční obvody, které, jak již bylo uvedeno, mají paměť. Pojem stavu automatu odpovídá nějaké paměti minulosti, takže zavedení tohoto pojmu umožňuje eliminovat čas jako explicitní proměnnou a výstupy vyjádřit jako funkci stavů a ​​vstupů.

Provoz abstraktního automatu je třeba posuzovat ve vztahu ke konkrétním časovým intervalům, protože každý diskrétní interval t bude odpovídat jeho výstupnímu signálu y(t). V důsledku toho je provoz stroje zvažován prostřednictvím diskrétních časových intervalů s konečnou dobou trvání. V abstraktní teorii digitálních automatů se věří, že vstupní signály působí na synchronní automat na začátku každého i- interval (kvanta) času přidělený odpovídajícím synchronizačním impulsem (cyklem) a změna vnitřních stavů stroje nastává v časových intervalech mezi sousedními synchronizačními impulsy, kdy nedochází k ovlivnění vstupních signálů.

Pojem „stav“ se používá ke stanovení funkční závislosti symbolů a/nebo slov výstupního jazyka generovaného strojem na symbolech a/nebo slovech vstupního jazyka, když stroj implementuje daný algoritmus. Pro každý stav automatu sОS a pro každý symbol xОX v okamžiku diskrétního času [t] je na výstupu zařízení generován symbol yОY. Tato závislost je určena výstupní funkcí automatu j. Pro každý aktuální stav automatu sОS a pro každý symbol xОX v okamžiku diskrétního času [t] přejde automat do dalšího stavu sОS. Tato závislost je určena přechodovou funkcí automatu y. Činnost automatu spočívá ve generování dvou sekvencí: sekvence dalších stavů automatu (s 1[ s 2 s 3 ...) a sekvence výstupních symbolů (y 1 y 2 y 3 ...), které se pro posloupnost symbolů (x 1 x 2 x 3...) odvíjejí v okamžicích diskrétního času t = 1,2,3,.... V obdélníkových závorkách označují okamžiky diskrétního času, které se jinak nazývají hodinové cykly , v závorce - sekvence znaků abeced X, Y a S.

Matematický model konečného automatu je tedy třízákladní algebra, jejímž nositelem jsou tři množiny X, Y a S a operacemi jsou dvě funkce j a y.

V tomto článku termín „konečný automat“ odkazuje na algoritmus, který může být v jednom z malého počtu stavů. „Stav“ je určitá podmínka, která definuje daný vztah mezi vstupními a výstupními signály, jakož i vstupními signály a následnými stavy. Inteligentní čtenář si okamžitě všimne, že konečné automaty popsané v tomto článku jsou stroje Mealy. Mealyův stroj je konečný stavový stroj, kde výstupy jsou funkcemi aktuálního stavu a vstupního signálu, na rozdíl od Moorova stroje, kde jsou výstupy pouze funkcemi stavu. V obou případech je následný stav funkcí aktuálního stavu a vstupního signálu.

Podívejme se na příklad jednoduchého konečného automatu. Představte si, že v textovém řetězci potřebujete rozpoznat sekvenci znaků „//“. Obrázek 1 ukazuje, jak se to provádí pomocí stavového automatu. První výskyt lomítka nevytváří výstupní signál, ale způsobí, že stroj přejde do druhého stavu. Pokud ve druhém stavu stroj nenajde lomítko, vrátí se k prvnímu, protože vyžaduje přítomnost 2 lomítek za sebou. Pokud je nalezeno druhé lomítko, stroj vydá signál „připraven“.

Zjistěte, co zákazník potřebuje.

Vytvořte diagram přechodu stavu

Zakódujte „kostru“ stavového automatu bez podrobností o operacích větví.

Ujistěte se, že přechody fungují správně.

Buďte konkrétní ohledně podrobností přechodu.

Udělej test.

Příklad státního stroje

Podívejme se na zajímavější příklad stavového stroje – programu, který řídí zatahování a vysouvání podvozku letadla. Přestože většina letadel provádí tento postup pomocí elektrohydraulického ovládacího mechanismu (prostě proto, že na palubě není počítač), v některých případech, jako například u bezpilotních prostředků, se vyplatí použít softwarové ovládání.

Nejprve se podíváme na výbavu. Podvozek letadla se skládá z příďového podvozku, hlavního levého podvozku a hlavního pravého podvozku. Jsou poháněny hydraulickým mechanismem. Elektricky poháněné hydraulické čerpadlo dodává tlak do pohonu. Pomocí softwaru se pumpa zapíná nebo vypíná. Počítač nastavuje polohu směrového ventilu – „dolů“ nebo „nahoru“ – aby umožnil tlak ke zvednutí nebo snížení podvozku. Každá z podpěr podvozku má koncový spínač: jeden z nich se zavře, pokud je podvozek zvednutý, druhý - pokud je uzamčen v dolní poloze. K určení, zda je letadlo na zemi, se koncový spínač na vzpěře příďového podvozku sepne, když je hmotnost letadla na příďovém podvozku. Ovládací prvky pilota se skládají z horního/spodního ramene podvozku a tří světel (jedno pro každou nohu), které lze vypnout, zelené (dolní poloha) nebo červené (poloha jít).

Nyní přejděme k vývoji konečného automatu. Prvním a nejtěžším krokem je pochopit skutečná očekávání zákazníka. Jednou z výhod konečných automatů je, že nutí programátora promyslet všechny možné případy a ve výsledku tak od zákazníka dostat všechny požadované informace. Proč považuji tuto fázi za nejtěžší? A kolikrát jste dostali popis úkolu podobný tomuto: nezatahujte podvozek, pokud je letadlo na zemi.

To je samozřejmě důležité, ale zákazník věří, že tady to všechno končí. A co zbytek případů? Stačí zatáhnout podvozek ve chvíli, kdy letadlo vzlétne ze země? Co když letadlo narazí na hrbol na ranveji? Co když pilot při parkování přesune řadicí páku do horní polohy a v důsledku toho začne startovat? Měl by se v tomto případě zvednout podvozek?

Jednou z výhod uvažování v podmínkách stavového automatu je, že můžete rychle nakreslit stavový přechodový diagram na projekční tabuli přímo před zákazníkem a projít si s ním celý proces. Pro přechod stavu je akceptováno následující označení: „událost, která způsobila přechod“/„výstupní signál jako výsledek přechodu“. Pokud bychom vyvinuli pouze to, co zákazník původně požadoval („nezatahujte podvozek, pokud je letadlo na zemi“), dostali bychom stroj znázorněný na obrázku 2.

Při vytváření diagramu přechodu stavu (nebo jakéhokoli jiného algoritmu) mějte na paměti následující:

Počítače pracují velmi rychle ve srovnání s mechanickým zařízením

Strojní inženýr, který vysvětluje, co je třeba udělat, nemusí vědět o počítačích a algoritmech tolik jako vy. A to je také pozitivní věc, jinak byste nebyli potřeba!

Jak se bude váš program chovat, když se rozbije mechanická nebo elektrická část?

Stavový stroj podle toho, co zákazník skutečně požaduje, je znázorněn na obrázku 3. Zde chceme zabránit zatažení podvozku letadla, dokud nebude definitivně ve vzduchu. Za tímto účelem po otevření spínače přistání stroj několik sekund čeká. Chceme také reagovat na stoupající hranu páky pilota spíše než na úroveň, což zabrání problémům, pokud někdo pohne pákou, když je letadlo v parku. Zasunutí nebo vysunutí podvozku trvá pár sekund a musíme být připraveni na situaci, že si to pilot při této operaci rozmyslí a páku posune opačným směrem. Všimněte si také, že pokud letadlo znovu přistane, když jsme ve stavu „Čekání na vzlet“, časovač se restartuje a podvozek se zasune, pouze pokud je letadlo ve vzduchu po dobu 2 sekund.

Implementace konečného automatu

Výpis 1 je moje implementace stavového automatu znázorněného na obrázku 3. Pojďme diskutovat o některých podrobnostech kódu.

/*výpis 1*/

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

/*Toto pole obsahuje ukazatele na funkce volané v určitých stavech*/

prázdnota(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

State_Type curr_state;

InitializeLdgGearSM();

/*Srdcem stroje je tato nekonečná smyčka. Funkce odpovídající

Aktuální stav, voláno jednou za iteraci */

zatímco (1) {

state_table();

DecrementTimer();

prázdnota InitializeLdgGearSM( prázdnota )

curr_state = GEAR_DOWN;

/*Zastavení zařízení, zhasnutí světel atd.*/

prázdnota Podřadit( prázdnota )

/* Přejděte do stavu čekání, pokud letadlo

Ne na zemi a dostal příkaz ke zvednutí podvozku*/

-li((řadicí_páka == UP) && (prev_gear_lever == DOLŮ) && (přepínač na dřep == NAHORU)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

prázdnota RaisingGear( prázdnota )

-li((nosegear_is_up == VYROBENO) && (leftgear_is_up == VYROBENO) && (rtgear_is_up == VYROBENO)) (

curr_state = GEAR_UP;

/*Pokud pilot změnil své rozhodnutí, přejděte do stavu „podvozek nižší“*/

-li(řadicí páka == DOLŮ) (

curr_state = LOWERING_GEAR;

prázdnota GearUp( prázdnota )

/*pokud pilot přesunul páku do polohy „dolů“,

Přejdeme do stavu „spouštění podvozku“*/

-li(řadicí páka == DOLŮ) (

curr_state = LOWERING_GEAR;

prázdnota WtgForTakeoff( prázdnota )

/* Před zvednutím podvozku počkejte.*/

-li(časovač<= 0.0) {

curr_state = ZVÝŠENÍ_GEAR;

/*Pokud jsme se znovu dotkli nebo pilot změnil názor, začněte znovu*/

-li((squat_switch == DOLŮ) || (řadicí_páka == DOLŮ)) (

curr_state = GEAR_DOWN;

/* Nechci po něm vyžadovat, aby znovu přepnul páku

Tohle byl jen odraz.*/

prev_gear_lever = DOLŮ;

prázdnota Snížení převodového stupně( prázdnota )

-li(řadicí páka == NAHORU) (

curr_state = ZVÝŠENÍ_GEAR;

-li((nosegear_is_down == VYROBENO) && (leftgear_is_down == VYROBENO) &&(rtgear_is_down == VYROBENO)) (

curr_state = GEAR_DOWN;

Nejprve si můžete všimnout, že funkčnost každého stavu je implementována samostatnou C funkcí. Samozřejmě by bylo možné implementovat automat pomocí příkazu switch se samostatným případem pro každý stav, ale to může vést k velmi dlouhé funkci (10-20 řádků kódu na stav pro každý z 20-30 stavů) . To může také vést k chybám, pokud změníte kód v závěrečných fázích testování. Možná jste nikdy nezapomněli na prohlášení o přerušení na konci případu, ale takové případy se mi staly. Kód pro jeden stát nikdy neskončí v kódu pro jiný, pokud máte pro každý stav samostatnou funkci.

Abych se vyhnul použití příkazu switch, používám pole ukazatelů k uvedení funkcí a deklaruji proměnnou použitou jako index pole za typ enum.

Pro jednoduchost je I/O hardware zodpovědný za čtení stavu spínačů, zapínání a vypínání čerpadel atd. reprezentován jako jednoduché proměnné. Předpokládá se, že tyto proměnné jsou "magické adresy" spojené s hardwarem neviditelnými prostředky.

Další zřejmá věc je, že na kódu v tomto bodě opravdu nezáleží. Jednoduše se přesune z jednoho státu do druhého. Toto je důležitý mezikrok a neměl by být ignorován. Mimochodem, bylo by hezké přidat tiskové příkazy mezi direktivy podmíněné kompilace (#ifdef DEBUG .. #endif), které by vytiskly aktuální stav a hodnoty vstupních signálů.

Klíč k úspěchu spočívá v kódu, který způsobí přechod stavu, tzn. určuje, že došlo k zadání dat.

Pokud kód projde všemi stavy správně, dalším krokem je zapsat „náplň“ kódu, tedy přesně to, co produkuje výstupní signál. Pamatujte, že každý přechod má vstupní signál (událost, která jej způsobila) a výstupní signál (hardwarové I/O zařízení, jako v našem příkladu). Často je užitečné to zachytit ve formě tabulky přechodů stavů.

V tabulce přechodu stavu je jeden řádek na přechod stavu.

Při kódování stavového automatu se snažte zachovat jeho sílu – jasnou shodu mezi požadavky zákazníka a kódem. Může být nutné skrýt detaily hardwaru v jiné funkční vrstvě, například aby se kód stavového automatu co nejvíce podobal tabulce přechodů stavů a ​​diagramu přechodu stavů. Tato symetrie pomáhá předcházet chybám a vysvětluje, proč jsou stavové automaty tak důležitou součástí arzenálu programátorů vestavěných systémů. Stejného efektu byste samozřejmě mohli dosáhnout pomocí zaškrtávacích políček a nekonečného počtu vnořených příkazů if, ale to by velmi znesnadnilo sledování kódu a jeho porovnání s přáním zákazníka.

Fragment kódu ve výpisu 2 rozšiřuje funkci RaisingGear(). Všimněte si, že kód pro funkci RaisingGear() má za cíl zrcadlit 2 řádky tabulky přechodů pro stav Raising Gear.

prázdnota RaisingGear( prázdnota )

/*Po zvednutí všech spínačů přejdeme do stavu „podvozek zvednutý“*/

-li((nosegear_is_up == VYROBENO) && (leftgear_is_up == VYROBENO) && (rtgear_is_up == VYROBENO)) (

čerpadlo_motor = VYP;

gear_lights = Zhasnout;

curr_state = GEAR_UP;

/*Pokud si to pilot rozmyslí, začněte zatahovat podvozek*/

-li(řadicí páka == DOLŮ) (

pump_direction = DOLŮ;

curr_state = GEAR_LOWERING;

Nezapomeňte se vyhnout latentním stavům. Skrytý stav nastane, když se z lenosti pokusíte přidat podmíněný podstav namísto přidání konkrétního stavu. Pokud váš kód například zpracovává stejný vstupní signál různými způsoby (tj. spouští různé přechody stavů) v závislosti na režimu, jedná se o skrytý stav. V tomto případě by mě zajímalo, zda by se tento stát měl rozdělit na dva? Použití skrytých stavů neguje výhodu použití stavového automatu.

V praxi můžete stavový stroj, na který jsme se právě dívali, prodloužit přidáním časového limitu do cyklu zatahování nebo vysunutí podvozku, protože... Strojní inženýr nechce, aby hydraulické čerpadlo běželo déle než 60 sekund. Pokud cyklus skončí, pilot musí být upozorněn přepínáním zeleného a červeného světla a musí být schopen znovu pohnout pákou, aby to zkusil znovu. Můžete se také zeptat hypotetického strojního inženýra, jaký vliv má obrácení směru čerpadla za chodu na čerpadlo, protože se to stane ve dvou případech, kdy si to pilot rozmyslí. Mechanik samozřejmě řekne, že je to negativní. Jak byste tedy upravili stavový automat, aby rychle zastavil čerpadlo při změně směru?

Testování státních strojů

Krása kódovacích algoritmů jako stavových automatů spočívá v tom, že testovací plán se zapisuje téměř automaticky sám. Jediné, co musíte udělat, je projít každým přechodem stavu. Obvykle to dělám s fixem v ruce a přeškrtávám šipky na diagramu přechodu stavu, když projdou testem. Je to dobrý způsob, jak se vyhnout „skrytým stavům“ – ty se v testech míjejí častěji než konkrétní stavy.

To vyžaduje značnou trpělivost a hodně kávy, protože i středně velký stavový automat může mít až 100 různých přechodů. Mimochodem, počet přechodů je skvělý způsob, jak měřit složitost systému. Ten je dán požadavky zákazníka a ze stavu automatu je rozsah testování zřejmý. S méně organizovaným přístupem může být množství požadovaného testování stejně působivé, ale jednoduše to nepoznáte.

Je velmi výhodné použít v kódu tiskové příkazy, které zobrazují aktuální stav a hodnoty vstupních a výstupních signálů. To vám umožní snadno pozorovat, co vyjadřuje Zlaté pravidlo testování softwaru: zkontrolujte, zda program dělá to, k čemu je určen, a také, že nedělá nic zbytečného. Jinými slovy, dostáváte pouze výstupy, které očekáváte, a co dalšího se děje nad rámec toho? Existují nějaké „obtížné“ přechody stavů, tzn. stavy, které náhodně projdou pouze pro jedno opakování smyčky? Mění se výstupy, když to neočekáváte? V ideálním případě by výstup vašeho printfs měl nápadně připomínat tabulku přechodů stavů.

A konečně – a to platí pro jakýkoli vestavěný software, nejen pro software založený na státních strojích – buďte velmi opatrní, když poprvé spustíte software na skutečném hardwaru. Je velmi snadné zaměnit polaritu signálu - "Ach, myslel jsem, že 1 znamená přistávací zařízení nahoru a 0 znamená přistávací zařízení dolů." V mnoha případech můj hardwarový asistent používal dočasný „kuřecí spínač“ k ochraně cenných součástí, dokud si nebyl jistý, že můj software posouvá věci správným směrem.

Zahájení

Když jsou splněny všechny požadavky zákazníka, mohu za pár dní spustit stavový automat podobné složitosti. Téměř vždy stroje dělají, co chci. Nejtěžší je samozřejmě pochopit, co přesně zákazník chce, a ujistit se, že zákazník sám ví, co chce. To druhé trvá mnohem déle!

Martin Gomez je programátor v laboratoři aplikované fyziky na Johns Hopkins University. Zabývá se vývojem softwaru na podporu letů výzkumných kosmických lodí. V oblasti vývoje vestavěných systémů působí 17 let. Martin má bakalářský titul v oboru leteckého inženýrství a magisterský titul v oboru elektrotechnika na Cornellově univerzitě.

Článek pojednává o jednoduchých konečných automatech a jejich implementaci v C++ pomocí konstrukcí přepínačů, runtime tabulek a knihovny Boost Statechart.

Úvod

Zhruba řečeno, konečný stavový stroj je očima uživatele černá skříňka, do které lze něco přenést a něco odtud přijímat. Jedná se o velmi pohodlnou abstrakci, která vám umožňuje skrýt složitý algoritmus a velmi efektivní jsou také konečné automaty.

Konečné automaty jsou znázorněny ve formě diagramů sestávajících ze stavů a ​​přechodů. Dovolte mi to vysvětlit na jednoduchém příkladu:

Jak asi tušíte, jedná se o stavový diagram žárovky. Počáteční stav je označen černým kroužkem, přechody šipkami, některé šipky jsou označeny - to jsou události, po kterých stroj přejde do jiného stavu. Okamžitě z výchozího stavu se tedy ocitáme ve stavu Zhasnout- lampa se nerozsvítí. Pokud stisknete tlačítko, stroj změní svůj stav a bude postupovat podle označené šipky Stiskněte tlačítko, ve státě Rozsvítit- lampa svítí. Z tohoto stavu se opět po šipce přesunete po stisknutí tlačítka do stavu Zhasnout.

Přechodové tabulky jsou také široce používány:

Praktická aplikace automatů

Konečné automaty jsou široce používány v programování. Například je velmi vhodné si představit provoz zařízení ve formě automatického stroje. Díky tomu bude kód jednodušší a bude se s ním snadněji experimentovat a udržovat.

Konečné automaty se také používají k zápisu všech druhů parserů a textových analyzátorů, s jejich pomocí lze efektivně vyhledávat podřetězce, regulární výrazy jsou také překládány do konečného automatu.

Implementujeme například automat na počítání čísel a slov v textu. Pro začátek se shodneme, že za číslo bude považována posloupnost čísel od 0 do 9 libovolné délky, obklopená mezerami (mezera, tabulátor, odřádkování). Slovo bude považováno za posloupnost libovolné délky sestávající z písmen a také obklopená mezerami.

Podívejme se na diagram:

Z výchozího stavu se dostáváme do stavu Start. Zkontrolujeme aktuální znak, a pokud je to písmeno, pak přejdeme do stavu Slovo podél šipky označené jako Dopis. Tento stav předpokládá, že právě uvažujeme o slovu, analýza dalších symbolů tento předpoklad buď potvrdí, nebo vyvrátí. Zvažte tedy další znak, pokud je to písmeno, pak se stav nemění (všimněte si kruhové šipky označené jako Dopis). Pokud znak není písmeno, ale odpovídá prázdnému znaku, znamená to, že předpoklad byl správný a slovo jsme našli (postupujeme podle šipky Prostor ve státě Start). Pokud znak není ani písmeno, ani mezera, pak jsme udělali chybu v předpokladu a sekvence, kterou zvažujeme, není slovo (podle šipky Neznámý ve státě Přeskočit).

Schopný Přeskočit jsme tam, dokud nenarazíme na znak mezery. Po zjištění mezery postupujeme podle šipky Prostor ve státě Start. To je nutné k úplnému přeskočení řádku, který neodpovídá našemu vyhledávacímu vzoru.

Po vstupu do stavu Start, cyklus vyhledávání se opakuje od začátku. Větev rozpoznávání čísel je podobná větvi rozpoznávání slov.

Automat pomocí instrukcí přepínače

První jsou možné stavy:

Poté iterujeme přes řádek a vsuneme aktuální symbol do stroje. Samotný automat je instrukce switch, která nejprve provede přechod do sekce aktuálního stavu. Uvnitř sekce je konstrukce if-else, která v závislosti na události (příchozí symbol) mění aktuální stav:

const size_t length = text.length(); for (velikost_t i = 0 ; i ! = délka; ++ i) ( const char current = text[ i] ; switch (stav) ( case State_Start: if (std:: isdigit (current) ) ( state = State_Number; ) else if (std:: isalpha (aktuální) ) ( stav = Stavové_slovo; ) break ; case Číslo_stavu: if (std:: isspace (aktuální) ) (

Zde se podíváme na schéma - aktuální stav Číslo, událost Prostor(je nalezen znak mezery), což znamená, že bylo nalezeno číslo:

FoundNumber() ; stav = State_Start; ) else if (! std::isdigit(aktuální) ) ( state = State_Skip; ) break ; case State_Word: if (std:: isspace (aktuální) ) ( FoundWord() ; stav = State_Start; ) else if (! std:: isalpha (aktuální) ) ( stav = State_Skip; ) break ; case State_Skip: if (std::isspace (aktuální) ) ( stav = State_Start; ) break ; ))

Výsledek:

Vysoká účinnost

Snadná implementace pro jednoduché algoritmy

- Náročné na údržbu

Interpretace za běhu

Myšlenka tohoto přístupu je jednoduchá - musíte vytvořit tabulku přechodů, vyplnit ji a poté, když dojde k události, najít další stav v tabulce a provést přechod:

enum Události ( Event_Space, Event_Digit, Event_Letter, Event_Unknown) ; void ProcessEvent(událost událostí) ; ... struct Transition ( States BaseState_; Events Event_; States TargetState_; ) ; void AddTransition(States fromState, Events Event, States toState) ; ...typedef std::vector< transition>TransitionTable; TransitionTable Přechody_; Stavy CurrentState_;

Vyplnění tabulky:

AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(číslo_stavu, prostor_událostí, začátek_stavu) ; AddTransition(číslo_stavu, písmeno_události, přeskočení_stavu) ; AddTransition(Číslo_stavu, Neznámá_Událost, Přeskočit_Stav) ; AddTransition(Stav_slovo, prostor_udalosti, stav_začátek) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(Stav_slovo, Udalost_Neznámá, Stav_Přeskočit) ; AddTransition(State_Skip, Event_Space, State_Start) ;

Ukázalo se to celkem jasně. Cenou za přehlednost bude pomalejší chod stroje, který však často nevadí.

Aby stroj, když nastanou určité události, mohl upozornit nějaký kód, můžete jej přidat do struktury s informacemi o přechodu ( Přechod) ukazatel funkce ( Akce), který se bude jmenovat:

typedef void (DynamicMachine::* Akce) () ; struct Transition ( States BaseState_; Events Event_; States TargetState_; Action Action_; ); ... void AddTransition(States fromState, Events Event, States toState, Action action) ; ...AddTransition(State_Number, Event_Space, State_Start, & DynamicMachine::FoundNumber) ;

Výsledek:

Flexibilita a viditelnost

Jednodušší na údržbu

- Nižší výkon ve srovnání s bloky spínačů

Interpretace doby provedení. Optimalizace rychlosti

Je možné kombinovat viditelnost s rychlostí? Je nepravděpodobné, že bude možné vyrobit automatický stroj tak účinný jako automatický stroj založený na spínacích blocích, ale je možné tuto mezeru uzavřít. Chcete-li to provést, musíte z tabulky vytvořit matici, abyste získali informace o přechodu, nemusíte hledat, ale provést výběr podle stavu a čísla události:

Výsledek je dosažen na úkor spotřeby paměti.

Výsledek:

Flexibilita, přehlednost

Efektivní

- Spotřeba paměti (s největší pravděpodobností nevýznamná)

Boost Statechart

Probrali jsme několik způsobů, jak sami implementovat stavový automat. Pro změnu navrhuji zvážit knihovnu pro stavbu strojů od Boost. Tato knihovna je velmi výkonná; nabízené schopnosti vám umožňují vytvářet velmi složité konečné automaty. Podíváme se na to celkem rychle.

Nejprve tedy definujeme události:

jmenný prostor Události ( struct Digit : boost::statechart::event< Digit>( ); struct Letter : boost::statechart::event< Letter>( ); struct Prostor: boost::statechart::event< Space>( ); struct Neznámý : boost::statechart::event< Unknown> { } ; }

Samotný stroj (všimněte si, že druhý parametr šablony je počáteční stav):

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

A státy samotné. Uvnitř stavů je nutné určit typ, který popisuje přechody ( reakce), a pokud existuje několik přechodů, uveďte je v seznamu typů boost::mpl::list. Druhý parametr šablony jednoduchý_stav– typ popisující stroj. Přechody jsou popsány parametry šablony přechodu, dvojice Událost - Další stav:

jmenný prostor States ( struct Start : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reakce; ); struct Číslo : 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 >> reakce; ); struct Slovo: 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 >> reakce; ); struct Skip: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >reakce; ); )

Stroj je postaven, zbývá jej pouze inicializovat a můžete jej používat:

Strojní stroj; machine.initiate(); ...stroj.process_event(Události::Space());

Výsledek:

Flexibilita, rozšiřitelnost

- Účinnost

Výkon

Napsal jsem testovací program pro kontrolu výkonu postavených strojů. Prošel jsem přes stroje ~17 MB text. Zde jsou výsledky běhu:

Načítání textu Délka textu: 17605548 bajtů 0,19 s Běh BoostMachine Words: 998002, čísla: 6816 0,73 s Běh DynamicMachine Words: 998002, čísla: 6816 0,56 s Běh RychlýDynamic9,16 Machine Words:26 ine Words: 998002, čísla : 6816 0,20 s

Co zůstalo neprozkoumané

Stále existuje několik implementací konečných automatů (doporučuji http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml a http://www.rsdn.ru/article/alg/FiniteStateMachine.xml) , generátory, které sestavují stroje z popisů, knihovna Meta State Machine z Boost verze 1.44.0, stejně jako formální popisy konečných automatů. Se vším výše uvedeným se může zvídavý čtenář seznámit sám.

Teorie automatů je obor diskrétní matematiky, který studuje modely diskrétních převaděčů informací. Takovými převodníky jsou jak skutečná zařízení (počítače, živé organismy), tak imaginární zařízení (axiomatické teorie, matematické stroje). V podstatě lze konečný automat charakterizovat jako zařízení M , mající vstupní a výstupní kanály a v každém z jednotlivých časových okamžiků, nazývaných hodinové momenty, je v jednom z konečných stavů.

Prostřednictvím vstupního kanálu v každém okamžiku t =1, 2, ... do zařízení M vstupní signály přicházejí (z nějaké konečné množiny signálů). Zákon změny stavu v příštím čase je nastaven v závislosti na vstupním signálu a stavu zařízení v aktuálním čase. Výstupní signál závisí na stavu a vstupním signálu v aktuálním čase (obr. 1).

Konečný automat je matematický model skutečných diskrétních zařízení pro zpracování informací.

Státní stroj nazývaný systém A= (X , Q , Y ,  ,  ), kde X , Q , Y jsou libovolné neprázdné konečné množiny a  A  - funkce, z toho:

hromada X ={A 1 , ..., A m ) je nazýván vstupní abeceda a jeho prvky jsou vstupní signály , jejich sekvence jsou v v běžných slovech ;

hromada Q ={q 1 , ..., q n ) je nazýván mnoho států automat a jeho prvky - státy ;

hromada Y ={b 1 , ..., b p ) je nazýván výstupní abeceda , jeho prvky jsou výstupní signály , jejich sekvence jsou výstupní slova ;

funkce  : X  Q Q volal přechodová funkce ;

funkce  :X  Q Y volal výstupní funkce .

Tím pádem,  (X , q )Q ,  (X , q )Y pro  X X , q Q .

Konečný automat je spojen s imaginárním zařízením, které funguje následovně. Může to být v jednom z mnoha států Q , vnímat signály z různých X a vydávat signály z různých Y .

2. Metody specifikace konečného automatu

Existuje několik ekvivalentních způsobů, jak definovat abstraktní automaty, z nichž tři lze jmenovat: tabelární , geometrický A funkční .

2.1 Tabulková úloha stroje

Z definice automatu vyplývá, že jej lze vždy specifikovat tabulkou obsahující dva vstupy T linky a P kolony, kde na průsečíku kolony q a struny A jsou funkční hodnoty  (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. Určení automatu pomocí Moorova diagramu

Dalším způsobem, jak definovat konečný automat, je graficky, tedy pomocí grafu. Automat je znázorněn jako označený orientovaný graf G(Q , D ) s mnoha vrcholy Q a mnoho oblouků D ={(q j ,  (A i , q j ))| q j Q , A i X ), zatímco oblouk ( q j ,  (A i , q j )) je označena dvojicí ( A i ,  (A i , q j )). Při této metodě jsou tedy stavy stroje znázorněny kroužky, ve kterých jsou zapsány státní symboly q j (j = 1, …, n ). Z každého kruhu se provádí T šipky (orientované hrany) jedna ku jedné odpovídající znakům vstupní abecedy X ={A 1 , ..., A m ). Šipka odpovídající písmenu A i X a opuštění kruhu q j Q , je připisován páru ( A i ,  (A i , q j )) a tato šipka vede k příslušnému kruhu  (A i , q j ).

Výsledný výkres se nazývá automatový graf nebo, Moorův diagram . U nepříliš složitých strojů je tato metoda více vizuální než tabelární.