Mamy automat rozpoznający słowa z L, nazwijmy go A.
A = (\Sigma, Q, q_0, F, \delta )
Idea jest taka, że budujemy nowy automat, którego zbiorem stanów, jest krotka stanów starego automatu (przedstawiona jako funkcja Q\rightarrow Q) - symbolizuje, gdzie doszełby ten nasz automat wczytając k liter, jeśli zaczynałby w każdym ze stanów oraz podzbiór stanów (podsłowo w) - symbolizuje stany osiągalne po k krokach (dowolną literą)(podsłowo v).
Q' = Q^Q \times 2^Q
Stan początkowy, to krotka wszystkich stanów automatu i stan poczatkowy. q_0' = id \times \{ q_0 \}
Po zrobieniu kroku, mamy w krotce stany po wczytaniu kolejnej litery, i stany osiągalne po następnej literze (suma po obecnych stanach, stanów osiągalnych):
Zdefiniujmy:
\hat \delta( q, w ) =\hat \delta^w( q )
\delta'( (\hat \delta^w,R) , a ) = \hat \delta^{wa} \times \{ q \in Q |\exists_{a \in \Sigma}\; \exists_{ q_s \in R }\; \delta(q_s,a) = q \}
Stan (\hat \delta^w, R) jest akceptujący, jeśli istnieje stan osiągalny, dla którego funkcja zwróci stan akceptujący w A.
F = \{(\hat \delta^w,R) \in Q'| \hat \delta^w( R ) \cap F \neq \emptyset \}