====== JFiZO - Zadanie 09.003 ======
  *Rozwiązanie w Hopcroft, Przykład 3.2, strony 72-73

===== Treść =====
Zbiór $L$ tych słów nad $\lbrace 0,1 \rbrace$, które są liczbą pierwszą w zapisie binarnym nie jest regularny.
===== Lemat 1 =====
 FIXME Ten lemat nie dowodzi równoważności regularności tych języków. Bez tego lematu dowód na dole nic nie daje.
 --- //[[all3@eww.pl|Alistra]] 2010/03/07 21:55//
\\ \\

Niech $N = \{ 1^n | n - prime \}$ nad {1}.\\

Każde słowo z $N$ ma równoważne sobie słowo w $L$. (== jęzki N i L są równoważne?)\\
**Dowód $\Leftarrow$.** \\
$f(l_1l_2...l_n \in L) = 1^{\sum_{i=1}^{i=n}2^il_i} \in N$\\
**Dowód $\Rightarrow$.** \\
$f^{-1}(1^n \in N) = l_1l_2...l_m \in L$ t.że $l_1l_2...l_m = n$ w zapisie binarnym.
===== Dowód =====

Pokażemy, że $N$ nie jest regularny.\\
Załóżmy niewprost, że $N$ jest regularny. Istnieje więc $p$ t.że dla każdego $s = xyz = 1^n \in N$, $|s| >= p$ zachodzi $xy^iz \in N$.\\
Niech:
  *$|x| = len_x$, $|y| = len_y$, $|z| = len_z$
  *Skoro $xyz \in N$ to $prime(len_x + len_y + len_z) == true$.\\
  *Skoro $N$ jest regularny, to $prime(len_x + len_y * i + len_z) == true$\\
  *Niech $i = len_x + len_z + 2*len_y + 2$, wtedy:\\
$len_x + len_z + i * len_y = $\\
$(len_x + len_z) + (len_x + len_z + 2*len_y + 2) * len_y = $\\
$(len_x + len_z) + (len_x + len_z) * len_y + (2*len_y + 2) * len_y = $\\
$(len_x + len_z) * (1 + len_y) + 2 * (len_y + 1) * len_y = $\\
$(1 + len_y) * (len_x + len_z + 2 * len_y)$.\\
  *$len_y \geq 1$ z lematu o pompowaniu. Rozłożyliśmy więc liczbę pierwszą na składniki $> 1$. Sprzeczność.

{{tag>[listy_zadan]}}
{{tag>[jfizolista2]}}