====== JFiZO - Zadanie 09.033 ======

**Zadanie 33.** Czy język $L_4 = \{w \in \{0, 1, 2\}^∗ : \exists x \in \{0, 1, 2\}^∗ \, w = xx\}$ jest bezkontekstowy?

**Twierdzenie.** Język $L_4$ nie jest bezkontekstowy.

**Dowód.** Rozpatrzmy język $L = L_4 \cap L(0^*10^*10^*10^*1)$. Przecięcie języka bezkontekstowego z regularnym, daje nam język bezkontekstowy (dowodu jednak nie będzie, a mógłby polegać na łączeniu dwóch automatu w jeden).

Załóżmy nie wprost, że $L$ jest bezkontekstowy. Na mocy bla bla lemat o pomopowaniu  bla bla stała $N$.

Rozpatrzmy słowo $w = 0^N10^N10^N10^N1$. Nie da się go rozbić na $sztyx$ taki, że $|zty| \leq N$.