Reversal (FSA)

Reversal (as the name implies) involving swapping states and transitions in a FSA, such that it accepts the reverse of a language. The procedure for producing a minimally equivalent DFA (from an NFA) requires reversal.

The reverse can be either a DFA or an NFA.

If $A$ has more than one accept state, $A_{rev}$ is guaranteed to become a NFA. Else, it can be a DFA (if $A$ was originally a DFA).

Procedure §

Let $A=(Q,\Sigma ,q_0,\delta ,F)$ be an finite state automata. To reverse $A$ (to produce $A_{rev}$) , we:

1. Check if $A$ has only one accept state, $F=\{q\}$. If it does, do nothing. If $F$ has more than one accept state, create a new state $q$ and connect all previous accept states to $q$ via epsilon transitions That is, for each state in $F$, add an $ϵ$-transition from that state to $q$. Then, make this $q$ the only accept state.
2. Reverse every transition. That is, if we had $\delta (q_{old},a)=q$, it now becomes $\delta (q,a)=q_{old}$.
3. Finally, make $q$ the initial state and make the initial state $q_0$ the accept state. I.e. swap the accept and initial states.

%%🖋 Edit in Excalidraw, and the dark exported image%%