CMI2011-B-04a

Question

Let $\subseteq \{0,1\}^*$ Suppose $L$ is regular and there is a non-deterministic automaton $N$ which recognizes $L$. Define the reverse of the language $L$ to be the language $L^R = \{w \in \{0, 1\} | \text{ reverse}(w) \in L \}$ - here $reverse(w)$ denotes the string $w$ read in reverse. For example $reverse(0001) = 1000$.

1. Show that $L^R$ is regular, How can you use $N$ to construct an automata to recognize $L^R$.

Answer 1

first we will convert that nfa to dfa by subset construction algorithm .start with a DFA M for A, and build a NFA M0 for A^(R)as follows: reverse all the arrows of M, and designate the start state for M as the only accept state q acc for M’. Add a new start state q 0  for M0 and from q 0  , add epsilon-transitions to each state of M0 corresponding to accept states of M. It is easy to verify that for any w ∈ Σ ^(*) , there is a path following w from the state start  to an accept state in M iff there is a path following w^(R) from q 0 to q acc in M0 . It follows that w ∈ A iff w^(R) ∈ A^(R).

Answer 2

Steps:

1. Convert the NFA to a DFA using the subset construction algorithm. Let the resulting DFA be $D$.
2. To build an NFA $N'$ to accept $L^R$, we do the following:

•     Reverse the direction of all edges in the transition diagram. 
  That is, replace every transition $\delta(q_i, a) = q_j$, where $a \in \{0,1\}$, with  $\delta^R(q_j, a) = q_i$.
•     The original start state of $D$ becomes the new final state in $N'$.
• The final state(s) in $D$ become the new start state(s) in $N'$. If $|F| > 1$, add a new start state $q_0$ and add $\epsilon$-transitions from $q_0$ to all original final states in $D$.