Lemat o pompowaniu

  1. 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}\}.\)
  2. Dowieść, że zbiór palindromów nad alfabetem o co najmniej dwóch elementach nie jest regularny.
  3. Dowieść, że zbiór wyrażeń regularnych nie jest regularny.
  4. 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.
  5. 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.

  6. 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.

  7. 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 ?