Twierdzenie 4.11 z Hopcrofta
Jeśli L jest regularny, to L^R = \lbrace w : w^R \in L \rbrace też jest regularny.
(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.
E \in \{ \epsilon, \emptyset, a \}, gdzie a \in \Sigma. Wtedy E^R = E, bo \epsilon^R = \epsilon, \emptyset^R = \emptyset, a^R = a.
Mamy trzy przypadki (trzeba je udowodnić, korzystając z założenia indukcyjnego, że prostsze wyrażenia regularne są już dobrze odwrócone):
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.