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'):
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ę:
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.