Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, I'm really stuck on how to prove the following:

Given that $L$ is a language and $L'$ is a set such that $L' = \{w \mid w' \in L\}$ where $w$ is the reverse of $w'$, e.g., if $w = a a b$ then $w' = b a a$ (i.e. you flip the string around), prove that $L$ is NFA-recognizable if and only if $L'$ is NFA-recognizable

share|cite|improve this question
See also this question on Computer Science. – Raphael Oct 2 '12 at 18:13
up vote 0 down vote accepted

You can more or less 'reverse' the NFA, but we have to take care of $\epsilon$-transitions (where $\epsilon$ denotes the empty word), therefore assume that a NFA $A = (\Sigma, Q, \delta, S, F)$ without $\epsilon$-transitions is given with $L = L(A)$, that is $A$ recognizes $L$. Here

  • $\Sigma$ is the alphabet
  • $Q$ denotes the set of states
  • $\delta\colon Q \times \Sigma \to \mathscr P(Q)$ is the transition function.
  • $S \subseteq Q$ is the set of starting states
  • $F \subseteq Q$ is the set of final states

Now we define an automaton $A' = (\Sigma, Q, \delta', S', F')$ by - just reversing the transitions:

  • $S' := F$, $F' := S$
  • $\delta'(q, a) := \{q' \in Q \mid q \in \delta(q', a)\}$

We will prove $L' = L(A')$ now:

$\subseteq$: Let $w = a_1 \ldots a_n \in L'$ be given, then $a_n \ldots a_1 \in L$, hence there is a sequence $q_0, \ldots, q_n$ of elements of $Q$ such that $q_0 \in S$, $q_n \in F$ and $q_{i+1} \in \delta(q_i, a_{n-i})$ for $0 \le i \le n-1$. But then $q_n, \ldots, q_0$ is a sequence of states such that $q_n \in S'$, $q_0 \in F'$ and $q_{n-i-1} \in \delta'(q_{n-i}, a_{i+1})$ by definition. Hence $A'$ recognizes $w$.

$\supseteq$: Let $w = a_1 \ldots a_n \in L(A')$, then there is a sequence $q_0, \ldots, q_n$ of states with $q_{i+1} \in \delta'(q_i, a_{i+1})$ and $q_0 \in S'$, $q_n \in F'$. This means by definition $q_n \in S$, $q_0 \in F$ and $q_i \in \delta(q_{i+1}, a_{i+1})$. This proves $a_n \ldots a_1 = w' \in L(A) = L$, hence $w \in L'$.

So if $L$ is NFA-recognizable, $L'$ is also. On the other side, if $L'$ is recognizable, then $L''$ is (by what we have proved), but $L = L''$, so we are done.

share|cite|improve this answer

Reverse all transitions. Add a fresh starting state. Connect them to the old accepting state with $\varepsilon$-transitions. The old starting state now becomes accepting.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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