====== JFiZO - Zadanie 09.025 ======

$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)$.

{{tag>listy_zadan}}