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 si predstavili na predchádzajúcom cvičení. Zopakujte si teóriu regulárnych výrazov. 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ý taktiež na predchádzajúcom cvičení.

Prostrednícvom nasledujúceho príkladu si teraz 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 prijma reťazec zložený z terminálnych symbolov. Ten spracuje a v konečnom čase (po konečnom počte operácií) 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 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 momentá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}$ 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). $$

• 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 s kontrolovaný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 bežne v teórii informatiky vytvárajú prostredníctvom zostavenia prechodových tabuliek (ako je tomu v zbierke v kapitole 3.2). Takto vytvorené automaty sú nedeterministické. Nedeterministické automaty sú také, kde pri niektorom vstupe $x$ je definovaná prechodová funkcia nie do jediného možného stavu $q$, ale do množiny možných stavov $\{q_1, q_2, \ldots, q_n\}$. O nedeterministických automatoch si povieme viac v nasledujúcom cvičení.

Na vytvorenie deterministického automatu sa využíva metóda nazývaná determinizácia.

Na tomto predmete sa však využíva iná metóda, vytváranie prechodových grafov , ktorá je uvedená v animovanej prezentácii. Táto metóda má tú výhodu, že pomocou nej je možné vytvoriť priamo deterministický konečnostavový automat a nie je potrebná ďalšia determinizácia. Je ju však možné použiť len vtedy, ak množinu vstupných reťazcov pre konečnostavový automat je možné definovať prostredníctvom regulárnych výrazov.

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 implementácii, a to:

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

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

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{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 $\texttt{q_i}$ vráti pravdivostnú hodnotu $\texttt{True}$, ak $\texttt{q_i}$ zodpovedá koncovému stavu DKA a jej argumentom je prázdny reťazec $\varepsilon$.
• Funkcia $\texttt{q_i}$ na základe prvého symbolu $x$ jej odovzdaného slova $xw_r$ vráti výsledok volania funkcie $\texttt{q_j}$ 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{q_i}$ pravdivostnú hodnotu $\texttt{False}$.

$$\texttt{q_i(}w\texttt{)} = \left\{\begin{array}{ll} \texttt{True}, & \text{ak } w=\varepsilon\;\land\;q_i\in F\\ \texttt{q_j(}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 q_0 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 ide o neiteratívny prístup k jeho implementácii.

/*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_j(&word[1]);
            /*...*/
            case 'k':
                return q_k(&word[1]);

            default:
                return false;
        }
    }
}

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

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 týmto slovom) mení na základe prechodovej funkcie $\delta$. Ak sa po prečítaní celého slova v tejto internej premennej nacháda 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.