HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMajor

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

Submitted by: @import:stackexchange-cs··
0
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."

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.