it-swarm-eu.dev

Příklady konečných stavových strojů

Hledám dobré příklady strojů konečných stavů; jazyk není zvlášť důležitý, pouze dobré příklady.

Implementace kódu jsou užitečné (zobecněný pseudokód), ale je také velmi užitečné shromáždit různá použití FSM.

Příklady nemusí být nutně založeny na počítači, například velmi užitečný je příklad Mike Dunlavey's Railroad networks.

26
ocodo

Bezpečný (událost spuštěna)

  • Stavy : Více stavů „uzamčeno“, jeden stav „odemčeno“
  • Přechody : Správné kombinace/klávesy vás posunou z počátečních uzamčených stavů do uzamčených stavů blíže k odemknutým, dokud se konečně nedostanete k odemknutým. Nesprávné kombinace/klíče vás vrátí zpět do původního uzamčeného stavu (někdy označovaného jako nečinný ).

Semafor (aktivováno časem | senzor [událost] spuštěn)

  • Stavy : ČERVENÁ, ŽLUTÁ, ZELENÁ (nejjednodušší příklad)
  • Přechody : Po změně časovače ČERVENÁ na ZELENOU, ZELENOU na ŽLUTOU a ŽLUTOU na ČERVENOU. Mohlo by být také spuštěno na snímání automobilů v různých (složitějších) stavech.

Automat (spuštěná událost, varianta bezpečná)

  • Stavy : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS atd., VEND, CHANGE
  • Přechody : Změny stavu po vložení mincí, bankovek, přechodu na VEND při správném množství nákupu (nebo více), poté přechodu na ZMĚNU nebo IDLE (v závislosti na jak etický je váš automat)
28
aqua

Příklad protokolu Border Gateway Protocol

BGP je protokol, který podporuje základní rozhodnutí o směrování na internetu. Udržuje tabulku k určení dosažitelnosti hostitelů z daného uzlu a učinil internet skutečně decentralizovaným.

V síti je každý BGP uzel peer a používá konečný stavový stroj s jedním ze šesti stavů Idle , Connect, Active, OpenSent, OpenConfirm a Založeno. Každé vzájemné připojení v síti udržuje jeden z těchto stavů.

Protokol BGP určuje zprávy, které jsou zasílány kolegům za účelem změny jejich stavu.

BPG statechart.

BGP statechart

Líný

První stav nečinný . V tomto stavu BGP inicializuje zdroje a odmítá pokusy o příchozí připojení a zahájí připojení k partnerovi.

Připojit

Druhý stav Connect . V tomto stavu router čeká na dokončení připojení a přechází do stavu OpenSent , pokud je úspěšný. Pokud není úspěšný, resetuje časovač ConnectRetry a po uplynutí doby přechodu přejde do aktivního stavu.

Aktivní

Ve stavu aktivní router resetuje časovač ConnectRetry na nulu a vrátí se do stavu Connect .

OpenSent

Ve stavu OpenSent router odešle zprávu Open a na oplátku čeká. Výměnné zprávy jsou vyměňovány a po úspěšném přijetí je router umístěn do zavedeného stavu.

Založeno

Ve stavu Vytvořeno může router odesílat/přijímat: Keepalive; Aktualizace; a oznamovací zprávy do/ze svého vrstevníka.

Více informace o BGP jsou na wikipedii

14
ocodo

Jsou užitečné pro modelování všech druhů věcí. Například, volební cyklus může být modelován se státy podél linií (normální vláda) - výběr nazvaný -> (časná kampaň) - parlament rozpuštěn -> (těžký kampaň) - výběr -> (počítání hlasů) ). Pak buď (počítání hlasů) - žádná většina -> (koaliční jednání) - dosažená dohoda -> (normální vláda) nebo (počítání hlasů) - majorita -> (normální vláda). Provedl jsem variantu tohoto schématu ve hře s politickou podřízenou.

Používají se také v jiných aspektech her: AI je často založeno na státu; Přechody mezi nabídkami a úrovněmi a přechody po smrti nebo dokončení úrovně jsou FSM často dobře modelovány.

7
Peter Taylor

Analyzátor CSV používaný v jquery-csv plug-in

Je to základní Chomsky gramatika typu III syntaktický analyzátor.

Tokenizer regexu se používá k vyhodnocení dat na základě char-by-char. Když se vyskytne kontrolní znak, je kód předán příkazu switch pro další vyhodnocení na základě počátečního stavu. Nekontrolní znaky jsou hromadně seskupovány a kopírovány, aby se snížil počet potřebných operací kopírování řetězců.

Tokenizer:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

První sada shody jsou kontrolní znaky: oddělovač hodnot (") oddělovač hodnot (,) a oddělovač vstupů (všechny varianty nového řádku). Poslední shoda zpracovává nekontrolované seskupení znaků.

Existuje 10 pravidel, která musí analyzátor splňovat:

  • Pravidlo č. 1 - Jeden záznam na řádek, každý řádek končí novým řádkem
  • Pravidlo # 2 - Konec nového řádku na konci souboru vynechán
  • Pravidlo # 3 - První řádek obsahuje data záhlaví
  • Pravidlo # 4 - Mezery jsou považovány za data a položky by neměly obsahovat koncové čárky
  • Pravidlo # 5 - Řádky mohou nebo nemusí být ohraničeny dvojitými uvozovkami
  • Pravidlo # 6 - Pole obsahující zalomení řádků, dvojité uvozovky a čárky by měly být uzavřeny v dvojitých uvozovkách.
  • Pravidlo č. 7 - Pokud se k uzavírání polí používají dvojité uvozovky, musí být dvojité uvození, které se objeví uvnitř pole, předcházeno další dvojité uvozovce.
  • Pozměňovací návrh # 1 - Nekótované pole může nebo může
  • Pozměňovací návrh # 2 - Citované pole může, ale nemusí
  • Změna č. 3 - Poslední pole v položce může nebo nemusí obsahovat nulovou hodnotu

Poznámka: Prvních 7 pravidel je odvozeno přímo z IETF RFC 418 . Poslední 3 byly přidány, aby pokryly případy Edge zavedené moderními tabulkovými aplikacemi (ex Excel, Google Spreadsheet), které ve výchozím nastavení neomezují (tj. Neuvádějí) všechny hodnoty. Snažil jsem se přispět zpět ke změnám RFC, ale ještě jsem neslyšel odpověď na můj dotaz.

Dost s ukončením, tady je diagram:

CSV parser finite state machine

Stavy:

  1. počáteční stav pro položku a/nebo hodnotu
  2. objevila se úvodní nabídka
  3. došlo k druhé nabídce
  4. došlo k neuvedené hodnotě

Přechody:

  • a. kontroluje citované hodnoty (1), nekótované hodnoty (3), nulové hodnoty (0), nulové položky (0) a nové položky (0)
  • b. šeky na druhou nabídku char (2)
  • c. zkontroluje únikovou nabídku (1), konec hodnoty (0) a konec zadání (0)
  • d. kontroluje konec hodnoty (0) a konec zadání (0)

Poznámka: Ve skutečnosti chybí stav. Měla by existovat čára od 'c' -> 'b' označená stavem '1', protože uniklý druhý oddělovač znamená, že první oddělovač je stále otevřený. Ve skutečnosti by bylo pravděpodobně lepší ho reprezentovat jako další přechod. Jejich vytváření je umění, neexistuje jediný správný způsob.

Poznámka: Chybí také výstupní stav, ale na platných datech syntaktický analyzátor vždy končí přechodem 'a' a žádný ze stavů není možný, protože není co analyzovat.

Rozdíl mezi státy a přechody:

Stát je konečný, což znamená, že lze odvodit pouze jednu věc.

Přechod představuje tok mezi stavy, takže může znamenat mnoho věcí.

V zásadě je vztah mezi stavem a přechodem 1 -> * (tj. Jeden-k-mnoho). Stav definuje „co to je“ a přechod definuje „jak se s ním zachází“.

Poznámka: Nebojte se, pokud se aplikace stavů/přechodů necítí intuitivně, není intuitivní. Trvalo to nějaké rozsáhlé korespondence s někým mnohem chytřejší než já, než jsem konečně dostal koncept držet.

Pseudokód:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.Push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.Push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Poznámka: Toto je Gist, v praxi je toho ještě mnohem více. Například kontrola chyb, nulové hodnoty, koncový prázdný řádek (tj. Který je platný) atd.

V tomto případě je stav stavem, když regexový blok dokončí iteraci. Přechod je reprezentován jako příkazy případu.

Jako lidé máme tendenci zjednodušovat operace na nízké úrovni do abstraktů vyšších úrovní, ale práce s FSM je práce s operacemi na nízké úrovni. Zatímco se státy a přechody lze velmi snadno pracovat individuálně, je neodmyslitelně obtížné celý vizualizovat najednou. Zjistil jsem, že je nejjednodušší sledovat jednotlivé cesty provádění znovu a znovu, dokud jsem nemohl intuitivně zjistit, jak se přechody odehrávají. Je to král jako učení základní matematiky, nebudete schopni vyhodnotit kód z vyšší úrovně, dokud se podrobnosti o nízké úrovni nezačnou automatizovat.

Kromě: Pokud se podíváte na skutečnou implementaci, chybí mnoho podrobností. Za prvé, všechny nemožné cesty vyvolají konkrétní výjimky. Nemělo by být možné je zasáhnout, ale pokud se něco pokazí, budou absolutně vyvolávat výjimky ve zkušebním běžec. Za druhé, pravidla syntaktického analyzátoru toho, co je povoleno v „legálním“ datovém řetězci CSV, jsou dosti volná, takže kód potřebný k řešení mnoha konkrétních případů Edge. Bez ohledu na tuto skutečnost to byl proces používaný k zesměšňování FSM před všemi opravami chyb, rozšířeními a doladěním.

Stejně jako u většiny návrhů nejde o přesnou reprezentaci implementace, ale nastíní důležité části. V praxi existují ve skutečnosti 3 různé funkce syntaktického analyzátoru odvozené od tohoto návrhu: csv-specifický linkový rozdělovač, jednořádkový syntaktický analyzátor a úplný víceřádkový syntaktický analyzátor. Všichni pracují podobným způsobem, liší se způsobem, jakým zacházejí s znaky Newline.

4
Evan Plaice

Zjistil jsem, že přemýšlení o modelování výtahu (výtah) je dobrým příkladem stroje konečných stavů. To vyžaduje jen málo ve způsobu zavedení, ale poskytuje daleko od triviální situace k provedení.

Stavy jsou například v přízemí, v prvním patře atd. A pohybují se ze země do prvního patra, nebo se pohybují ze třetího do patra, ale v současné době mezi 3. a 2. poschodím atd.

Účinek tlačítek v kleci výtahu a na samotných podlahách poskytuje vstupy, jejichž účinek závisí na tlačítku, které je stisknuto spolu s aktuálním stavem.

Každé patro, kromě horního a spodního, bude mít dvě tlačítka: jedno pro vyžádání zvedání výtahu nahoru, druhé dolů.

3
jan

Simple FSM v Javě

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Tady máš. Dobře, není to brilantní, ale ukazuje to.

V telekomunikačních produktech často najdete FSM, protože nabízejí jednoduché řešení jinak složité situace.

3
Gary Rowe

Dobře, tady je příklad. Předpokládejme, že chcete analyzovat celé číslo. Bylo by to něco jako dd* kde d je celé číslo.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Samozřejmě, jak řekl @Gary, můžete tyto goto maskovat pomocí příkazu switch a stavové proměnné. Všimněte si, že lze strukturovat do tohoto kódu, který je izomorfní s původním regulárním výrazem:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Samozřejmě to můžete udělat také pomocí vyhledávacího stolu.

Konečné stavové stroje mohou být vyrobeny mnoha způsoby a mnoho věcí lze popsat jako příklady konečných stavových strojů. Nejde o „věc“ ani o koncept, o přemýšlení o věcech.

Příklad železniční sítě

Jedním příkladem FSM je železniční síť.

Existuje konečný počet přepínačů, ve kterých může vlak jet na jednu ze dvou kolejí.

K těmto spínačům je připojen konečný počet stop.

Kdykoli je vlak na jedné koleji, může být poslán na jinou kolej křížením přepínače na základě jediného kousku vstupních informací.

2
Mike Dunlavey

Konečný státní stroj v Ruby:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

To je chování jediného výpočetního uzlu v distribuovaném systému, kterým se nastavuje komunikační schéma založené na propojení. Víceméně. V grafické podobě to vypadá takto:

enter image description here

2
philosodad

Podívejte se na tento odkaz pro několik jednoduchých příkladů lexikální analýzy (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

Můžete si také prohlédnout příklady „dračí knihy“ (není to lehké čtení)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

1
jmq

V praxi se státní stroje často používají pro:

  • Účel návrhu (modelování různých akcí v programu)
  • Parsery přirozeného jazyka (gramatiky)
  • Analýza řetězců

Jedním příkladem by mohl být státní počítač, který prohledá řetězec, aby zjistil, zda má správnou syntaxi. Například nizozemské PSČ jsou formátovány jako „1234 AB“. První část může obsahovat pouze čísla, druhá pouze písmena. Lze napsat státní počítač, který sleduje, zda je ve stavu NUMBER nebo LETTER a pokud narazí na nesprávný vstup, odmítněte jej.

Tento akceptorový stavový stroj má dva stavy: číselný a alfa. Stavový stroj se spustí v číselném stavu a začne číst znaky řetězce ke kontrole. Pokud se během kteréhokoli ze stavů vyskytnou neplatné znaky, funkce se vrací s hodnotou FALSE a vstup odmítne jako neplatný.

Pythonův kód:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        Elif char not in string.digits:
            return False
    Elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Zdroj: (konečně) státní stroje v praxi

0
theD