Konečnostavové akceptory – determinizácia. Pumpovacia lema.

Krok 1

V rámci predchádzajúceho cvičenia sme uviedli, že NKA a DKA predstavujú expresívne ekvivalentné modely. Je teda zrejmé, že ku každému NKA musí existovať DKA akceptujúci rovnaký jazyk. V tomto kroku sa preto pozrieme bližšie na princíp konštrukcie ekvivalentného DKA zo zadaného NKA, teda na proces zvaný determinizácia NKA vyjadrený nasledujúcim Algoritmom 1.

Algoritmus 1. Konštrukcia ekvivalentného DKA k NKA.
Vstup: NKA $M=(Q,T,\delta,q_0,F)$.
Výstup: Množina stavov $\acute{Q}$ a prechodová funkcia $\acute{\delta}$ ekvivalentného DKA.

1. $\acute{\delta}\leftarrow\bot;$
2. $\acute{Q}\leftarrow\{\mathit{CLOSURE}_\varepsilon(\{q_0\})\}$ a označ tento zložený stav za nespracovaný;
3. while v $\acute{Q}$ existujú nespracované stavy do
4.   vyber z $\acute{Q}$ ľubovoľný nespracovaný stav $q$ a označ ho za spracovaný;
5.   for all $a\in T$ do
6.    $p\leftarrow\mathit{CLOSURE}_\varepsilon(\cup_{q_i\in q}\delta(q_i,a))$;
7.    if $p \notin \acute{Q}$ then
8.     $\acute{Q}\leftarrow\acute{Q}\cup\{p\}$ a označ $p$ ako nespracovaný;
9.    end if
10.    $\acute{\delta}\leftarrow\acute{\delta}\cup\{(q,a)\mapsto p\}$;
11.   end for
12. end while

Slovný opis algoritmu:

Algoritmus 1. Konštrukcia ekvivalentného DKA k NKA.
Vstup: NKA $M=(Q,T,\delta,q_0,F)$.
Výstup: Množina stavov $\acute{Q}$ a prechodová funkcia $\acute{\delta}$ ekvivalentného DKA.

1. Inicializuj $\acute{\delta}$ prázdnou množinou.
2. Inicializuj $\acute{Q}$ výsledkom volania funkcie $\mathit{CLOSURE}_\varepsilon$ na množinu obsahujúcu počiatočný stav $q_0$ a označ tento zložený stav za nespracovaný.
3. while v $\acute{Q}$ existujú nespracované stavy, do
4.   Vyber z $\acute{Q}$ ľubovoľný nespracovaný stav $q$ a označ ho za spracovaný.
5.   for all symboly $a$ zo vstupnej abecedy $T$ do
6.    Do $p$ priraď výsledok aplikácie funkcie $\mathit{CLOSURE}_\varepsilon$ na množinu všetkých elementárnych     stavov, do krorých sa možno dostať zo všetkých elementárnych stavov zloženého stavu $q$ po    prečítaní symbolu $a$.
7.    if sa zložený stav $p$ nenachádza v množine $\acute{Q}$ then
8.     Do $\acute{Q}$ pridaj $p$ a označ ho ako nespracovaný.
9.    end if
10.    Do $\acute{\delta}$ pridaj nový prechod zo stavu $q$ do stavu $p$ cez symbol $a$.
11.   end for
12. end while

Algoritmus 2. Určenie výsledku operácie $\mathit{CLOSURE_\varepsilon}$.
Vstup: Prechodová funkcia $\delta$ NKA $M$, množinu stavov $S\subseteq Q$.
Výstup: Množina stavov $S$ uzavretá vzhľadom na $\varepsilon$-prechody.

1. function $\mathit{CLOSURE_\varepsilon}(S)$
2.   do
3.    $\acute{S}\leftarrow S$;
4.    $S\leftarrow S\cup_{q\in\acute{S}}\delta(q,\varepsilon)$;
5.   while $S\neq\acute{S}$
6.   return S;
7. end function

Slovný opis algoritmu:

Algoritmus 2. Určenie výsledku operácie $\mathit{CLOSURE_\varepsilon}$.
Vstup: Prechodová funkcia $\delta$ NKA $M$, množinu stavov $S\subseteq Q$.
Výstup: Množina stavov $S$ uzavretá vzhľadom na $\varepsilon$-prechody.

1. function $\mathit{CLOSURE_\varepsilon}(S)$
2.   do
3.    Skopríruj obsah $S$ do $\acute{S}$.
4.    Do $S$ pridaj všetky stavy, do ktorých sa možno dostať zo stavov z množiny $\acute{S}$ cez $\varepsilon$-prechod.
5.   while je obsah $S$ rôzny od obsahu $\acute{S}$
6.   return S;
7. end function

Príklad

Formálne definujte a následne determinizujte NKA s nasledujúcim diagramom.

Riešenie

$$M=(\{q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_8,q_9,q_{10}\},\{0,1\},\delta,q_0,\{q_2,q_5,q_8,q_{10}\})$$ Prechodovú funkciu $\delta$ definujeme pomocou prechodovej tabuľky, a to nasledovne:

stav	$0$	$1$	$\boldsymbol\varepsilon$
$q_0$	$\emptyset$	$\emptyset$	$\{q_1,q_3\}$
$q_1$	$\{q_2\}$	$\emptyset$	$\emptyset$
$q_2$	$\emptyset$	$\emptyset$	$\emptyset$
$q_3$	$\emptyset$	$\{q_4\}$	$\emptyset$
$q_4$	$\emptyset$	$\emptyset$	$\{q_5\}$
$q_5$	$\emptyset$	$\emptyset$	$\{q_6\}$
$q_6$	$\emptyset$	$\emptyset$	$\{q_7,q_9\}$
$q_7$	$\{q_8\}$	$\emptyset$	$\emptyset$
$q_8$	$\emptyset$	$\emptyset$	$\{q_6\}$
$q_9$	$\emptyset$	$\{q_{10}\}$	$\emptyset$
$q_{10}$	$\emptyset$	$\emptyset$	$\{q_6\}$

Teraz možno pristúpiť k determinizácii NKA $M$ na základe Algoritmu 1.
Najprv potrebujeme inicializovať množinu nových stavov $\acute{Q}$ výsledkom aplikácie funkcie $\mathit{CLOSURE}_\varepsilon$ na $\{q_0\}$, ktorej postupný výpočet prezentuje nasledujúca tabuľka.

Iterácia logického cyklu	Množina $S$	Množina $\acute{S}$	Podmienka cyklu $S\neq\acute{S}$
1.	$\{q_0,q_1,q_3\}$	$\{q_0\}$	$\mathit{true}$
2.	$\underline{\underline{\{q_0,q_1,q_3\}}}$	$\{q_0,q_1,q_3\}$	$\mathit{false}$
$\phantom{1.}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\mathit{false}}$

$\acute{Q}$ sa teda inicializuje zloženým stavom $\{q_0,q_1,q_3\}_N$. Hodnoty premenných na konci jednotlivých iterácií nasledujúcich cyklov sú prehľadne prezentované v nasledujúcej tabuľke.

Iterácia vonkajšieho cyklu	Zložený stav $q$	Iterácia vnútorneho cyklu	Symbol $a$	Zložený stav $p$	Prírastok množiny $\acute{Q}$	Prírastok prechodovej funkcie $\acute{\delta}$
1.	$\{q_0,q_1,q_3\}$	1.	$0$	$\{q_2\}$	$\{q_2\}_N$	$(\{q_0,q_1,q_3\},0)\mapsto\{q_2\}$
1.	$\{q_0,q_1,q_3\}$	2.	$1$	$\{q_4,q_5,q_6,q_7,q_9\}$	$\{q_4,q_5,q_6,q_7,q_9\}_N$	$(\{q_0,q_1,q_3\},1)\mapsto\{q_4,q_5,q_6,q_7,q_9\}$
2.	$\{q_2\}$	1.	$0$	$\emptyset$	$\emptyset_N$	$(\{q_2\},0)\mapsto\emptyset$
2.	$\{q_2\}$	2.	$1$	$\emptyset$		$(\{q_2\},1)\mapsto\emptyset$
3.	$\{q_4,q_5,q_6,q_7,q_9\}$	1.	$0$	$\{q_6,q_7,q_8,q_9\}$	$\{q_6,q_7,q_8,q_9\}_N$	$(\{q_4,q_5,q_6,q_7,q_9\},0)\mapsto\{q_6,q_7,q_8,q_9\}$
3.	$\{q_4,q_5,q_6,q_7,q_9\}$	2.	$1$	$\{q_6,q_7,q_9,q_{10}\}$	$\{q_6,q_7,q_9,q_{10}\}_N$	$(\{q_4,q_5,q_6,q_7,q_9\},1)\mapsto\{q_6,q_7,q_9,q_{10}\}$
4.	$\emptyset$	1.	$0$	$\emptyset$		$(\emptyset,0)\mapsto\emptyset$
4.	$\emptyset$	2.	$1$	$\emptyset$		$(\emptyset,1)\mapsto\emptyset$
5.	$\{q_6,q_7,q_8,q_9\}$	1.	$0$	$\{q_6,q_7,q_8,q_9\}$		$(\{q_6,q_7,q_8,q_9\},0)\mapsto\{q_6,q_7,q_8,q_9\}$
5.	$\{q_6,q_7,q_8,q_9\}$	2.	$1$	$\{q_6,q_7,q_9,q_{10}\}$		$(\{q_6,q_7,q_8,q_9\},1)\mapsto\{q_6,q_7,q_9,q_{10}\}$
6.	$\{q_6,q_7,q_9,q_{10}\}$	1.	$0$	$\{q_6,q_7,q_8,q_9\}$		$(\{q_6,q_7,q_9,q_{10}\},0)\mapsto\{q_6,q_7,q_8,q_9\}$
6.	$\{q_6,q_7,q_9,q_{10}\}$	2.	$1$	$\{q_6,q_7,q_9,q_{10}\}$		$(\{q_6,q_7,q_9,q_{10}\},1)\mapsto\{q_6,q_7,q_9,q_{10}\}$

Pre zjednodušenie zavedieme nasledujúce substitúcie: $$\underbrace{\{q_0,q_1,q_3\}}_{A},\underbrace{\{q_2\}}_{B},\underbrace{\{q_4,q_5,q_6,q_7,q_9\}}_{C},\emptyset,\underbrace{\{q_6,q_7,q_8,q_9\}}_{D},\underbrace{\{q_6,q_7,q_9,q_{10}\}}_{E}$$

Konštrukcia $\mathit{CLOSURE}_\varepsilon(\{q_2\})$

Iterácia logického cyklu	Množina $S$	Množina $\acute{S}$	Podmienka cyklu $S\neq\acute{S}$
1.	$\underline{\underline{\{q_2\}}}$	$\{q_2\}$	$\mathit{false}$
$\phantom{1.}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\mathit{false}}$

Konštrukcia $\mathit{CLOSURE}_\varepsilon(\{q_4\})$

Iterácia logického cyklu	Množina $S$	Množina $\acute{S}$	Podmienka cyklu $S\neq\acute{S}$
1.	$\{q_4,q_5\}$	$\{q_4\}$	$\mathit{true}$
2.	$\{q_4,q_5,q_6\}$	$\{q_4,q_5\}$	$\mathit{true}$
3.	$\{q_4,q_5,q_6,q_7,q_9\}$	$\{q_4,q_5,q_6\}$	$\mathit{true}$
4.	$\underline{\underline{\{q_4,q_5,q_6,q_7,q_9\}}}$	$\{q_4,q_5,q_6,q_7,q_9\}$	$\mathit{false}$
$\phantom{1.}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\mathit{false}}$

Konštrukcia $\mathit{CLOSURE}_\varepsilon(\emptyset)$

Iterácia logického cyklu	Množina $S$	Množina $\acute{S}$	Podmienka cyklu $S\neq\acute{S}$
1.	$\underline{\underline{\emptyset}}$	$\emptyset$	$\mathit{false}$
$\phantom{1.}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\mathit{false}}$

Konštrukcia $\mathit{CLOSURE}_\varepsilon(\{q_8\})$

Iterácia logického cyklu	Množina $S$	Množina $\acute{S}$	Podmienka cyklu $S\neq\acute{S}$
1.	$\{q_8,q_6\}$	$\{q_8\}$	$\mathit{true}$
2.	$\{q_8,q_6,q_7,q_9\}$	$\{q_8,q_6\}$	$\mathit{true}$
3.	$\underline{\underline{\{q_8,q_6,q_7,q_9\}}}$	$\{q_8,q_6,q_7,q_9\}$	$\mathit{false}$
$\phantom{1.}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\mathit{false}}$

Konštrukcia $\mathit{CLOSURE}_\varepsilon(\{q_{10}\})$

Iterácia logického cyklu	Množina $S$	Množina $\acute{S}$	Podmienka cyklu $S\neq\acute{S}$
1.	$\{q_{10},q_6\}$	$\{q_{10}\}$	$\mathit{true}$
2.	$\{q_{10},q_6,q_7,q_9\}$	$\{q_{10},q_6\}$	$\mathit{true}$
3.	$\underline{\underline{\{q_{10},q_6,q_7,q_9\}}}$	$\{q_{10},q_6,q_7,q_9\}$	$\mathit{false}$
$\phantom{1.}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\{q_4,q_5,q_6,q_7,q_9\}}$	$\phantom{\mathit{false}}$

Krok 2

Pumpovacia lema (z angl. pumping lemma) (PL) pre regulárne jazyky sa týka štruktúry týchto jazykov. Jej platnosť vyplýva z obmedzených možností konečnostavových automatov uchovávať informácie o histórii spracovania vstupu – "pamäť" konečného automatu je obmedzená na konečný počet stavov a vstupné slovo môže byť prečítané iba raz, sekvenčne.

Nech $L$ je regulárny jazyk. Potom existuje prirodzené číslo $p$, nazývané pumpovacia dĺžka, také, že pre všteky slová $w \in L$, ktorých dĺžka $|w| \geq p$, existuje rozklad $w = xyz$, pre ktorý platí:

1. $|xy| \leq p$,
2. $|y| > 0$,
3. $\forall i\in \mathbb{N}_0$: $xy^iz \in L$.

Teraz sa pozrieme na intuíciu za pumpovacou lemou pre regulárne jazyky. Keďže konečnostavový automat má len konečný počet stavov a pri každom prechode možno spravovať naviac jeden symbol slova je zrejmé, že v prípade, ak automat spracováva dostatočne dlhé slovo $w=xyz$ (ktorého dĺžka $|w|$ je väčšia ako počet stavov $|Q|$ automatu rozpozávajúceho tento regulárny jazyk), musí sa aspoň jeden stav v akceptujúcom výpočte zopakovať (Dirichletov princíp). $$(q_0,xyz)\vdash^*\boxed{(q,yz)\vdash^*(q,z)}\vdash^*(q_f,\varepsilon)$$

Inými slovami v diagrame tohto automatu musí existovať cyklus (resp. slučka), ktorý toto opakovanie stavu zabezpečia (pozri Obr 3.). Z tohto zároveň vyplýva, že touto slučkou resp. cyklom možno prejsť ľubovoľný početkrát, čo zabezpečí taktiež akceptovanie slov tvaru $xy^iz$, pre ľubovoľné $i\in \mathbb{N}_0$ (pozri 3. bod PL). Každé dostatočne dlhé slovo v regulárnom jazyku teda obsahuje časť, ktorú môžeme "napumpovať" ($y^i$) a stále zostaneme v jazyku (odtiaľ názov pumpovacia lema).

Krok 3

V tejto časti sa pozrieme na praktické využitie pumpovacej lémy pri dôkaze neregularity jazyka. Pri tomto konkrétnom type dôkazu postupujeme metódou dôkazu sporom (z lat. reductio ad absurdum), kedy dokazované tvrdenie negujeme, predpokladáme platnosť tejto negácie a snažíme sa odvodiť spor. V prípade odvodenia sporu je negované tvrdenie neplatné a pôvodné tvrdenie možno prehlásiť za pravdivé.