Deterministické konečnostavové automaty.

Krok 1

Regulárne výrazy predstavujú prvú z pokročilých metód špecifikácie jazyka (konkrétne tzv. regulárneho jazyka), ktorú sme predstavili v predchádzajúcom cvičení. Taktiež vieme, že regulárne výrazy je možné zobraziť aj graficky pomocou prechodových diagramov. Princíp zostrojenia takýchto diagramov bol vysvetlený v predchádzajúcom cvičení.

Prostrednícvom nasledujúceho príkladu zopakujeme tvorbu regulárneho výrazu na základe slovnej špecifikácie ním identifikovaného jazyka a následne pristúpime ku konštrukcii jeho prechodového diagramu.

Krok 2

Jedným z pokročilých spôsobov špecifikácie jazyka je aj jeho akceptácia prostredníctvom automatu. Automat predstavuje v teoretickej informatike bežne využívaný matematický model, ktorý na vstupe prijíma reťazec symbolov. Tento reťazec spracuje a po konečnom počte ktorov rozhodne, či patrí do takto špecifikovaného jazyka alebo nie (hovoríme, že automat reťazec akceptuje resp. neakceptuje).

Existuje viacero druhov automatov, ktoré sa líšia svojou zložitosťou a typom jazykov, ktoré dokážu spracovať. Na tomto a nasledujúcom cvičení sa zameriame na najjednoduchší z nich, tzv. konečnostavové automaty, ktoré dokážu rozpoznať práve triedu regulárných jazykov.

Schému konečnostavového automatu môžeme vidieť na Obr. 1. Tento model sa skladá zo vstupnej pásky a konečnostavovej riadiacej jednotky. Na vstupnej páske je zapísaný reťazec, o ktorom má automat rozhodnúť, či patrí do daného jazyka. Riadiaca jednotka sa vždy nachádza v určitom stave a vidí jeden aktuálny symbol zo vstupnej pásky. Deterministický konečnostavový automat pracuje diskrétne po jednotlivých krokoch. V každom kroku prečíta aktuálny symbol zo vstupnej pásky, presunie čítaciu hlavu na nasledujúci symbol a prejde do nového stavu. Nový stav sa určí na základe pôvodného stavu a prečítaného vstupného symbolu. Na začiatku výpočtu je čítacia hlava nastavená na prvý symbol reťazca a konečnostavová riadiaca jednotka sa nachádza v tzv. počiatočnom stave. Výpočet sa skončí, keď sa spracuje celý vstupný reťazec, alebo keď sa automat zasekne. Reťazec je následne akceptovaný, ak automat po spracovaní celého vstupu skončí v akceptačnom stave.

Uvedené skutočnosti teraz formalizujeme následovne. Deterministický konečnostavový automat (DKA) je usporiadaná pätica $$ M = (Q, T, \delta, q_0, F), $$ kde:

• $ Q $ je konečná množina stavov automatu,
• $ T $ je konečná množina prípustných vstupných symbolov (alebo vstupná abeceda) automatu,
• $ \delta $ je prechodová funkcia automatu, $ \delta: Q \times T \rightharpoonup Q $,
• $ q_0 $ je počiatočný alebo iniciálny stav automatu, $ q_0 \in Q $,
• $ F $ je množina akceptačných stavov automatu, $F \subseteq Q $.
  

Konfigurácia DKA je usporiadaná dvojica $(q, w) \in Q \times T^* $, kde $q$ je aktuálny stav automatu a $w$ je ešte nespracovaná časť vstupu. Vo výpočte automatu sa vyskytujú taktiež osobitné konfigurácie, ktoré zohrávajú špecifickú úlohu pri akceptácii vstupu:

• Začiatočná konfigurácia automatu – je konfigurácia $ (q_0, w) $, kde $w$ je celý vstupný reťazec.
• Koncová konfigurácia automatu – je konfigurácia tvaru $(q, \varepsilon)$, teda taká, pri ktorej bol celý vstup spracovaný.
• Akceptujúca konfigurácia automatu – je koncová konfigurácia, v ktorej $q \in F$.

Na množine konfigurácií $Q \times T^* $ definujeme binárnu reláciu prechodu (alebo krok výpočtu) DKA, označovanú symbolom $\vdash$ nasledovne: 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 \delta(q, x) = p. $$

Výpočtom automatu $M$ nazývame konečnú lineárnu postupnosť konfigurácií $c_0, c_1, \dots c_k$, kde $k \in \mathbb{N}_0$ a pre každé $i \in \left\{0, 1, \ldots, k-1 \right\}$ platí $c_{i} \vdash c_{i+1}$, kde $c_{0}$ je začiatočná konfigurácia a $c_{k}$ je koncová konfigurácia. Každá konfigurácia má tvar $$c_i = (q_i, w_i),$$ pričom $q_i \in Q$ a $w_i \in T^*$. Takýto výpočet budeme označovať symbolicky $c_0 \vdash^k c_k$, kde $k$ predstavuje počet krokov výpočtu.

Na vyjadrenie výpočtového správania automatu v ľubovoľnom počte krokov využijeme uzávery relácie prechodu $\vdash$. Nech $M = (Q, T, \delta, q_0, F)$ je DKA a $\vdash$ je jeho relácia kroku výpočtu. Potom definujeme:

• Tranzitívny uzáver relácie ($\vdash$ alebo $\vdash^{+}$) – je množina všetkých dvojíc $(c, c') \in (Q \times T^{*})^2$, pre ktoré existuje $k \in \mathbb{N}$ a konfigurácie $c_0, \ldots, c_k$ také, že $$c = c_0 \vdash c_1 \vdash \cdots \vdash c_k = c', \qquad k \ge 1.$$
• Reflexívny a tranzitívny uzáver relácie ($\vdash$ alebo $\vdash^{*}$) – je množina všetkých dvojíc $(c, c') \in (Q \times T^{*})^2,$ pre ktoré existuje $k \in \mathbb{N}_0$ a konfigurácie $c_0, \ldots, c_k$ také, že $$c = c_0 \vdash c_1 \vdash \cdots \vdash c_k = c', \qquad k \ge 0.$$

Reťazec $w$ je akceptovaný DKA $M$, ak existuje výpočet, ktorého prvá konfigurácia je začiatočná konfigurácia so vstupným reťazcom $w$ a posledná konfigurácia je koncová akceptujúca konfigurácia, teda $$(q_0,w) \vdash^{*} (q,\varepsilon)\text{, kde }q\in F.$$

Jazyk $L(M)$ rozpoznávaný alebo taktiež akceptovaný konečným automatom $M$ je množina: $$ L(M) = \{ w \mid (q_0, w) \vdash^* (q, \varepsilon) \land w \in T^* \land q \in F \} $$

Krok 3

Konečnostavové automaty sa v teoerickej informatike bežne vytvárajú prostredníctvom zostavenia prechodových tabuliek (ako je tomu v zbierke v kapitole 3.2). Takto vytvorené automaty sú nedeterministické, čo znamená, že pri niektorom vstupe $x$ je prechodová funkcia definovaná nie do jediného možného stavu $q$, ale do množiny možných stavov $Q'\subseteq Q$.

Na transformáciu NKA na DKA sa využíva metóda nazývaná determinizácia. My sa však teraz oboznámime s metódou priamej konštrukcie DKA za základe daného regulárneho výrazu tzv. metódou tokenou. Tá je uvedená v animovanej prezentácii a taktiež detailne popísaná na nasledujúcich príkladoch.

Okrem prezentovanej metódy tokenov existujú aj ďalšie spôsoby priamej konštrukcie DKA zo zadaného regulárneho výrazu, ako napríklad Brzozowského derivácia, s ktorou ste sa oboznamili na prednáškach.

Precvičte si vytváranie deterministického konečnostavového akceptora na základe zadaného regulárneho výrazu s využitím metódy tokenov na nasledujúcich príkladoch.

Krok 4

V predchádzajúcom kroku tohto cvičenia sme sa naučili, ako z regulárneho výrazu priamo vytvoriť DKA. V tomto kroku sa oboznámime s dvoma základnými prístupmi k jeho praktickej programovej implementácii, a to:

• rekurzívnym resp. neiteratívnym a
• iteratívnym prístupom.

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

Vstupom tejto 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 poskytne pravdivostnú hodnotu. Princíp fungovania každej takejto funkcie je nasledovný:

• Ak ide o akceptačný stav ($q_i \in F$) a vstupný reťazec je prázdny ($\varepsilon$), funkcia vráti hodnotu $\texttt{True}$.
• Ak reťazec začína symbolom $x$ a prechodová funkcia určuje $\delta(q_i, x) = q_j$, funkcia rekurzívne zavolá $\texttt{qj}$ so zvyšným reťazcom (bez prvého symbolu) a vráti jej výsledok.
• Vo všetkých ostatných prípadoch funkcia vráti $\texttt{False}$.

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

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

#implementácia funkcie zodpovedajúcej koncovému 
#stavu qi
def qi(string: str) -> bool:
    if len(string) == 0:
        return True
    else:
        if string[0] == 'j':
            return qj(string[1:])
        #...
        elif string[0] == 'k':
            return qk(string[1:])
        else:
            return False

#implementácia funkcie zodpovedajúcej stavu qi
def qi(string: str) -> bool:
    if len(string) > 0:
        if string[0] == 'j':
            return qj(string[1:])
        #...
        elif string[0] == 'k':
            return qk(string[1:])
        else:
            return False
    return False

Volaním funkcie $\texttt{q0}$ zodpovedajúcej počiatočnému stavu implementovaného DKA s argumentom predstavujúcim vstupný reťazec spustíme samotný výpočet DKA. Keďže tento prístup využíva pre spracovanie symbolov vstupného reťazca postupné volanie funkcií zodpovedajúcich jednotlivým stavom implementovaného DKA, hovoríme o rekurzívnom presnejšie povedané neiteratívnom prístupe k jeho implementácii.

def q0(string: str) -> bool:
    if len(string) > 0:
        if string[0] == '0':
            return q1(string[1:])
        elif string[0] == '1':
            return q2(string[1:])
        else:
            return False
    return False

def q1(string: str) -> bool:
    if len(string) == 0:
        return True
    else:
        return False

def q2(string: str) -> bool:
    if len(string) == 0:
        return True
    else:
        if string[0] in ('0', '1'):
            return q2(string[1:])
        else:
            return False

if __name__ == "__main__":
    input_string = input("Zadaj vstupný reťazec> ")
    while input_string != "quit":
        print(
            f"Reťazec '{input_string}' "
            f"{'JE' if q0(input_string) else 'NIE JE'} akceptovaný!"
        )
        input_string = input("Zadaj vstupný reťazec> ")

Okrem vyššie uvedeného prístupu môžno zvoliť aj štandardnejší iteratívny prístup k implementácii DKA, kedy aktuálny stav automatu predstavuje internu premennú, ktorá sa pri postupnom čítaní jednotlivých symbolov vstupného reťazca mení na základe prechodovej funkcie $\delta$. Ak sa po prečítaní celého reťazca v tejto internej premennej nachádza koncový stav, reťazec je akceptovaný, v opačnom prípade reťazec nebude akceptovaný. Reťazec nebude akceptovaný taktiež v prípade, ak funkcia $\delta$ neposkytne žiadny nový stav po prečítaní niektorého zo symbolov vstupného reťazca.