====== JFIZO - Zadanie 09.036 ======

**Zadanie.** Czy $L = \{ wvw : w, v \in \{0, 1\}^* \wedge |w| = |v| \}$ 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 $1^N0^N1^N$. Musielibyśmy móc pompować wszystkie trzy części tego słowa, a te części są odległe o więcej niż $N$. Zatem język nie jest bezkontekstowy.