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

Krok 1

Na predchádzajúcom cvičení sme 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 definíciu DKA na nasledujúcom príklade.

Príklad

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

Ako je možné vidieť, DKA z predádzajúceho príkladu predstavuje pomerne zložitý automat. Preto je vhodné hovoriť o jeho minimalizácii (redukcii), ktorej proces 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 jednotlivých podprocesov demonštrujeme na vyššie uvedenom príklade. 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číme pomocou nasledujúceho algoritmu.

Algoritmus 1. Konštrukcia 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 dosiahnuteľ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}$

Slovný opis algoritmu:

Algoritmus 1. Konštrukcia 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 dosiahnuteľných stavov $S$ konečného automatu $M$.

1. Inicializuj $S$ množinou obsahujúcou počiatočný stav $q_0$.
2. opakuj
3.   Skopríruj obsah $S$ do $\acute{S}$.
4.   pre všetky stavy $q$ z množiny $\acute{S}$ vykonaj
5.    pre všetky symboly $a$ zo vstupnej abecedy $T$ vykonaj
6.     Do $S$ pridaj stav, do ktorého sa možno dostať zo stavu $q$ po prečítaní symbolu $a$.
7.    koniec pre
8.   koniec pre
9. pokiaľ je obsah $S$ rôzny od obsahu $\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 rozdeliť do vzájomne disjunktných tried ekvivalencie, teda zložených stavov redukovaného DKA pomocou nasledujúcho algoritmu.

Algoritmus 2. Konštrukcia 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 krok 2;
7.    koniec ak
8.   koniec pre
9. koniec pre

Slovný opis algoritmu:

Algoritmus 2. Konštrukcia 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. Inicializuj $R$ množinou obsahujúcou množinu koncových stavov $F$ a množinu ostatných stavov, ktorú získame ako rozdiel množiny všetkých stavov $Q$ a množiny koncových stavov $F$.
2. pre všetky zložené stavy $S$ z množiny $R$ vykonaj
3.   pre všetky symboly $a$ zo vstupnej abecedy $T$ vykonaj
4.    ak všetky elementárne stavy, do ktorých sa možno dostať zo všetkých elementárnych stavov $q$     zloženého stavu $S$ po prečítaní symbolu $a$ 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ď aj stavy do     ktorých sa možno dostať z týchto stavov po prečítaní toho istého symbolu $a$ patria do
       rovnakého zloženého stavu.
6.     choď na krok 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 (tried ekvivalencie) získanej Algoritmom 2.
• Nech $[q_i]$ resp. $[q_j]$ označujú triedy 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 vyhodnotenia 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 nedosiahnuteľné, a preto ich spolu s im prisluchajúcimi hranami môžeme 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 tak 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})$ 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\} $ tzv. rozšírená abeceda) 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 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 koreňový 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ácii.

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

Krok 3

V tomto kroku 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\}$
Konštrukciou NKA začíname od 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ískame výsledný NKA.

Na záver priradíme označenia jednotlivých stavov, čím získame úplný 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 predstavili jednoduchý spôsob, ako možno z regulárneho výrazu vytvoriť NKA akceptujúci rovnaký jazyk, ako je jazyk vyjadrený 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 rekurzívnej resp. 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 $$\texttt{qi:String -> Bool},$$ ktorá na vstupe prijíma reťazec a na výstupe posktuje pravdivostnú hodnotu. Pri implementácii tejto funkcie sa riadime nasledujúcimi pravidlami:

• Funkcia $\texttt{qi}$ vráti pravdivostnú hodnotu $\texttt{True}$, ak $\texttt{qi}$ zodpovedá koncovému stavu DKA a jej argumentom je prázdny reťazec $\varepsilon$.
• Funkcia $\texttt{qi}$ na základe prvého symbolu $x$ jej odovzdaného slova $w$ vráti elementárnu disjunkciu všetkých volaní funkcií $\texttt{qj(}w_r\texttt{)}$ a $\texttt{qk(}xw_r\texttt{)}$, kde $q_j\in\delta(q_i,x)$ a $q_k\in\delta(q_i,\varepsilon)$ a $w_r$ predstavuje ešte nespracovanú časť slova. Štandardne vráti elementárnu disjunkciu všetkých volaní funkcií $\texttt{qk(}xw_r\texttt{)}$, kde $q_k\in\delta(q_i,\varepsilon)$.
• Vo všetkých ostatných prípadoch vráti funkcia $\texttt{qi}$ pravdivostnú hodnotu $\texttt{False}$.

$$\texttt{qi(}w\texttt{)} = \left\{\begin{array}{ll} \texttt{True}, & \text{ak } w=\varepsilon\;\land\;q_i\in F\\ \bigvee_{q_j\in\delta(q_i,x)}\texttt{qj(}w_r\texttt{)}\;\lor\; \bigvee_{q_k\in\delta(q_i,\varepsilon)}\texttt{qk(}w\texttt{)}\;\lor\;\texttt{False}, & \text{ak } w=xw_r \end{array}\color{transparent}\right\}$$

Nasledujúce fragmenty kódu predstavujú princíp implementácie koncových a nekoncových stavov NKA v jazyku python.

#implementácia funkcie zodpovedajúcej koncovému stavu qi
def qi(word):
    if len(word) == 0:
        return True
    else:
        if word[0] == 'j':
            return qj1(word[1:]) or '''...''' 
            qjn(word[1:]) or qk1(word) or '''...''' qkm(word)
        #...    
        else:
            return q_k1(word) or '''...''' q_km(word) or False

#implementácia funkcie zodpovedajúcej stavu qi
def qi(word):
    if len(word) > 0:
        if word[0] == 'j':
            return qj1(word[1:]) or '''...''' 
            qjn(word[1:]) or qk1(word) or '''...''' qkm(word)
        #...
        else:
            return qk1(word) or '''...''' qkm(word) or False
    return qk1(word) or '''...''' qkm(word) or False

Volaním funkcie $\texttt{q0}$ zodpovedajúcej počiatočnému stavu implementovaného NKA s argumentom predstavujúcim vstupné 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 rekurzívny presnejšie povedané 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.

def q0(word):
    return q3(word) or q1(word)

def q1(word):
    if len(word) > 0:
        if word[0] == '0':
            return q2(word[1:])
        else:
            return False
    else:
        return False

def q2(word):
    if len(word) == 0:
        return True
    else:
        return False

def q3(word):
    if len(word) > 0:
        if word[0] == '1':
            return q4(word[1:])
        else:
            return False
    else:
        return False

def q4(word):
    if len(word) == 0:
        return True
    else:
        return q5(word)

def q5(word):
    if len(word) == 0:
        return True
    else:
        return q6(word)

def q6(word):
    return q9(word) or q7(word)

def q7(word):
    if len(word) > 0:
        if word[0] == '0':
            return q8(word[1:])
        else:
            return False
    else:
        return False

def q8(word):
    if len(word) == 0:
        return True
    else:
        return q6(word)

def q9(word):
    if len(word) > 0:
        if word[0] == '1':
            return q10(word[1:])
        else:
            return False
    else:
        return False

def q10(word):
    if len(word) == 0:
        return True
    else:
        return q6(word)

def main():
    while True:
        input_word = input("Enter input word: ")
        print(f"Word '{input_word}' is {'ACCEPTED' if q0(input_word) else 'NOT ACCEPTED'}!")

if __name__ == "__main__":
    main()

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 internú 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é.