Łatwo zauważyć, że możemy bez problemu rozpoznać język $L_p'$, który działa dokładnie tak samo, z taką różnicą, że wczytujemy słowa od lewej (od **najbardziej** znaczącego bitu).
Widzimy, że $L_p' = \{ w^R | w \in L_p \}$ i skorzystamy z tego, że NDFA się łatwo odwracają. Pokażę teraz krótko konstrukcję automatu rozpoznającego odwrócony język. \\
Niech $A = \langle \Sigma, Q, q_0, F, \delta \rangle$, to $A^R = \langle \Sigma, Q \cup \{q_z\}, q_z, \{q_0\}, \delta' \}$. Idea konstrukcji jest taka:
  * $q_z$ jest dodatkowym stanem, od którego będziemy startować
  * od $q_z$ idą epsilon-przejścia do każdego stanu akceptującego automatu $A$ 
  * potem łazimy po stanach $A$ przy czym po odwróconych krawędziach
  * stanem akceptującym jest $q_0$
Formalniej, 
  * $\delta'(q_z, \epsilon, q) \Leftarrow q \in F$
  * $\delta'(q, a, q') \Leftarrow \delta(q', a, q)$
Innymi słowy, jesteśmy w stanie rozpoznać odwrócony język używając jednego stanu więcej. \\
No dobrze, uzbrojeni w tą wiedzę, możemy krótko opisać automat z zadania. Nietrudno skonstruować NDFA (a nawet DFA) rozpoznający $L_p'$. Niech $Q = \{q_0\} \cup \{0, \ldots, p-1\}$, krawędzie zaś są postaci: $\delta(q_0, a) = a \wedge \delta(r, a) = (2r + a) mod\ p$, gdzie oczywiście $a \in \{0,1\}$. Automat na $p+1$ stanów, także ten rozpoznający odwrócony - $p+2$. Koniec.