3
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ Thanks for the more specific question! Well, usually, if you have to ask "is this obvious?" that's potentially a tip it might be worth spelling out the reasoning why it's true (as asking the question suggests that perhaps some readers might not find it obvious and this will benefit from the more detailed explanation). $\endgroup$ – D.W. Jun 13 '16 at 3:42
  • 1
    $\begingroup$ Your NFA has loops on $q_0'$ for each letter of the alphabet; this actually allows it to accept any word of the form $vw^R$ with $v\in\Sigma^*, w\in A$. Removing the loops gives you the correct automaton (remember that NFAs have a transition relation, in particular not every state needs to have an $a$-successor for all $a$). $\endgroup$ – Klaus Draeger Jun 13 '16 at 14:14
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thanks Peter! This makes a lot of sense, I'll include details at the transition level in the proof. $\endgroup$ – Srinivas Vasudevan Jun 13 '16 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.