====== JFiZO - Zadanie 09.020 ======
Niech $L$ będzie językiem regularnym, a $A = (Q, \Sigma, \delta, q_0, F)$ automatem, który go rozpoznaje. $L' = \{ w : \exists n \in \mathbb{N} \, \exists v \in L \, w^n = v \}$. Pokażemy, że $L'$ jest językiem regularnym.

Niech $Q = \{ 0, 1, \ldots, s\}$. Zdefiniujmy automat $A' = (Q', \Sigma, \delta', q_0', F')$:
  * $Q' = Q^{s+1}$,
  * $q_0' = <0, 1, \ldots, s>$,
  * $\delta'(<i_0, \ldots, i_s>, a) = <\delta(i_0,a), \ldots, \delta(i_s, a)>$, więc $\hat\delta'(<i_0, \ldots, i_s>, w) = <\hat\delta(i_0, w), \ldots, \hat\delta(i_s, w)>$,
  * $<i_0, \ldots, i_s> \in F' \iff \exists k \, \sigma_k \in F$, gdzie $\sigma_0 = q_0, \sigma_{k+1} = i_{\sigma_k}$.

**Przykład stanu akceptującego.** Załóżmy, że $Q = \{0, 1, 2\}, q_0 = 1$ i $F = \{2\}$. Po wczytaniu pewnego słowa, ze stanu początkowego $<0, 1, 2>$ znaleźliśmy się w przykładowym stanie $q = <2, 0, 2>$. Sprawdźmy teraz ciąg $\sigma$. Z definicji wiemy, że $\sigma_0 = q_0 = 1$. Patrzymy na pozycję 1 i tam jest 0, więc $\sigma_1 = 0$. Teraz patrzymy na pozycję 0 i tam jest $2 = \sigma_2$, które jest stanem akceptującym. Czyli $\sigma_k \in F$ dla $k = 2$, czyli cała krotka $<2, 0, 2>$ należy do $F'$. Gdyby $q = <0, 0, 2>$, to byśmy mieli ciąg: 

$\sigma_0 = 1 \to \sigma_1 = 0 \to \sigma_2 = 0 \to \sigma_3 = 0 \ldots$

Taki stan nie byłby akceptujący.

**Twierdzenie.** $L' = L(A')$.

**Dowód $\Rightarrow$.** Weźmy dowolne $w \in L'$. Istnieją $n$ i $v$ takie, że $w^n = v$. Niech $q_1, \ldots, q_n$ będą stanami, w których automat $A$ znajdzie się po wczytaniu słowa $w$ odpowiednio 1 raz, $\ldots$, n razy. Zauważmy, że $\forall i < n \, \hat\delta(q_i, w) = q_{i+1}$ i $q_n \in F$. Przyjrzyjmy się teraz, w jakim stanie będzie automat $A'$ po wczytaniu słowa $w$. Zaczynami w $q_0' = <0, 1, \ldots, s>$, a po wczytaniu słowa $w$ znaleźliśmy się w jakimś stanie $q' = <i_0, \ldots, i_s>$. W stanie $q'$ na pozycji $q_0$ znajduje się stan $\hat\delta(q_0, w) = q_1$. Zatem $\sigma_1 = q_1$. Ogólne, $\sigma_i = q_i$ dla $i \leq n$. Z tego wynika, że $\sigma_n = q_n \in F$, więc $q' \in F'$.

**Dowód $\Leftarrow$.** Weźmy dowolne $w \in L(A')$. Automat $A'$ akceptuje słowo $w$, więc $\hat\delta'(q_0', w) = q' \in F'$.

Skoro $q' \in F'$, to znaczy, że istnieje takie $k$, że $\sigma_k \in F$. Niech $q' = <i_0, i_1, \ldots, i_s>$.

**Lemat.** $\forall j \leq k \Rightarrow \hat\delta(q_0, w^j) = \sigma_j$. Dowód przez indukcję:
  - Dla $j = 0$ mamy $\hat\delta(q_0, 0) = q_0 = \sigma_0$. 
  - Niech twierdzenie będzie prawdziwe dla pewnego $j < k$, czyli $\hat\delta(q_0, w^j) = \sigma_j$. W $q'$ na pozycji $\sigma_j$ znajduje się $\sigma_{j+1} = \hat\delta(\sigma_j, w) = \hat\delta(\hat\delta(q_0, w^j), w) = \hat\delta(q_0, w^{j+1})$.

Z lematu wynika, że dla $j = k$ jest $\hat\delta(q_0, w^k) = \sigma_k \in F$, czyli $w^k \in L$. Zatem $n = k$.   
   
{{tag>[listy_zadan]}}