JFiZO - Zadanie 09.003

• Rozwiązanie w Hopcroft, Przykład 3.2, strony 72-73

Zbiór L tych słów nad \lbrace 0,1 \rbrace, które są liczbą pierwszą w zapisie binarnym nie jest regularny.

Ten lemat nie dowodzi równoważności regularności tych języków. Bez tego lematu dowód na dole nic nie daje. — 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.

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ść.