snippetMajor
How to show that a "reversed" regular language is regular
Viewed 0 times
showregularreversedlanguagethathow
Problem
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."
"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."
Solution
So given a regular language $L$, we know (essentially by definition) that it is accepted by some finite automaton, 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. Then, 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}$.
Context
StackExchange Computer Science Q#3251, answer score: 39
Revisions (0)
No revisions yet.