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

$$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:

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 operácie $\mathit{CLOSURE}_\varepsilon$ aplikovanej na $\{q_0\}$, postupný výpočet ktorej prezentuje nasledujúca tabuľka.

$\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ácií nasledujúcich cyklov sú prehľadne prezentované v tejto tabuľke.

Výpočet $\mathit{CLOSURE}_\varepsilon(\{q_2\})$

Výpočet $\mathit{CLOSURE}_\varepsilon(\{q_4\})$

Výpočet $\mathit{CLOSURE}_\varepsilon(\emptyset)$

Výpočet $\mathit{CLOSURE}_\varepsilon(\{q_8\})$

Výpočet $\mathit{CLOSURE}_\varepsilon(\{q_{10}\})$

1. Prvým krokom dôkazu neregularity jazyka $L$ je predpoklad, že tento jazyk je regulárny a platí preň pumpovacia lema.

2. Predpokladáme, že existuje také číslo $p$ (pumpovacia dĺžka alebo pumpovacia konštanta), že slová s dĺžkou aspoň $p$ možno rozdeliť na základe vyššie prezentovaného princípu na 3 časti $x,y,z$.

3. Určime slovo $w$, pre ktoré platí $|w|\geq p.$ Takýmto slovom je napíklad slovo $a^pb^p$, keďže $$|w|=|a^pb^p|=|a^p|+|b^p|=p+p=\underline{\underline{2p\geq p}}.$$

4. Teraz sa pozrieme na všetký možné dekompozície tohto slova.
   Na základe prvého bodu PL platí $|xy|\leq p$. Vieme že $xp$ je podľa definície predponou našho slova $w$, keďže dĺžka tejto predpony je menšia rovná $p$ a vieme, že na začiatku slova $w$ sa nachádza $p$ symbolov $a$, je zrejmé, že predpona $xy$ môže pozostávať len zo symbolov $a$. Z toho teda vyplýva: $$ \begin{align*} &x=a^\alpha, \alpha\geq 0 \text{ a}\\ &y=a^\beta, \beta> 0 \text{ (na základe 2. bodu PL.)} \end{align*} $$ Taktiež platí: $$ \begin{align*} |xy|&\leq p\quad \text{(1. bod PL)}\\ |a^\alpha a^\beta|&\leq p\\ |a^\alpha|+|a^\beta|&\leq p\\ \alpha+\beta&\leq p\\ \end{align*} $$ Príponu tohto slova $z$, potom možno vyjadriť ako zvyšný počet symbolov $a$ (v prípade ak $\alpha+\beta< p$) nasledovaný $p$ symbolmi $b$, teda $$z=a^{p-\alpha-\beta}b^p.$$ V prípade, ak $\alpha+\beta=p$ počet symbolov $a$ v prípone $z$ bude rovný $0$. Dané slovo $w$ budete teda po dekompozí vyzerať nasledovne: $$w=\underbrace{a^\alpha}_{x}\underbrace{a^\beta}_{y}\underbrace{a^{p-\alpha-\beta}b^p}_{z}.$$

5. V poslednom kroku ukážeme spor s platnosťou 3. bodu PL, a teda $$\forall i\in\mathbb{N}_0: xy^iz\in L.$$ Zapíšme teda slovo $xy^iz$ pomocou symbolov abecedy tohto jazyka: $$w=\underbrace{a^\alpha\phantom{)}}_{x}\underbrace{(a^\beta)^i}_{y^i}\underbrace{\phantom{(}a^{p-\alpha-\beta}b^p}_{z}=a^\alpha a^{\beta i}a^{p-\alpha-\beta}b^p.$$ Slovo, takéhoto tvaru može patriť jazyku $L$ len v prípade, ak má rovnaký počet sybolov $a$ a symbolov $b$. Preto musí platiť: $$ \begin{align*} \alpha + \beta i + p-\alpha-\beta &= p\\ \beta i + p-\beta &= p\quad /-p\\ \beta i -\beta &= 0\\ \beta (i-1) &= 0\quad/\frac{1}{\beta} \text{(ekvivalentná úpravu, keďže }\beta>0\text{)}\\ i-1 &= 0\quad /+1\\ i &=1 \end{align*} $$ Platí, teda že slovo $xy^iz$ bude mať rovnaký počet symbolov $a$ a $b$ len v jednom jedinom prípade, a to ak $i=1$, čo popiera platnosť 3. bodu PL a predstavuje SPOR s predpokladom, že jazyk $L$ je regulárny. Pre názornosť zvoľme $i\neq 1$, napíklad 2 a ukážme, že slovo $xy^{2}z$ nebude patriť jazyku $L$ $$xy^{2}z=a^{\alpha}(a^{\beta})^2a^{p-\alpha-\beta}b^p=a^{\alpha}a^{2\beta}a^{p-\alpha-\beta}b^p.$$ Toto slovo môže patriť jazyku $L$ len v prípade, ak bude platiť: $$ \begin{align*} \alpha+2\beta+p-\alpha-\beta &=p\\ p+\beta &=p\\ \end{align*} $$ Z predpokladu však vieme, že $\beta>0$, takéto slovo by teda nemohlo mať rovnaký počet symbolov $a$ a $b$, $p+\beta \neq p$. Našli sme kontrapríklad 3. bodu PL.

Záver: Jazyk $L$ nie je regulárny Q.E.D.