====== JFIZO - Zadanie 09.042 ======

**Zadanie.** Czy $L = \{ 0^n1^{n^2} : n \in N \}$ jest bezkontekstowy?

Nie jest.

**Dowód.** Załóżmy nie wprost, że $L$ jest bezkontekstowy. Niech $N$ będzie stałą z lematu o pompowaniu. Rozpatrzmy słowo $w = 0^N1^{N^2} = sztyx$. Musimy pompować zarówno zera jak i jedynki. Ani $z$ ani $y$ nie może zawierać zarówno jedynek jak i zer. $z = 0^a$, $y = 1^b$. Czy słowo $sz^2ty^2x \in L$? Przybyło $a$ zer i $b$ jedynek. Czy $(N+a)^2 = N^2+b$? $(N+a)^2 = N^2 + 2Na + a$. Wiemy, że $b < N$. Jeśli $a = 0$ to $b = 0$, sprzeczność. Jeśli $a \not= 0$ to $b = 2Na + a \ge N$, sprzeczność.