Lemat o pompowaniu | Informatyka MIMUW

Dowieść, że następujące języki nie są regularne:
1. $\{ a^{n}b^{n}\,:\, n\in N\}$
2. $\{ a^{{2^{n}}}\,:\, n\in N\}$
3. $\{ a^{{p}}\,:\, p\mbox{ jest liczb"a pierwsz"a}\}$
4. $\{ a^{{i}}b^{j}\,:\,\mbox{nwd}(i,j)=1\}$
5. $\{ a^{m}b^{n}\,:\, m\neq n\}$
6. $\{\mbox{bin}(p)\,:\, p\mbox{ jest liczb"a pierwsz"a}\}.$
Dowieść, że zbiór palindromów nad alfabetem o co najmniej dwóch elementach nie jest regularny.
Dowieść, że zbiór wyrażeń regularnych nie jest regularny.
Dowieść, że jeśli w Zadaniu ?? z punktu ?? zamienimy dodawanie przez mnożenie, to otrzymany język (nad alfabetem $\{ 0,1\}^{3}$ ) jest wprawdzie dobrze określony, ale nie jest regularny.
Udowodnić nieco silniejszy wariant Lematu o pompowaniu:

Jeśli $L$ jest regularny, to

(*) Istnieje stała $n_{0}$ , że dla każdych słów $v,w,u$ takich że $|w|\geq n_{0}$ i $vwu\in L$ , istnieją $x,y,z$ takie, że $w=xyz$ , $0< |y|\leq n_{0}$ , oraz $\forall n\in{\bf N},\, vxy^{n}zu\in L$ .

Podać przykład języka $L$ , który spełnia (*), choć nie jest regularny.

Wskazówka. $\sum _{p}\underbrace{cb^{*}cb^{*}\ldots cb^{*}}_{p}+(b+c)^{*}cc(b+c)^{*}$ , gdzie $p$ przebiega liczby pierwsze.
Czy jest regularny język:

$\{ w\in(a+b)^{*}:\ \# _{a}(u)>2009\cdot\# _{b}(u)\textrm{\quad dla ka"rdego niepustego prefiksu $u$ s"lowa $w$}\}$ $u$ słowa $w$

$\# _{s}$ oznacza liczbę wystąpień symbolu $s$ w słowie.
Słowo binarne $x$ jest antypalindromem gdy dla pewnego niepustego słowa $z$ , oraz $s\in\{ 0,1\}$ zachodzi:

$x\ =\ z\;\bar{z}^{R}$ lub $x\ =\ z\; s\;\bar{z}^{R}$ ,

gdzie $\bar{z}$ oznacza negację (logiczną) elementów w $z$ . Np. 0010011, 0011 są antypalindromami, a słowo puste i pojedyńczy symbol nie są. Niech $L$ będzie zbiorem słów binarnych nie zawierających jako podsłowa antypalindromu o długości większej niż 3 zaczynającego się od zera. Czy $L$ jest regularny ?