How to show that a "reversed" regular language is regular

Question Detail: 

I'm stuck on the following question:

"Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{R}$ is also accepted by some finite; $L^{R}$ consists of all words of $L$ reversed."

Asked By : Cat

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3251

Answered By : Luke Mathieson

I think the problem here is that not being a CS student, you're just missing some practical experience with finite automata. I'll sketch out the idea for reversing a regular language and try to add some pictures later when I'm not using a tablet!

So given a regular language $L$, we know (essentially by definition) that it is accepted by some finite automata, so there's a finite set of states with appropriate transitions that take us from the starting state to the accepting state if and only if the input is a string in $L$. We can even insist that there's only one accepting state, to simplify things. The to accept the reverse language all we need to do is reverse the direction of the transitions, change the start state to an accept state, and the accept state to the start state. Then we have a machine that is "backwards" compared to the original, and accepts the language $L^{R}$.