Pokazać, że jeśli L\subseteq \Sigma^* jest regularny, to Lustro(L)=\{wv^R\in \Sigma^* : wv\in L\} też jest.
Niech A=(Q_A, \Sigma, \delta_A, q^A_0, F_A) będzie DFA takim, że, L(A)=L. Skonstruujemy sobie NFA B rozpoznający Lustro(L).
Q_B=Q_A\times 2^{Q_A}\times\{0,1\} - oznacza to trójki złożone ze stanu A, ze stanu odwróconego A (podzbioru Q_A) i jednej flagi. Odwrócony A to NFA powstały przez odwrócenie strzałek (funkcja przejścia staje się relacją). Flagę będziemy czytać jako „czy przekroczyłeś już granicę w|v”.
q^B_0=\langle q^A_0, F_A, 0\rangle
Zasada działania jest taka, że czytamy literki i przesuwamy się po lewej współrzędnej do pewnego miejsca (czyli wczytujemy w), w pewnym momencie przełączamy flagę (tylko raz; odpowiedni moment dostajemy od tego… jak go JMA nazywa? adwokata? sędziego? wyroczni?) i zaczynamy jechać po drugiej współrzędnej, czytając literki w odwrotnej kolejności niż by to było w L (co odpowiada v^R). W momencie, gdy nasze współrzędne się spotkają (lewa będzie należeć do drugiej), mamy stan akceptujący.
Formalniej:
\delta_B(\langle q, R, 0 \rangle, a) = \{\langle\delta_A(q,a),R,0\rangle\}\cup \{\langle q, \{p\in Q_A : \delta_A(p,a)\in R\}, 1\rangle\},
\delta_B(\langle q, R, 1 \rangle, a) = \{\langle q, \{p\in Q_A : \delta_A(p,a)\in R\}, 1\rangle\},
F_B = \{\langle q, R, \_\rangle : q \in R\}.