Konečný stavový automat & RegEx
Interaktívny simulátor deterministických konečných automatov (DFA) a regulárnych jazykov.
Sledujte prechodový diagram stav po stave, krokovanie vstupnej pásky v reálnom čase,
rozhodnutie o akceptovaní či zamietnutí reťazca a formálnu 5-ticu (Q, Σ, δ, q0, F).
1. Prechodový stavový diagram (Graph View)
Stavy sú kruhy, koncové akceptujúce stavy majú dvojitý kruh. Šípka → označuje počiatočný stav. Aktívny stav je zeleno rozsvietený.
2. Simulácia & Krokovanie pásky reťazca
Zadajte testovací reťazec a krokujte spracovanie znak po znaku alebo spustite plynulú animáciu.
Reťazec je načítaný na vstupnej páske. Kliknite na 'Krok vpred' alebo 'Prehrať'.
3. Prechodová tabuľka funkcie δ (Delta)
δ: Q × Σ → QRiadky predstavujú aktuálny stav, stĺpce prichádzajúci vstupný symbol. Riadok aktívneho stavu je zvýraznený.
Formálna definícia (5-tica)
A = (Q, Σ, δ, q0, F)
(0|1(01*0)*1)*
Prečo sú konečné automaty a regulárne výrazy také kľúčové?
Lexikálna analýza prekladačov (Lexery)
Každý kompilátor (C, Java, PHP, Python) začína lexikálnym analyzátorom. Tokeny ako kľúčové slová, premenné, čísla či reťazce sú rozpoznávané deterministickými konečnými automatmi odvodenými z regulárnych výrazov.
Číslicové sekvenčné obvody (FSM)
V hardware (FPGA, mikroprocesory) sa stavové automaty realizujú pomocou klopných obvodov a kombinačnej logiky. Riadiče pamätí, zbernice SPI/I2C aj sieťové karty bežia ako hardvérové stavové automaty.
Chomského hierarchia (Typ 3)
Regulárne jazyky predstavujú najzákladnejšiu triedu Chomského hierarchie. Na rozdiel od bezkontextových jazykov (so zásobníkom) konečný automat nemá neobmedzenú pamäť – pamätá si iba to, v akom stave sa práve nachádza.