Koncový stroj - Finite-state machine

Combinational logic Finite-state machine Pushdown automaton Turing machine Automata theoryAutomata theory.svg
O tomto obrázku
Třídy automatů
(Kliknutím na každou vrstvu získáte článek na toto téma)

Konečných státní stroj ( FSM ) nebo konečný-automat ( FSA , množné číslo: automaty ), konečný automat , nebo jednoduše stav stroje , je matematický model výpočtu . Je to abstraktní stroj, který může být v přesně daném čase přesně v jednom z konečného počtu stavů . FSM se může v závislosti na některých vstupech změnit z jednoho stavu do druhého ; změna z jednoho stavu do druhého se nazývá přechod . FSM je definován seznamem jeho stavů, jeho počátečního stavu a vstupů, které spouští každý přechod. Stroje s konečným stavem jsou dvou typů- deterministické stroje s konečným stavem a nedeterministické stroje s konečným stavem . Deterministický stroj s konečným stavem může být konstruován ekvivalentně k jakémukoli nedeterministickému.

Chování stavových strojů lze pozorovat na mnoha zařízeních v moderní společnosti, která provádějí předem stanovený sled akcí v závislosti na sledu událostí, se kterými jsou prezentovány. Jednoduchými příklady jsou prodejní automaty , které vydávají produkty, když je uložena správná kombinace mincí, výtahy , jejichž pořadí zastávek je určeno podlažími požadovanými jezdci, semafory , které mění pořadí, když čekají auta, a kombinační zámky , které vyžadují zadání sekvence čísel ve správném pořadí.

Stroj s konečným stavem má menší výpočetní výkon než některé jiné modely výpočtu, jako je Turingův stroj . Rozlišení na výpočetní výkon znamená, že existují výpočetní úlohy, které může Turingův stroj dělat, ale FSM ne. Důvodem je, že paměť FSM je omezena počtem stavů, které má. Stroj s konečným stavem má stejný výpočetní výkon jako Turingův stroj, který je omezen tak, že jeho hlava může provádět pouze operace „čtení“ a vždy se musí pohybovat zleva doprava. FSM jsou studovány v obecnější oblasti teorie automatů .

Příklad: turniket na mince

Stavový diagram turniketu
Turniket

Příkladem jednoduchého mechanismu, který lze modelovat pomocí stavového stroje, je turniket . Turniket, který se používá k řízení přístupu k metru a zábavním parkům, je brána se třemi rotujícími rameny ve výšce pasu, jedním přes vchod. Zpočátku jsou paže zamčené, blokují vstup a brání čtenářům v průchodu. Uložení mince nebo tokenu do štěrbiny na turniketu odemkne ruce, což umožní jednomu zákazníkovi prosadit se. Poté, co zákazník projde, jsou ramena opět uzamčena, dokud není vložena další mince.

Považován za stavový automat, turniket má dva možné stavy: Zamčeno a Odemčeno . Existují dva možné vstupy, které ovlivňují jeho stav: vložení mince do slotu ( mince ) a zatlačení paže ( zatlačení ). V uzamčeném stavu nemá stisknutí paže žádný účinek; bez ohledu na to, kolikrát je vstupní stisk zadán, zůstane v uzamčeném stavu. Vložením mince - tj. Automatickým vstupem do mince - se stav posune ze zamčeného na odemčený . V odemčeném stavu nemá vložení dalších mincí žádný účinek; to znamená, že přidáním dalších mincových vstupů se stav nezmění. Zákazník, který tlačí skrz paže a dává podněty , přesune stav zpět na Uzamčeno .

Turniketový stavový stroj může být reprezentován tabulkou stavových přechodů , zobrazující pro každý možný stav, přechody mezi nimi (na základě vstupů daných stroji) a výstupy vyplývající z každého vstupu:

Aktuální stav Vstup Další stát Výstup
Zamčeno mince Odemčený Odemkne turniket, aby se zákazník mohl prosadit.
tam Zamčeno Žádný
Odemčený mince Odemčený Žádný
tam Zamčeno Když se zákazník prosadí, turniket zamkne.

Turniketový stavový stroj může být také reprezentován směrovaným grafem nazývaným stavový diagram (výše) . Každý stav je reprezentován uzlem ( kružnicí ). Hrany ( šipky ) ukazují přechody z jednoho stavu do druhého. Každá šipka je označena vstupem, který spouští tento přechod. Vstup, který nezpůsobuje změnu stavu (například vstup mince v odemčeném stavu), je znázorněn kruhovou šipkou, která se vrací do původního stavu. Šipka do uzlu Uzamčeno od černé tečky označuje, že se jedná o počáteční stav.

Pojmy a terminologie

Stav je popis stavu systému, který je připraven provést přechod . Přechod je sada akcí, které se mají provést, když je splněna podmínka nebo je přijata událost. Například při poslechu rádia pomocí zvukového systému (systém je ve stavu „rádia“) má příjem „dalšího“ stimulu za následek přesun na další stanici. Když je systém ve stavu „CD“, podnět „další“ má za následek přesun na další stopu. Identické podněty spouští různé akce v závislosti na aktuálním stavu.

V některých reprezentacích strojů s konečným stavem je také možné přiřadit akce ke stavu:

  • vstupní akce: provádí se při vstupu do stavu a
  • akce ukončení: provádí se při opuštění stavu.

Zastoupení

Obr. 1 Příklad grafu stavu UML (toustovač)
Obr. 2 Příklad stavového stroje SDL
Obr. 3 Příklad jednoduchého stroje s konečným stavem

Tabulka stavu/události

Používá se několik typů tabulek přechodů stavu . Nejběžnější zobrazení je uvedeno níže: kombinace aktuálního stavu (např. B) a vstupu (např. Y) ukazuje další stav (např. C). Informace o úplné akci nejsou v tabulce přímo popsány a lze je přidat pouze pomocí poznámek pod čarou. Definice FSM včetně informací o úplné akci je možná pomocí stavových tabulek (viz také virtuální stroj konečného stavu ).

Tabulka přechodu stavu
  Aktuální
stav
Vstup
Stát A. Stát B. Stát C.
Vstup X ... ... ...
Vstup Y ... Stát C. ...
Vstup Z ... ... ...

Stavové stroje UML

Unified Modeling Language má notace pro popis stavových automatů. Státní stroje UML překonávají omezení tradičních strojů s konečným stavem při zachování jejich hlavních výhod. Státní stroje UML zavádějí nové koncepty hierarchicky vnořených stavů a ortogonálních oblastí a zároveň rozšiřují pojem akcí . Státní stroje UML mají vlastnosti strojů Mealy i Moore . Podporují akce, které závisí na stavu systému a spouštěcí události , jako u strojů Mealy, stejně jako akce vstupu a výstupu , které jsou spojeny spíše se stavy než s přechody, jako u strojů Moore.

Státní stroje SDL

Specifikace a Description Language je standardní od ITU , který obsahuje grafické symboly, které popisují činnosti v přechodném období:

  • poslat událost
  • přijmout událost
  • spustit časovač
  • zrušit časovač
  • spusťte další souběžný stavový stroj
  • rozhodnutí

SDL obsahuje základní datové typy zvané „abstraktní datové typy“, akční jazyk a sémantiku provádění, aby byl stroj s konečným stavem spustitelný.

Další stavové diagramy

Existuje velké množství variant reprezentujících FSM, jako je ta na obrázku 3.

Používání

Kromě jejich použití při modelování reaktivních systémů, které jsou zde uvedeny, jsou stroje s konečným stavem významné v mnoha různých oblastech, včetně elektrotechniky , lingvistiky , počítačové vědy , filozofie , biologie , matematiky , programování videoher a logiky . Stroje s konečným stavem jsou třídou automatů studovaných v teorii automatů a teorii výpočtu . V počítačové vědě jsou stroje s konečným stavem široce používány při modelování chování aplikací, návrhu hardwarových digitálních systémů , softwarovém inženýrství , překladačích , síťových protokolech a studiu výpočtů a jazyků.

Klasifikace

Stroje s konečným stavem lze rozdělit na akceptory, klasifikátory, převodníky a sekvencery.

Přijímače

Obr. 4: Akceptor FSM: analýza řetězce „pěkný“.
Obr. 5: Znázornění akceptoru; tento příklad ukazuje číslo, které určuje, zda má binární číslo sudý počet 0 s, kde S 1 je přijímající stav a S 2 je nepřijímající stav .

Akceptory (nazývané také detektory nebo rozpoznávače ) produkují binární výstup, který indikuje, zda je přijatý vstup přijat. Každý stav akceptora buď přijímá, nebo neakceptuje . Jakmile je přijat veškerý vstup, je -li aktuální stav stavem přijímajícím, vstup je přijat; jinak se zamítá. Vstupem je zpravidla sekvence symbolů (znaků); akce se nepoužívají. Počáteční stav může být také přijímající stav, v takovém případě akceptor přijímá prázdný řetězec. Příklad na obrázku 4 ukazuje akceptor, který přijímá řetězec „nice“. V tomto akceptoru je jediným přijímajícím stavem stav 7.

(Možná nekonečná) sada sekvencí symbolů, nazývaná formální jazyk , je pravidelný jazyk, pokud existuje nějaký akceptor, který přijímá přesně tuto sadu. Například sada binárních řetězců se sudým počtem nul je regulárním jazykem (viz obr. 5), zatímco množina všech řetězců, jejichž délka je prvočíslo, není.

Akceptor by také mohl být popsán jako definující jazyk, který by obsahoval každý řetězec přijatý akceptorem, ale žádný z odmítnutých; tento jazyk je přijímán přijímačem. Podle definice jsou jazyky přijímané akceptory běžnými jazyky .

Problém určení jazyka přijatého daným akceptorem je příkladem problému algebraické cesty - sám zobecněním problému s nejkratší cestou na grafy s hranami váženými prvky (libovolného) semiringu .

Příklad přijatelného stavu se objevuje na obr. 5: deterministický konečný automat (DFA), který detekuje, zda řetězec binárního vstupu obsahuje sudý počet 0 s.

S 1 (což je také počáteční stav) označuje stav, ve kterém byl zadán sudý počet 0 s. S 1 je tedy přijímající stav. Tento akceptor skončí ve stavu přijetí, pokud binární řetězec obsahuje sudý počet 0 s (včetně libovolného binárního řetězce bez 0). Příklady řetězců přijatých tímto akceptorem jsou ε ( prázdný řetězec ), 1, 11, 11 ..., 00, 010, 1010, 10110 atd.

Klasifikátory

Klasifikátory jsou zobecnění akceptorů, které produkují n -ary výstup, kde n je striktně větší než dva.

Převodníky

Obr. 6 Převodník FSM: příklad modelu Moore
Obr. 7 Převodník FSM: Mealyho modelový příklad

Převodníky produkují výstup na základě daného vstupu a/nebo stavu pomocí akcí. Používají se pro řídicí aplikace a v oblasti počítačové lingvistiky .

V řídicích aplikacích se rozlišují dva typy:

Mooreův stroj
FSM používá pouze vstupní akce, tj. Výstup závisí pouze na stavu. Výhodou modelu Moore je zjednodušení chování. Zvažte dveře výtahu. Stavový stroj rozpoznává dva příkazy: „command_open“ a „command_close“, které aktivují změny stavu. Vstupní akce (E :) ve stavu „Otevírání“ spustí motor otevírající dveře, vstupní akce ve stavu „Zavírání“ spustí motor v opačném směru a zavře dveře. Stavy „Otevřeno“ a „Zavřeno“ zastaví motor při úplném otevření nebo zavření. Signalizují vnějšímu světu (např. Jiným stavovým strojům) situaci: „dveře jsou otevřené“ nebo „dveře jsou zavřené“.
Mealy machine
FSM také používá vstupní akce, tj. Výstup závisí na vstupu a stavu. Použití Mealy FSM často vede ke snížení počtu států. Příklad na obrázku 7 ukazuje Mealy FSM implementující stejné chování jako v příkladu Moore (chování závisí na implementovaném modelu provedení FSM a bude fungovat např. Pro virtuální FSM, ale ne pro událostmi řízený FSM ). Existují dvě vstupní akce (I :): „spustit motor, aby se dveře zavřely, když dorazí command_close“ a „spustit motor v opačném směru, aby se dveře otevřely, pokud dorazí command_open“. Mezistavy „otevírání“ a „zavírání“ nejsou zobrazeny.

Sekvencery

Sekvencery (také nazývané generátory ) jsou podtřída akceptorů a převodníků, které mají jednopísmennou vstupní abecedu. Produkují pouze jednu sekvenci, kterou lze považovat za výstupní sekvenci výstupů akceptoru nebo převodníku.

Determinismus

Další rozdíl je mezi deterministickými ( DFA ) a nedeterministickými ( NFA , GNFA ) automaty. V deterministickém automatu má každý stav přesně jeden přechod pro každý možný vstup. V nedeterministickém automatu může vstup vést k jednomu, více než jednomu nebo k žádnému přechodu pro daný stav. POWERSET konstrukce algoritmus může převést jakýkoli nedeterministický automat na (obvykle více komplex) deterministického automatu se stejnou funkčností.

Stroj s konečným stavem pouze s jedním stavem se nazývá „kombinatorický FSM“. Umožňuje pouze akce při přechodu do stavu. Tento koncept je užitečný v případech, kdy je požadováno, aby spolupracovala řada strojů s konečným stavem, a když je vhodné považovat čistě kombinatorickou část za formu FSM, která vyhovuje návrhovým nástrojům.

Alternativní sémantika

Pro reprezentaci stavových strojů jsou k dispozici další sady sémantiky. Existují například nástroje pro modelování a navrhování logiky pro integrované řadiče. Kombinují hierarchické stavové stroje (které obvykle mají více než jeden aktuální stav), vývojové grafy a pravdivostní tabulky do jednoho jazyka, což má za následek odlišný formalismus a sadu sémantiky. Tyto grafy, stejně jako původní stavové stroje Harel, podporují hierarchicky vnořené stavy, ortogonální oblasti , akce stavu a akce přechodu.

Matematický model

V souladu s obecnou klasifikací jsou nalezeny následující formální definice.

Deterministický konečný automat nebo deterministický konečný stavu akceptor je pětinásobný , kde:

  • je vstupní abeceda (konečná neprázdná sada symbolů);
  • je konečná neprázdná množina stavů;
  • je počáteční stav, prvek ;
  • je funkce přechodu stavu: (v nedeterministickém konečném automatu by to bylo , tj. vrátilo by sadu stavů);
  • je množina konečných stavů, (možná prázdná) podmnožina .

Pro deterministické i nedeterministické FSM je obvyklé dovolit být dílčí funkcí , tj. Nemusí být definováno pro každou kombinaci a . Pokud je FSM ve stavu , další symbol je a není definován, pak může oznámit chybu (tj. Odmítnout vstup). To je užitečné v definicích strojů s obecným stavem, ale méně užitečné při transformaci stroje. Některé algoritmy ve své výchozí formě mohou vyžadovat celkové funkce.

Stroj s konečným stavem má stejný výpočetní výkon jako Turingův stroj, který je omezen tak, že jeho hlava může provádět pouze operace „čtení“ a vždy se musí pohybovat zleva doprava. To znamená, že každý formální jazyk přijatý automatem konečného stavu je akceptován takovým druhem omezeného Turingova stroje a naopak.

Převodník konečných stav je Šestilůžkový , kde:

  • je vstupní abeceda (konečná neprázdná sada symbolů);
  • je výstupní abeceda (konečná neprázdná sada symbolů);
  • je konečná neprázdná množina stavů;
  • je počáteční stav, prvek ;
  • je funkcí stavu přechodu: ;
  • je výstupní funkce.

Pokud výstupní funkce závisí na stavu a vstupním symbolu ( ), odpovídá tato definice modelu Mealy a lze jej modelovat jako Mealyho stroj . Pokud výstupní funkce závisí pouze na stavu ( ), odpovídá tato definice modelu Moore a lze jej modelovat jako stroj Moore . Stroj s konečným stavem, který nemá vůbec žádnou výstupní funkci, se nazývá poloautomat nebo přechodový systém .

Pokud pomineme první výstupní symbol stroje Moore , pak jej lze snadno převést na stroj Mealy ekvivalentní výstupu nastavením výstupní funkce každého přechodu Mealy (tj. Označení každé hrany) symbolem výstupu daným cílovým Moore Stát. Konverzní transformace je méně přímočará, protože stav stroje Mealy může mít na svých příchozích přechodech (hranách) různé výstupní popisky. Každý takový stav je třeba rozdělit do více stavů stroje Moore, jeden pro každý výstupní symbol incidentu.

Optimalizace

Optimalizace FSM znamená nalezení stroje s minimálním počtem stavů, který vykonává stejnou funkci. Nejrychlejším známým algoritmem, který to dělá, je minimalizační algoritmus Hopcroft . Mezi další techniky patří použití implikační tabulky nebo postup Mooreovy redukce. Navíc lze acyklické FSA minimalizovat v lineárním čase.

Implementace

Hardwarové aplikace

Obr. 9 Schéma zapojení pro 4bitový čítač TTL , typ stavového stroje

V digitálním obvodu může být FSM postaveno pomocí programovatelného logického zařízení , programovatelného logického řadiče , logických bran a klopných obvodů nebo relé . Přesněji řečeno, hardwarová implementace vyžaduje registr pro ukládání stavových proměnných, blok kombinační logiky, který určuje přechod stavu, a druhý blok kombinační logiky, který určuje výstup FSM. Jednou z klasických hardwarových implementací je řadič Richards .

V počítači Medvedev je výstup přímo připojen ke stavovým klopným obvodům, což minimalizuje časové zpoždění mezi klopnými obvody a výstupem.

Prostřednictvím kódování stavu pro stroje s nízkou spotřebou energie lze optimalizovat, aby se minimalizovala spotřeba energie.

Softwarové aplikace

K vytváření softwarových aplikací pomocí strojů s konečným stavem se běžně používají následující koncepty:

Stroje a překladače konečných stavů

Konečné automaty se často používají v frontendu kompilátorů programovacího jazyka. Takový frontend může zahrnovat několik strojů s konečným stavem, které implementují lexikální analyzátor a analyzátor. Počínaje posloupností znaků lexikální analyzátor vytvoří posloupnost tokenů jazyků (jako jsou vyhrazená slova, literály a identifikátory), ze kterých analyzátor vytvoří strom syntaxe. Lexikální analyzátor a analyzátor zpracovávají pravidelné a bezkontextové části gramatiky programovacího jazyka.

Viz také

Reference

Další čtení

Všeobecné

Koncové stroje (teorie automatů) v teoretické informatice

Abstraktní stavové stroje v teoretické informatice

Strojové učení pomocí algoritmů konečného stavu

  • Mitchell, Tom M. (1997). Strojové učení (1. vyd.). New York: WCB/McGraw-Hill Corporation. ISBN 978-0-07-042807-2.

Hardwarové inženýrství: minimalizace stavu a syntéza sekvenčních obvodů

  • Booth, Taylor L. (1967). Sekvenční stroje a teorie automatů (1. vyd.). New York: John Wiley and Sons, Inc. Library of Congress Card Katalogové číslo 67-25924.
  • Booth, Taylor L. (1971). Digitální sítě a počítačové systémy (1. vyd.). New York: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
  • McCluskey, EJ (1965). Úvod do teorie spínacích obvodů (1. vyd.). New York: McGraw-Hill Book Company, Inc. Katalogové číslo knihovny kongresové knihovny 65-17394.
  • Hill, Fredrick J .; Peterson, Gerald R. (1965). Úvod do teorie spínacích obvodů (1. vyd.). New York: McGraw-Hill Book Company. Katalogové číslo karty Kongresu knihovny 65-17394.

Konečné Markovovy řetězové procesy

Markovův řetězec můžeme považovat za proces, který se postupně pohybuje sadou stavů s 1 , s 2 ,…, s r .… Pokud je ve stavu s i , přechází na další zastávku do stavu s j s pravděpodobnost p ij . Tyto pravděpodobnosti mohou být vystaveny ve formě přechodové matice “(Kemeny (1959), s. 384)

Konečné procesy Markovova řetězce jsou také známé jako dílčí posuny konečného typu .

  • Booth, Taylor L. (1967). Sekvenční stroje a teorie automatů (1. vyd.). New York: John Wiley and Sons, Inc. Library of Congress Card Katalogové číslo 67-25924.
  • Kemeny, John G .; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Konečné matematické struktury (1. vyd.). Englewood Cliffs, New Jersey: Prentice-Hall, Inc. Katalog kongresové karty Library of Congress Card 59-12841. Kapitola 6 „Konečné Markovovy řetězy“.

externí odkazy