Konečnostavové akceptory. DKA

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í. Samotný princíp určenia jazyka pomocou regulárneho výrazu spočíva v špecifikácii vzoru, ktorý splňajú všetky slová (reťazce) tohto jazyka, ktoré preto možno označiť za konkrétne inštancie tohto vzoru. Ďalej 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

Ďalším z pokročilých spôsobov špecifikácie jazyka je takzvaný akceptačný spôsob využitím automatu. Automat predstavuje v teórii informatiky bežne využívaný matematický model, ktorý na vstupe prijíma reťazec zložený z terminálnych symbolov. Ten spracuje a v konečnom čase (po konečnom počte operácií resp. krokov) rozhodne, či daný reťazec patrí do takto určeného jazyka alebo nie (hovoríme, že automat slovo akceptuje resp. neakceptuje).

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é slovo, o ktorom má automat rozhodnúť, či patrí do jazyka. Konečnostavová riadiaca jednotka sa vždy nachádza v určitom stave a vidí jeden aktuálny vstupný symbol na páske. Konečný 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 slova a konečnostavová riadiaca jednotka sa nachádza v tzv. počiatočnom stave. Výpočet sa skončí, keď sa spracuje celé vstupné slovo, alebo keď sa automat zasekne. Automat slovo akceptuje, ak sa mu podarí spracovať celé vstupné slovo, pričom skončí v tzv. akceptujúcom 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 akceptujúcich (alebo koncových) stavov automatu, $F \subseteq Q $.
  

Konfigurácia konečného automatu $M=(Q, T, \delta, q_0, F)$ je usporiadaná dvojica $(q, w) \in Q \times T^* $, kde $q$ je aktuálny stav automatu $M$ a $w$ je ešte nespracovaná časť vstupu.

• Začiatočná konfigurácia automatu $M$ je konfigurácia $ (q_0, w) $, kde $w$ je celý vstupný reťazec.
• Koncová (alebo akceptujúca) konfigurácia automatu $M$ je konfigurácia $ (q, \varepsilon) $ kde $ q \in F $.

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

Postupnosť (sekvencia) konfigurácií $ (q_0, w_0), (q_1, w_1), \ldots, (q_k, w_k) $, pre $ k \in \mathbb{N}_0$ takých, že $$ (q_0, w_0) \vdash (q_1, w_1) \vdash \dots \vdash (q_k, w_k), $$ sa nazýva výpočet DKA $M$ z $ (q_0, w_0) \to (q_k, w_k) $ a vyjadrovať ho budeme v tvare $$ (q_0, w_0) \vdash^k (q_k, w_k). $$

Okrem vyššie uvedeného definujeme nad reláciou prechodu taktiež nasledujúce:

• tranzitívnym uzáverom relácie krok výpočtu nazývame reláciu $ \vdash^+ $ definovanú na množine jeho konfigurácii následovne:
  $ (q,w_1) \vdash^+ (p,w_2) $ práve vtedy, keď existuje $ n \geq 1$ také, že $(q,w_1) \vdash^n (p,w_2) $.

• reflexívnym a tranzitívnym uzáverom relácie krok výpočtu nazývame reláciu $ \vdash^* $ definovanú na množine jeho konfigurácii následovne:
  $ (q,w_1) \vdash^* (p,w_2) $ práve vtedy, keď existuje $ n \geq 0$ také, že $(q,w_1) \vdash^n (p,w_2) $.
  

Slovo $w$ je teda akceptované DKA $M$, ak existuje taký výpočet, že prvá konfigurácia tohto výpočtu je začiatočná konfigurácia so vstupným slovom $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ý (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_1, q_2, \ldots, q_n\}$.

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.

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 vytvárania prechodových grafov 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:

• neiteratívnym resp. rekurzí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},$$ t. j. funkcii, ktorá na vstupe prijíma reťazec a na výstupe poskytne pravdivostnú hodnotu, pri implementácii ktorej 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 $xw_r$ vráti výsledok volania funkcie $\texttt{qj}$ s argumentom $w_r$, ak pre prechodovú funkciu implementovaného DKA platí $\delta(q_i,x)=q_j$.
• 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,\\ \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\}$$

Volaním funkcie $\texttt{q0}$ zodpovedajúcej počiatočnému stavu implementovaného DKA s argumentom predstavujúcim kontrolované slovo 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 neiteratívnom prístupe k jeho implementácii.

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

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

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

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

def q2(word):
    if len(word) == 0:
        return True
    else:
        if word[0] in ('0', '1'):
            return q2(word[1:])
        else:
            return False

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

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 slova (teda pri iterácii nad týmto slovom) mení na základe prechodovej funkcie $\delta$. Ak sa po prečítaní celého slova v tejto internej premennej nachádza koncový stav, slovo je akceptované, v opačnom prípade slovo nebude akceptované. Slovo nebude akceptované taktiež v prípade, ak funkcia $\delta$ neposkytne žiadny nový stav po prečítaní niektorého zo symbolov slova.