Ł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.