====== JFiZO - Zadanie 09.019 ======

//Twierdzenie 4.11 z Hopcrofta//

Jeśli $L$ jest regularny, to $L^R = \lbrace w : w^R \in L \rbrace$ też jest regularny.

====== Rozwiązanie ======

//(indukcja względem struktury wyrażenia regularnego)// Skoro $L$ jest regularny, to istnieje wyrażenie regularne $E$ takie, że $L(E) = L$. Pokażemy, że istnieje wyrażenie regularne $E^R$ takie, że $L(E^R) = \left(L(E)\right)^R$.

====== Podstawa indukcji ======
$E \in \{ \epsilon, \emptyset, a \}$, gdzie $a \in \Sigma$. Wtedy $E^R = E$, bo $\epsilon^R = \epsilon, \emptyset^R = \emptyset, a^R = a$.

====== Krok indukcyjny ======
Mamy trzy przypadki (trzeba je udowodnić, korzystając z założenia indukcyjnego, że prostsze wyrażenia regularne są już dobrze odwrócone):
  * $E = E_1 + E_2$. Wtedy $E^R = E_1^R + E_2^R$.
  * $E = E_1E_2$. Wtedy $E^R = E_2^RE_1^R$.
  * $E = E_1^*$. Wtedy $E^R = (E_1^R)^*$.
====== Rozwiązanie alternatywne ======  
Wiemy, że jeżeli istnieje NDFA $A$ rozpoznający dany jezyk,\\
 to możemy skonstuować DFA $A'$ taki, że $L(A)=L(A')$.\\

Naszym automatem rozpoznającym język $L^R(A')$ będzie NDFA $B$.\\
$A' = (\Sigma, Q, S, F, \delta )$\\
$B = (\Sigma, Q, S_B, F_B, \delta_B )$\\
$S_B = q_0 $\\
$F_B = \{ S \} $\\
$\delta_B = \{ (q_2,a,{q_1}) : (q_1,a,q_2) \in \delta \} \cup \{ (q_0,\epsilon,F)\}$\\

Wystarczy pokazać, że:\\
$w \in L^R(A') <=> w$ jest rozpoznawany przez $B$\\

($\Rightarrow$)
Weźmy dowolne słowo $w$ z $L(A')$. Czyli słowo $w^R \in L^R(A')$.\\
Dla słowa $w$, w $A'$ istnieje taka ścieżka stanów $q_0 \rightarrow q_1 \rightarrow ...  \rightarrow q_n$, że $q_0 \in S \wedge q_n \in F$.\\
Czyli z definicji $B$ wiemy, że istnieje tam ścieżka stanów $q_n \rightarrow q_{n-1} \rightarrow ...  \rightarrow q_0$, że $q_n \in S_B \wedge q_0 \in F_B$.\\
Widać, że to ścieżka dla słowa $w^R$, czyli jest ono rozpoznawane przez automat.

($\Leftarrow$)
Weźmy dowolne słowo $v$ akceptowane przez automat $B$. To znaczy, że istnieje w $B$ ścieżka stanów $q_0 \rightarrow q_1 \rightarrow ...  \rightarrow q_n$, że $q_0 \in S_B \wedge q_n \in F_B$.\\
Z definicji automatu $B$ wiemy, że musi istnieć ścieżka stanów $q_n \rightarrow q_{n-1} \rightarrow ...  \rightarrow q_0$, że $q_n \in S \wedge q_0 \in F$ w automacie $A'$.\\
Widzimy, że to ścieżka dla słowa $v^R$. Czyli $v^R \in L(A')$. Czyli $v \in L^R(A')$.



Ścieżka, to taki ciąg $\{q_i, a_i\}$, że $δ(q_i, a_i) = q_{i+1}$ oraz $\hat{δ}(q_0, w ) \in F$, dla każdego $q_0 \in S$.