Matematické Fórum

Dobrý den

Chtěl bych se zeptat na několik věcí ohledně pumping lemmatu.
Mám následující přiklad:


Dejme tomu, že na tomto příkladu někomu vysvětluji pumping lemma a chci dokázat, že uvedený jazyk L není bezkontextový.
Postupuji takto:
1. A si zvolí libovolné přirozené číslo n (prostě libovolné, neřeknu žádné konkrétní, může být jakékoli)
2. B zvolí slovo z takové, že patří do L ale je větší nebo rovno n, např. protože bude vždy |z| >= n
3. A a tady jsem skončil.. Nevím, jestli si pomyslet nějaké konkrétní slova pro u, v, w, x, y protože pomyslet na všechny libovolné, které mohou nastat je trochu obtížné. Takže asi bych to vysvětlil tak, že pokud bych zvolil n = 1 tak zvolím:
u = 010
v = 1
w = prazdne slovo
x = prazdne slovo
y = prazdne slovo
kde |vwx| <= n, tj. |vwx| = 1 a |vx| >= 1, tj. |vx| = 1. Sedí
4. B zvolí třeba i = 0, i nemůže být 1, protože by v téhle kombinaci nešlo ověřit, jestli to je nebo není CFL.
Dá se nějak snadno zjistit, pro jaké i to nejde ověřit pro libovolný jazyk, který chci ověřit?
5. Protože , (pro i = 0) rovno 010, což nepatří do jazyka L, tak vyhrává B => není to CFL.

Chápu to správně? Dělám někde chybu?

Děkuji