3
$\begingroup$

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

  • 0
    See also [this question](http://cs.stackexchange.com/questions/3251/how-to-show-that-a-reversed-regular-language-is-regular) on [cs.SE].2012-10-02

2 Answers 2

4

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.

  • 0
    How do we take care of $\epsilon$ transitions when there are any in the original NFA?2017-01-24
6

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.