P = \{p: \mathrm{prime}(p)\}.
P_2 = \{2\cdot p: \mathrm{prime}(p) \wedge p > 3\}.
Lemma 1: d(L_k) = k - nie wprost, d(L_k) < k. 0^k - najkrótsze słowo, którego nie akceptujemy. Ale wtedy pewien stan występuje dwukrotnie, więc nie akceptujemy również pewnego słowa 0^l, l < k, sprzeczność.
Lemma 2: n(L_p) = p, p - prime -
Załóżmy, że n( L_p ) < d( L_p ) = p.
Weźmy słowo 0^{p+1}. Należy ono do języka L_p.
To znaczy, że na drodze do stanu akceptującego w automacie powtórzył nam się jakiś stan,
czyli droga stanów wygląda tak q_0 \to \cdots \to q_k \to \cdots \to q_k \to q_e.
Przyjmijmy, że długoś tego cyklu to q. Chcemy tyle razy powtórzyć ten cykl, aby uzyskać false positive.
z - liczba powtórzeń pętli q podczas wczytywania słowa
w \cdot p - wielokrotność p
\exists w,z.(p+1 - q) + z \cdot q = w\cdot p
Istnieje słowo takiej długości, która jest wielokrotnością p
Nie ma różnicy czy z jest większe lub mniejsze o 1, ważne aby było całkowite.
\exists {z' \in \mathbb{N}} \; 1 + z' \cdot q \equiv_p 0
Dodajemy obustronnie p-1
\exists {z' \in \mathbb{N}} \; z \cdot q \equiv_p p - 1
W grupach \mathbb{Z}_p każdy element jest generatorem, czyli w szczególności zawsze osiagniemy p-1 mnożąc q odpowiednio wiele razy.
Uzyskamy wtedy stan akceptujący dla słowa w postaci 0^{wp}, czyli takiego, co nie należy do jeżyka.
Lemma 3: n(L_{2p}) \le 1 + 2 + p, 2p = 2 * p, p - prime, p > 3 - Nie akceptujemy 0^{n} jeśli 2p | n. 2p | n jeśli 2 | n i p | n. Czyli akceptujemy, jesli 2 \not | n lub p \not | n, nasz automat to mucha z wykladu, akceptuje wszedzie oprocz dwoch stanow do ktorych prowadzi epsilon-przejscie ze stanu startowego.
\displaystyle \forall p \in P. \; d(L_p) = n(L_p).
\displaystyle \forall q \in P_2. \; d(L_q) > n(L_q).