Formálne automaty (konečné)

Nedeterministické a deterministické konečné formálne automaty, ako ich čítať a vytvárať

Konečné automaty

Automat (z hľadiska formálnych jazykov) je orientovaný, ohodnotený multigraf ktorý sa používa pre modelovanie výpočtov na reťazcoch a popisuje možnosti, ako môžeme určitý reťazec spracovať.

Konečný automat je automat, ktorého množina stavov je konečná (to znamená, že máme presne dané prechody, ktoré môžeme realizovať pre spracovanie určitého reťazca). Avšak, to neznamená že konečné automaty nedokážu generovať nekonečný počet slov.

Konečné automaty dokážu rozpoznávať iba regulárne jazyky (teoreticky by sa dalo povedať že konečný automat je do istej miery vizuálnou reprezentáciou regulárnej gramatiky).

Takže, kým pri gramatikách sme generovali nové slová, pri automatoch je to akoby naopak: máme dané existujúce slovo a kontrolujeme, či toto slovo patrí do jazyka ktorý tento automat rozpoznáva. Jedná sa o algoritmus, ktorý dokáže automaticky kontrolovať správnosť reťazcov na vstupe. Môžeme riešiť otázky ako napríklad: je reťazec platné číslo? Je reťazec správne naformátované evidenčné číslo vozidla (ŠPZ)? A podobne...

Deterministické konečné automaty

Deterministický konečný automat - skrátene "DFA" (deterministic finite automaton) - je formálny automat, ktorý je jednoznačný. To znamená, že pre každý stav a vstupný symbol existuje presne práve jeden nasledovný stav (jeden prechod).

Deterministický konečný automat je definovaný ako pätica: $A = (Q, Σ, δ, q_{0}, F)$ , kde:

$A$ je označenie automatu;
$Q$ je konečná množina všetkých stavov (niečo ako neterminálne symboly - ale nie je to to isté!)
$Σ$ je konečná množina vstupných symbolov - abeceda, teda množina znakov z ktorých môžu byť zložené reťazce ktoré dokáže automat rozpoznať. Ak sa znak v množine nenachádza, slovo nepatrí do jazyka rozpoznávaného daným automatom;
δ je prechodová funkcia, ktorá určuje nasledovný stav.
- Táto funkcia je definovaná ako: $δ : Q \times Σ \to Q$ , čo znamená že pre každý stav a každý symbol abecedy určuje presne práve jeden nasledovný stav (pričom sa môže jednať aj o ten istý stav, napr.: cyklus / rekurzia);
$q_{0}$ je počiatočný stav (od ktorého začíname spracovávať daný reťazec). Platí, že $q_{0} \in Q$ (počiatočný stav musí byť z množiny všetkých stavov, čo dáva zmysel - ak máme napr. stavy $q_{0}$ , $q_{1}$ a $q_{2}$ , tak môžeme iba jeden z týchto troch zvoliť ako začiatočný, teda nemôžme si vymyslieť nejaký neexistujúci pretože by to nedávalo zmysel);
F je množina koncových (akceptačných) stavov (platí, že koncové stavy sú podmnožinou všetkých stavov: F⊆Q, teda môžeme mať viacero koncových stavov).
- Ak sa výpočet dostane do jedného z týchto koncových stavov, automat môže toto slovo akceptovať (alebo pokračovať ďalej, pokiaľ existujú ďalšie prechody). Ak je po skončení celého reťazca výpočet aktuálne v koncovom stave (z množiny $F$ ), slovo je akceptované - znamená to, že patrí do jazyka ktorý daný automat rozpoznáva.
- Pokiaľ spracovanie reťazca nikdy neskončí, alebo neskončí v koncovom stave, znamená to že slovo nepatrí do jazyka ktorý automat rozpoznáva.

Nedeterministické konečné automaty

Nedeterministický konečný automat - skratka "NFA" (non-deterministic finite automaton) - je podobný deterministickému konečnému automatu (DFA), ale umožňuje viaceré možnosti prechodu pre rovnaký vstup a stav alebo dokonca prechody bez spotreby symbolu (tzv. epsilon prechody $ϵ$ ). NFA je definovaný rovnako ako DFA, až na prechodovú funkciu, ktorá tu má tvar:

$δ : Q \times (Σ \cup {ϵ}) \to 2^{Q}$

To znamená, že prechodová funkcia $δ$ priradí ku každému stavu a symbolu (alebo epsilon prechodu) množinu stavov, do ktorých sa môže automat presunúť. Preto môže NFA existovať v niekoľkých stavoch súčasne. Ak aspoň jeden z týchto stavov je po skončení reťazca z množiny koncových stavov $F$ , automat slovo akceptuje.

Definícia automatu

Prechodové funkcie automatov môžu mať rôzne formy zápisov:

Ako orientovaný, ohodnotený multigraf;
Vymenovaním prechodov;
Ako tabuľka prechodov;

Napríklad, povedzme že máme definovaný nasledovný nedeterministický konečný automat, ktorý akceptuje práve slovo 10 a nič iné:

$\begin{aligned} A & = (Q, Σ, δ, q_{0}, F) \\ Q & = {q_{0}, q_{1}, q_{2}} \\ Σ & = {0, 1} \\ F & = {q_{2}} \end{aligned}$

Potom funkcia $δ$ by v podobe grafu vyzerala nasledovne:

{{#display_diagram:Drawio:Príklad nedeterministického konečného automatu}}

Tento zápis je najprehľadnejší zo všetkých, pretože vieme sa pomyselne pohybovať po jednotlivých vrcholoch a hranách. Ak dokážeme zo začiatočného stavu (šípka, ktorá ide zvonku do $q_{0}$ ) poskladať slovo, ktoré je na vstupe a skončíme v koncovom stave (ktorý je označený dvojitým kruhom), tak dané slovo patrí do jazyka ktorý rozpoznáva daný automat. Napr. v tomto prípade jednoznačne vidíme, že slovo "10" je v poriadku, pretože po "1" a "0" skončíme v dvojitom kruhu (koncovom / akceptačnom stave) a slovo patrí do jazyka a všetci sú spokojní.

Vymenovaním prechodov:

$\begin{aligned} δ (q_{0}; 1) = q_{1} \\ δ (q_{1}; 0) = q_{2} \end{aligned}$

Teda, ak sa nachádzame v stave $q_{0}$ a aktuálne spracovávaný znak bude "1", presunieme sa do stavu $q_{1}$ . Ak sme v $q_{1}$ a aktuálny znak je "0", presunieme sa do stavu $q_{2}$ . Zobrazujeme iba prechody, ktoré sa dostanú do nejakého stavu a vynechávame neexistujúce predchody.

V tabuľkovom zápise:

$δ$	0	1
$q_{0}$	$\emptyset$	$q_{1}$
$q_{1}$	$q_{2}$	$\emptyset$
$q_{2}$	$\emptyset$	$\emptyset$

Tabuľkový zápis je podobný ako vymenovanie prechodov, s tým rozdielom že zobrazujeme všetky možné prechody pre všetky symboly (aj tie prechody, ktoré neexistujú, napríklad nemôžme sa zo stavu $q_{0}$ dostať do iného stavu pomocou nuly, tento prechod teda nie je definovaný: $\emptyset$ ).

Najčastejšie sa používa zobrazenie prostredníctvom grafu. Ak prevádzame automat na gramatiku alebo na iný typ automatu, väčšinou robíme úpravy prostredníctvom tabuľky (kde ľahšie zbadáme, ktoré prechody musíme upraviť pre to, aby sme dostali požadovaný typ automatu, napríklad pri prevode nedeterministického automatu na deterministický musíme jasne definovať všetky nedefinované prechody do stavov $\emptyset$ ).

Že sa jedná o nedeterministický automat vieme podľa toho, že nie všetky stavy obsahujú prechody do iného stavu pre všetky symboly z abecedy (množiny $Σ$ ). Napríklad, ak sa nachádzame v stave $q_{0}$ a nasledujúci symbol je "0", tak nevieme do akého stavu sa má automat presunúť - prechod je nedefinovaný. Ale to nevadí, pretože keďže sa jedná o nedeterministický automat, stačí ak aspoň jeden výpočet zo všetkých možných výpočtov skončí v koncovom stave (nedeterministické automaty si predstavujeme, akoby išli všetkými možnými cestami prechodov naraz, a ak je aspoň jeden správny, tak aktuálne spracovávané slovo patrí do jazyka).

Postup výpočtu

Výpočet slova cez automat sa realizuje nasledovným spôsobom: dané slovo postupne spracovávame, pričom píšeme postup výpočtu, teda aký podreťazec automatu zostáva ešte spracovať. Ak automat spracuje celé slovo a nezostal mu už spracovať žiadny podreťazec (respektíve zostalo iba prázdne slovo $ϵ$ ), tak môžeme tvrdiť že pôvodný reťazec na vstupe patrí do jazyka ktorý daný automat rozpoznáva.

Napríklad, povedzme že pre automat definovaný vyššie máme na vstupe slovo $w = 10$ . Už na prvý pohľad toto slovo patrí do jazyka, ktorý automat rozpoznáva (pretože vieme, že sme povedali že automat rozpoznáva práve reťazec "10" a nič iné). Napriek tomu, postup výpočtu by vyzeral nasledovne:

$(q_{0}; 10) ⊢ (q_{1}; 1) ⊢ (q_{2}; ϵ)$

Ako môžeme vidieť, na vstupe sme mali slovo "10" a začíname v stave $q_{0}$ . Z pravej strany reťazca zoberieme nulu - teda, sa presunieme do stavu $q_{1}$ a na vstupe nám zostalo spracovať už iba jednotku. Ak zoberieme aj túto jednotku, na vstupe nám už nezostalo nič (čo reprezentuje prázdne slovo $ϵ$ ) a presúvame sa do stavu $q_{2}$ . Ak máme na aktuálnom vstupe $ϵ$ a aktuálny stav ( $q_{2}$ ) patrí do množiny koncových stavov (ktoré sú v pôvodnej definícií vyššie definované ako: $F = {q_{2}}$ ), tak slovo patrí do jazyka ktorý daný automat rozpoznáva. Čo je, samozrejme náš prípad, takže slovo "10" patrí do jazyku pre tento automat.

« Pokročilé úlohy pre tvorbu gramatík

Zásobníkové automaty »