Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
See also this question on Computer Science. –  Raphael Oct 2 '12 at 18:13
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.