Below is a problem from Dexter C Kozen’s Automata and Computability followed by my attempt at a solution. Please provide feedback on my proof. Are there any errors/leaps in logic? If having access to the text would be helpful, then I am happy to post a link, assuming that doing so is permissible on this form.

$$$$

$$$$

**My attempt:**

$T$ is regular if and only if there exists a NFA accepting $T$. Let $N=(Q,∑,Δ,S,F)$ such that $L(N)=T.$

I will show that there exists a NFA accepting $T$ if and only if there exist a NFA $N_{R}=(Q,∑,Δ_R,S_R,F_R)$ such that $L(N_R)=revT.$

Define: $Δ_R(q,a)={p in Q : q in Δ(p,a)}$, $S_R=F$, $F_R=S$

**Lemma 1**: if $A⊆Q, $ then $hat{Δ}_R(hat{Δ}(A,x),rev(x))=A$ for all $x in ∑^✱$.

Base Cases:

$$hat{Δ}_R(hat{Δ}(A,ε),ε)=hat{Δ}_R(A,ε)=A$$ by Kozen (6.1). So, equality holds for the empty string.

$$hat{Δ}_R(hat{Δ}(A,a),rev(a))=$$$$bigcup_{qinhat{Δ}(A,a) } {p in Q : q in Δ(p,a) }=$$

$${p in Q : Δ(p,a) ∩ hat{Δ}(A,a) not =∅ }=A$$

by Kozen (6.2), the fact that $rev(a)=a$, and the definition of $Δ_R$.

Inductive Step:

Assume $hat{Δ}_R(hat{Δ}(A,x),rev(x))=A$.

$$hat{Δ}_R(hat{Δ}(A,xa),rev(xa))=hat{Δ}_R(hat{Δ}(A,xa),arev(x))=$$

by definition of string reversal in problem statement.

$$hat{Δ}_R(bigcup_{qinhat{Δ}(A,x)}Δ(q,a), arev(x)) $$

by Kozen definition (6.2) page 33

$$bigcup_{qinhat{Δ}(A,x)}hat{Δ}_R(Δ(q,a), arev(x)) $$

by Kozen Lemma 6.2 page 34

$$bigcup_{qinhat{Δ}(A,x)}hat{Δ}_R(hat{Δ}_R(Δ(q,a), a),rev(x))= $$

by Kozen Lemma 6.1

$$hat{Δ}_R(hat{Δ}_R(hat{Δ}(A,xa), a),rev(x))= $$

by Kozen Lemma 6.2

$$hat{Δ}_R(hat{Δ}_R(hat{Δ}(hat{Δ}(A,x),a), rev(a)),rev(x))= $$

by Kozen Lemma 6.1 and by the fact that $rev(a)=a$

$$hat{Δ}_R(hat{Δ}(A,x),rev(x))= $$

by the base case for a single character

$$A$$ by assumption.

**Lemma 2**: $hat{Δ}(A ∩ B,x)= hat{Δ}(A,x) ∩ hat{Δ}(B,x)$

Base Case:

$hat{Δ}(A ∩ B,ε)=A ∩ B= hat{Δ}(A,ε) ∩ hat{Δ}(B,ε)$ by definition (6.1) kozen

Inductive step:

Assume $hat{Δ}(A ∩ B,x)= hat{Δ}(A,x) ∩ hat{Δ}(B,x)$

$$hat{Δ}(A ∩ B,xa)=bigcup_{qinhat{Δ}(A∩ B,x)}Δ(q,a)=$$

by definition (6.2) kozen

$$bigcup_{qin(hat{Δ}(A,x)∩ hat{Δ}( B,x))}Δ(q,a)=$$

by assumption

$$bigcup_{qinhat{Δ}(A,x)}Δ(q,a)∩bigcup_{qinhat{Δ}(A,x)}Δ(q,a)=hat{Δ}(A,xa)∩hat{Δ}(B,xa)$$

by definition (6.2) kozen and basic set theory

Now I will use lemma 1 and lemma 2 to show $x in L(N)$ IFF $rev(x) in L(N_R)$

$x in L(N)$ IFF $hat{Δ}(S,x)∩F not = ∅$ IFF

$hat{Δ_R}(hat{Δ}(S,x)∩F,rev(x)) not = hat{Δ_R}(∅,rev(x)) $ IFF

$hat{Δ_R}(hat{Δ}(S,x),rev(x)) ∩hat{Δ_R}(F,rev(x)) not = ∅ $, by lemma 6.2, IFF

$S ∩hat{Δ_R}(F,rev(x)) not = ∅ $, by lemma 6.1, IFF

$F_R ∩hat{Δ_R}(S_R,rev(x))$, by definition of $F_R,S_R$, IFF

$rev(x) in L(N_R)$ $∎$