06.2 Použití pumping lemma

Last updated Nov 9, 2022

Použití pumping lemma k důkazu, že jazyk není regulární

• Důkaz, že jazyk $L = {0^{n}1^{n}: n \ge 1}$ není regulární

  • Předpokládejme, že $L$ je regulární
  • Pak pomocí pumping lemma musí platit, že existuje $p \ge 1$, že $w \in L$ lze zapsat ve tvaru $xyz$

• Věta $w = 0^{n}1^{n} \in L$ je zřejmě delší než $p \rightarrow$ musí splňovat PL

• K důkazu zkusíme všechny možné rozdělení $w$ na $xyz$

• Musíme pak ukázat, že každé z nich porušuje alespoň jednu z podmínek PL

1. Vyberu jednu vhodnou větu $w \in L$, jejíž délka $\ge p$
   • $w = 0^{p}1^{p}$
   • $00\dots011\dots1$
   • protože má $p \times$ symbolů $0$ a $p \times$ symbolů $1 \Rightarrow$ má $2p$ symbolů, tedy je delší než $p$
2. Dokázat, že nelze rozepsat jako $xyz$
   • $xy$ může dosahovat pouze do první jedničky (vyjma ní) - neprázdná posloupnost nul
     • $x = 0^{k}, \enspace k \ge 0$
     • $y = 0^{j}, \enspace j \ge 1$
     • $k+j \le p$
   • $z$ - obsahuje všechny jedničky
     • $z = 0^{\ell} 1^{p}$
     • $k+j+\ell=p$
3. Vyzkoušet, jestli pro všechny moje způsoby v kroku 2 platí třetí podmínka
   • Např. pro $i = 0$
     • $xy^{0}z = xz = 0^{k}0^{j}1^{p}$
     • $k+j+p$ je ale menší než $p$, nerovná se $p$
     • tedy tato věta nepatří do $L$
4. $\square$