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.