How to Trace Path in Proof that Regular Languages are Closed Under Reversal

Question

I'm self studying automata theory and I need help with proving that regular languages are closed under reversal.

I have a basic proof, but am unsure about last statement in my proof. Is this sufficient? Could you help me explain why it works? Is it rigorous enough?

Problem: For any string $w=w_1w_2\cdots w_n$, the reverse of $w$, written $w^\mathcal{R}$, is the string $w$ in reverse order, $w_n\cdots w_2w_1$. For any language $A$, let $A^\mathcal{R} = \{w^\mathcal{R} | w \in A \}$. Show that if $A$ is regular, so is $A^\mathcal{R}$.

Proof: Let $N = (Q, \Sigma, \delta, q_0, F)$ be an DFA recognizing $A$. We construct an NFA $M = (Q', \Sigma, \delta', q_0', F')$. Let $Q' = \mathcal{P}(Q) \cup \{q'_0\}$. For this NFA, $q'_0$ is a new start state. Let $F' = \{q_0\}$, the start state of $N$.

Define $\delta'$ so that for any $q \in Q'$ and any $a \in \Sigma_\epsilon$, \begin{equation*} \delta'(q,a) = \begin{cases} F & q = q'_0, a = \epsilon\\ q'_0 & q = q'_0, a \neq \epsilon\\ \{ x | x \in Q\ and\ \delta(x,a) = q \}&q \neq q'_0 \end{cases} \end{equation*}

For any $w \in \Sigma^*$, there is a path from $q_0$ to $q_{acc} \in F$ in $N$ if there is a path following $w^\mathcal{R}$ from $q'_0$ to $q_0$. Therefore, $w^\mathcal{R} \in A^\mathcal{R}$ iff $w \in A$.

Answer 1

Whether a proof is sufficiently detailed is in part a question of taste. Your last statement is very general and with little detail. A more detailed argumentation could be like this:

• Let the path from $q_0$ to $q_{acc}$ go through the sequence of states $q_0 -> q_1 -> ... -> q_{n-2} -> q_{n-1} -> q_{acc}$.
• Transition $q_{n-1} -> q_{acc}$ reads the letter $w[n]$ (w has length n) which is equal to $w^R[1]$. According to the third clause in the definition of $\delta'$ there is a transition $\delta'(q_{acc},w[1]) = q_{n-1}$ which can start a path for $w^R$ in M.
• Now you can continue by induction or by simply stating that the same is true for every transition in the path for $w$. At any rate, since your construction is on the level of transitions, your argumentation should go down to the level of transitions somewhere and not stop at the level of paths.