====== JFiZO - Zadanie 11.006 ======
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\}$.