Konečnostavové akceptory. NKA, DKA a vzťah medzi nimi.

Krok 1

Na predchádzajúcom cvičení sme si predstavili akceptačný spôsob špecifikácie jazyka, ktorý predstavuje ďalšiu z pokročilých metód definície jazyka na báze automatov. Konkrétne sme sa zaoberali špecifikáciou regulárneho jazyka využitím DKA. Zopakujme si teda definíciu DKA na nasledujúcom príklade.

Príklad

Nech $M$ je DKA s nasledujúcim diagramom. Formálne definujtete $M$.

Ako je možné vidieť DKA z predádzajúceho príkladu predstavuje pomerne zložitý automat. Je teda adekvátne hovoriť o jeho minimalizácii (redukcii), proces ktorej sa skladá z dvoch podprocesov, a to:

1. identifikácie a eliminácie tzv. nedosiahnuteľných stavov a
2. určenia tried ekvivalencie vzájomne nerozlíšiteľných stavov.

Realizáciu jednotlichých podprocesov si demonštrujeme na vyššie uvedenom príklade, ešte predým však pristúpime k definícii ich základných pojmov a uvedeniu ich algoritmov.

Nech $M=(Q,T,\delta,q_0,F)$ je konečný automat. Stav $q\in Q$ nazývame dosiahnuteľný, ak existuje také slovo $w \in T^*$, že $(q_0,w)\vdash^*(q,\varepsilon)$. Ak stav nie je dosiahnuteľný označujeme ho ako nedosiahnuteľný.

Množinu všetkých dosiahnueľných stavov konečného automatu určime pomocou nasledujúceho algoritmu.

Algoritmus 1. konštrukcie množiny dosiahnueľných stavov konečného automatu.
Vstup: Konečný automat $M=(Q,T,\delta,q_0,F)$
Výstup: Množina dosiahnueľných stavov $S$ konečného automatu $M$

1. $S\leftarrow\{q_0\}$;
2. opakuj
3.   $\acute{S}\leftarrow S$;
4.   pre všetky $q\in \acute{S}$ vykonaj
5.    pre všetky $a\in T$ vykonaj
6.     $S\leftarrow S\cup\{\delta(q,a)\}$;
7.    koniec pre
8.   koniec pre
9. pokiaľ $S\neq\acute{S}$

Nech $M=(Q,T,\delta,q_0,F)$ je DKA a $q_1, q_2\in Q$ sú jeho dva rôzne stavy. Potom hovoríme, že:

• reťazec $w\in T^*$ rozlišuje stavy $q_1$ a $q_2$ vtedy, ak $(q_1,w)\vdash^*(q_3,\varepsilon), (q_2,w)\vdash^*(q_4,\varepsilon)$, pričom jeden zo stavov $q_3, q_4$ patrí do $F$ a druhý nie,
• stavy $q_1$ a $q_2$ sú $k$-nerozlíšiteľné ($q_1 \equiv^k q_2$), ak neexistuje reťazec $w$ s dĺžkou $|w|\leq k$, ktorý $q_1$ a $q_2$ rozlišuje,
• stavy $q_1$ a $q_2$ sú nerozlíšiteľné ($q_1 \equiv q_2$), ak pre ľubovoľné $l\geq 0$ sú $k$-nerozlíšiteľné.

Nerozlíšiteľné stavy tvoria nový tzv. zložený stav, ktorý budeme zapisovať ako množinu elementárnych stavov. Následne možno celú množinu stavov DKA rodeliť do vzájomne disjunktných tried ekvivalencie teda zložených stavov redukovaného DKA pomocou nasledujúcho algoritmu.

Algoritmus 2. konštrukcie tried ekvivalencie vzájomne nerozlíšiteľných stavov.
Vstup: DKA $M=(Q,T,\delta,q_0,F)$ bez nedosiahnuteľných stavov
Výstup: Množina tried ekvivalencie $R$ vzájomne nerozlíšiteľných stavov DKA $M$

1. $R\leftarrow\{F, Q-F\}$;
2. pre všetky $S\in R$ vykonaj
3.   pre všetky $a\in T$ vykonaj
4.    ak všetky elementárne stavy $\delta(q,a)$ pre $q\in S$ nepatria do rovnakého zloženého stavu potom
5.     rozdeľ zložený stav $S$ tak, aby po jeho rozdelení pre každé dva stavy $q_i,q_j$, ktoré pôvodne     patrili do $S$, platilo: $q_i,q_j$ patria do toho istého zloženého stavu práve vtedy, keď $\delta(q_i,a)$ a     $\delta(q_j,a)$ patria do rovnakého zloženého stavu;
6.     choď na riadok 2;
7.    koniec ak
8.   koniec pre
9. koniec pre

Výsledný redukovaný DKA $\acute{M}=(\acute{Q},T,\acute{\delta},\acute{q}_0,\acute{F})$ skonštruujeme nasledovne:

• $\acute{Q}$ bude množina všetkých zložených stavov (tied ekvivalencie) získanej Algoritmom 1.
• Nech $[q_i]$ resp. $[q_j]$ označujú tiedy ekvivalenie (zložené stavy) do ktorých patria elementárne stavy $q_i$ resp. $q_j$ pôvodného automatu, potom pre prechodovú funkciu redukovaného automatu platí $\acute{\delta}([q_i],a)=[q_j]$, ak $\delta(q_i,a)=q_j$.
• Začiatočný stav redukovaného automatu predstavuje zložený stav obsahujúci elementárny začiatočný stav pôvodného automatu, $\acute{q}_0=[q_0]$.
• Množina koncových stavov redukovaného automatu pozostáva zo zložených stavov obsahujúcich aspoň jeden elementárny koncový stav pôvodného automatu, $\acute{F}=\{[q_f]\;|\;q_f\in F\}$.

Riešenie

Najprv teda musíme pristúpiť k identifikácii a následnej eliminácii jeho nedosiahnuteľných stavov. Tie zistíme ako rozdiel množiny všetkých stavov $Q$ a množiny dosiahnuteľných stavov $S$, ktorú získame ako výsledok aplikácie Algoritmu 1.
Po inicializácii množiny $S$ počiatočným stavom $q_0$, sú hodnoty $S$ a $\acute{S}$ v jednotlivých iteráciách za ňou nasledujúceho logického cyklu v momente vyhonotenia jeho podmienky prehľadne prezentované v nasledujúcej tabuľke.

Iterácia logického cyklu	Množina $S$	Množina $\acute{S}$	Podmienka cyklu $S\neq\acute{S}$
1.	$\{q_0,q_1,q_2\}$	$\{q_0\}$	$\mathit{true}$
2.	$\{q_0,q_1,q_2,q_3,q_4\}$	$\{q_0,q_1,q_2\}$	$\mathit{true}$
3.	$\{q_0,q_1,q_2,q_3,q_4,q_7\}$	$\{q_0,q_1,q_2,q_3,q_4\}$	$\mathit{true}$
4.	$\{q_0,q_1,q_2,q_3,q_4,q_7\}$	$\{q_0,q_1,q_2,q_3,q_4,q_7\}$	$\mathit{false}$

Výsledná množina dosiahnuteľných stavov $S=\{q_0,q_1,q_2,q_3,q_4,q_7\}$. Stavy $q_5$ a $q_6$ sú teda nedosiahnueteľné a preto ich možno spolu s im prisluchajúcimi hranami vylúčiť z daného DKA, čo možno vidieť aj na nasledujúcom digrame.

Teraz možno využitím Algoritmu 2. pristúpiť k určeniu tried ekvivalencie $R$ vzájomne nerozlíšiteľných stavov tohto DKA.
Po inicializácii množiny $R$ zloženým stavom obsahujúcim všetky finálne stavy teda stavom $\{q_7\}$ a zloženým stavom, ktorý vznikol ako rozdiel množiny všetkých stavov $Q$ a množiny finálnych stavov $F$ teda stavom $\{q_0,q_1,q_2,q_3,q_4\}$, sú hodnoty $R$ v jednotlivých iteráciách za ňou nasledujúcich cyklov prehľadne prezentované v nasledujúcej tabuľke.

Iterácia vonkajšieho cyklu	Zložený stav $S$	Iterácia vnútorneho cyklu	Symbol $a$	Množina $R$
1.	$\{q_7\}$	1.	$0$	$\{\{q_7\},\{q_0,q_1,q_2,q_3,q_4\}\}$
1.	$\{q_7\}$	2.	$1$	$\{\{q_7\},\{q_0,q_1,q_2,q_3,q_4\}\}$
2.	$\{q_0,q_1,q_2 \textcolor{red}{\mid} q_3,q_4\}$	1.	$0$	$\{\{q_7\},\{q_0,q_1,q_2\},\{q_3,q_4\}\}$
3.	$\{q_7\}$	1.	$0$	$\{\{q_7\},\{q_0,q_1,q_2\},\{q_3,q_4\}\}$
3.	$\{q_7\}$	2.	$1$	$\{\{q_7\},\{q_0,q_1,q_2\},\{q_3,q_4\}\}$
4.	$\{q_0,q_1,q_2\}$	1.	$0$	$\{\{q_7\},\{q_0,q_1,q_2\},\{q_3,q_4\}\}$
4.	$\{q_0 \textcolor{red}{\mid} q_1,q_2\}$	2.	$1$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
5.	$\{q_7\}$	1.	$0$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
5.	$\{q_7\}$	2.	$1$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
6.	$\{q_0\}$	1.	$0$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
6.	$\{q_0\}$	2.	$1$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
7.	$\{q_1,q_2\}$	1.	$0$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
7.	$\{q_1,q_2\}$	2.	$1$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
8.	$\{q_3,q_4\}$	1.	$0$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$
8.	$\{q_3,q_4\}$	2.	$1$	$\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$

Vo výsledku teda došlo k dvom rozdeleniam, čím sme získali nasledujúce triedy ekvivalencie $\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}$.

Pre výsledný redukovaný automat $\acute{M}=(\acute{Q},T,\acute{\delta},\acute{q}_0,\acute{F})$, teda platí:

• $\acute{Q}=\{\{q_7\},\{q_0\},\{q_1,q_2\},\{q_3,q_4\}\}$,
• prechodová funkcia $\acute{\delta}$ je definovaná nasledujúcou prechodovou tabuľkou:
  

stav	$0$	$1$
$[q_0]$	$[q_1]$	$[q_1]$
$[q_1]$	$[q_1]$	$[q_3]$
$[q_3]$	$[q_7]$	$[q_3]$
$[q_7]$	$[q_7]$	$[q_0]$

• $\acute{q}_0=\{q_0\}$,
• $\acute{F}= \{\{q_7\}\}$.

Krok 2

Nedeterministický konečnostavový automat (NKA) je usporiadaná pätica $$ M = (Q, T, \delta, q_0, F), $$ kde:

• $ Q $ je konečná množina stavov automatu.
• $ T $ je vstupná abeceda automatu.
• $ \delta $ je prechodová funkcia automatu, $ \delta: Q \times T_\varepsilon \to 2^Q $.
• $ q_0 $ je počiatočný alebo iniciálny stav automatu, $ q_0 \in Q $.
• $ F $ je množina akceptujúcich (alebo koncových) stavov automatu, $F \subseteq Q $.
  

Všimnime si, že jediný rozdiel v definícii NKA v porovnaní definíciou DKA je špecifikácia prechodovej funkcie $\delta$, na ktorú sa preto pozrieme bližšie.

• Voľba množiny $Q\times T_\varepsilon$ (kde $T_\varepsilon=T\cup\{\varepsilon\} $) za doménu funkcie $\delta$ umožňuje NKA vykonávať kroky aj na základe prázdneho slova $\varepsilon$, teda meniť svoj stav aj bez čítania vstupného symbolu, čo znamená, že výpočet môže prebiehať bez posunu čítacej hlavy.
• Pre daný stav a vstupný symbol nemusí byť prechod jednoznačne určený: na daný vstupný symbol môže automat prejsť do viacerých rôznych stavov, čím umožňuje paralelné vetvenie výpočtu. Prechodová funkcia NKA preto pre daný stav a vstupný symbol poskytne len množinu stavov do ktorých môže NKA prejsť. Táto skutočnosť je vyjadrená voľbou potenčnej množiny množiny $A$ za kodoménu (obor hodnôt) funkcie $\delta.$

Na základe vyššie uvedenej definície je teda zrejmé, že DKA je len špeciálnym prípadom NKA, a to konkrétne s nasledujúcimi obmedzeniami:

• DKA neumožňuje vykonávať prechody na $\varepsilon$.
• DKA sa v prípade návratovej hodnoty prechodovej funkcie $\delta$ obmedzuje len na jednoprvkové a prázdne podmnožiny množiny $Q$.

Musí preto platiť, že jazyky akceptované DKA sú podmnožinou jazykov akceptovaných NKA. Prekvapujúco však platí aj opačné tvrdenie, a to, že jazyky akceptované NKA sú podmnožinou jazykov akceptovaných DKA. Inými slovami DKA a NKA sú expresívne ekvivalentné modely.

Pojmy konfigurácia, začiatočná a koncová (akceptujúca) konfigurácia konečného automatu sú spoločné pre oba druhy konečných automatov (pozri definície z druhého kroku predchádzajúceho cvičenia).

Na množine konfigurácií $Q \times T^* $ definujeme binárnu reláciu prechodu (alebo krok výpočtu) NKA $\vdash\;\subseteq (Q \times T^*)^2$ následovne: Nech $q, p \in Q, w \in T^*, x \in T$. Potom $$ (q, xw) \vdash (p, w) \quad \textrm{vtedy a len vtedy, ak} \quad p \in \delta(q, x). $$

Zatiaľ čo výpočet nad DKA predstavoval lineárnu postupnosť konfigurácii začínajúcu v začiatočnej konfigurácii, výpočet NKA predstavuje orientovaný strom konfigurácii, ktorého koreň tvorí začiatočná konfigurácia a ktorý sa bude vetviť vždy, keď automat môže prejsť do viacerých stavov.

Slovo $w$ je akceptované NKA $M$, ak vo výpočte (výpočtovom orientovanom strome) existuje aspoň jedna výpočtová orientovaná cesta, ktorá končí v koncovej akceptujúcej konfigurácia.

Na záver si uvedieme prehľadné porovnanie DKA a NKA v rámci nasledujúcej tabuľky.

Krok 3

V tomto kroku si priblížime jednoduchý postup konštrukcie NKA na základe zadaného regulárneho výrazu, ktorého princíp ,inšpirovaný Thompsonovou konštrukciou NKA, je zobrazený na nasledujúcom obrázku.

Riešenie

0|1{0|1}
Začíname konštrukciou NKA elementárnych regulárnych výrazov, z ktorých sa daný regulárny výraz skladá. Následne aplikujeme kompozičné pravidla z Obr. 1. za účelom konštrukcie NKA zodpovedajúcim jednotlivým zloženým tvarom regulárnych výrazov až pokiaľ nezískane výsledný NKA.

Na záver, priradíme označenia jednotlivých stavov tohto NKA.

Riešenie

Slová $\varepsilon$ a $01$ nepatria do jazyka binárnych numerálov, zatiaľ čo slovo $101$ patrí do tohto jazyka.

Precvičte si vytváranie nedeterministického konečnostavového akceptora na základe zadaného regulárneho výrazu s využitím metódy popísanej v tomto kroku na nasledujúcich príkladoch:

Krok 4

V predchádzajúcom kroku tohto cvičenia sme si predstavili jednoduchý spôsob, ako možno z regulárneho výrazu vytvoriť NKA akceptujúci rovnaký jazyk ako je jazyk identifikovaný týmto regulárnym výrazom. V tomto kroku sa oboznámime s dvoma základnými prístupmi k jeho praktickej (sekvenčnej) implementácii, v rámci ktorých nadviažeme na implementácie DKA z predchádzajúceho cvičenia.

Najprv sa teda oboznámime so všeobecným princípom neiteratívnej implementácie NKA.

Vstupom implementácie je reťazec a výstupom je informácia, či reťazec patrí alebo nepatrí do jazyka, teda pravdivostná hodnota. Každý stav $q_i \in Q$ bude v rámci tejto implementácie zodpovedať funkcii

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$q_i:String -> Bool,

t. j. funkcii, ktorá na vstupe prijíma reťazec a na výstupe produkuje pravdivostnú hodnotu, pri implementácii ktorej sa riadime nasledujúcimi pravidlami:

• Funkcia q_i vráti pravdivostnú hodnotu True, ak q_i zodpovedá koncovému stavu DKA a jej argumentom je prázdny reťazec $\varepsilon$.
• Funkcia q_i na základe prvého symbolu $x$ jej odovzdaného slova $xw_r$ vráti disjunkciu všetkých volaní funkcií q_j($w_r$), pričom $q_j\in\delta(q_i,x)$ a q_k($xw_r$), kde $q_k\in\delta(q_i,\varepsilon)$ a defaultne vráti disjunkciu všetkých volaní funkcií q_k($xw_r$), kde $q_k\in\delta(q_i,\varepsilon)$.
• Vo všetkých ostatných prípadoch vráti funkcia q_i pravdivostnú hodnotu False.

Volaním funkcie q_0 zodpovedajúcej počiatočnému stavu implementovaného NKA s argumentom predstavujúcim kontrolované slovo spustíme samotný výpočet NKA. Keďže tento prístup využíva pre spracovanie symbolov vstupného reťazca postupné volanie funkcií zodpovedajúcich jednotlivým stavom implementovaného NKA ide o neiteratívny prístup k jeho implementácii. Výhodou tohto riešenia, je že ide o implicitnú implementáciu algoritmu spätného prehľadávania (z angl. backtracking), ktorá predstavuje základnú metódu sekvenčnej implementácie výpočtu NKA.

/*implementácia funkcie zodpovedajúcej koncovému stavu qi*/
bool q_i(char* word){
    if (strlen(word)==0){
        return true;
    }else{
        switch (word[0]){
            case 'j':
                return q_j1(&word[1]) || /*...*/ 
                q_jn(&word[1]) || q_k1(word) || /*...*/ q_km(word);
            /*...*/
            
            default:
                return q_k1(word) || /*...*/ q_km(word) || false;
        }
    }
}

/*implementácia funkcie zodpovedajúcej stavu qi*/
bool q_i(char* word){
    if (strlen(word)>0){
        switch (word[0]){
            case 'j':
                return q_j1(&word[1]) || /*...*/ 
                q_jn(&word[1]) || q_k1(word) || /*...*/ q_km(word);
            /*...*/
            
            default:
                return q_k1(word) || /*...*/ q_km(word) || false;
        }
    }
    return q_k1(word) || /*...*/ q_km(word) || false;
}

Okrem vyššie uvedeného prístupu sa možno vybrať taktiež cestou iteratívneho prístup k implementácii NKA, kedy aktuálny stav automatu predstavuje internu premennú, ktorá sa pri postupnom čítaní jednotlivých symbolov vstupného slova (teda pri iterácii týmto slovom) mení na základe prechodovej funkcie $\delta$. Na rozdiel od DKA je však potrebé pokryť všetky výpočtové orientované ciesty v orientovanom strome reprezentujúcom výpočet NKA, sekvenčné riešenie čoho si vyžaduje napríklad explicitnú implementáciu algoritmu spätného prehľadávania. Slovo je akceptované ak existuje aspoň jedna výpočtová orientovaná cesta, ktorá končí koncovou, akceptujúcou konfiguráciou, v opačnom prípade slovo nebude akceptované.