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