# How to show that a “reversed” regular language is regular

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

-
Well, did you try constructing an automaton that would accept $L^R$? It may help to draw an example. – Gilles Aug 18 '12 at 16:25
Thank you for your reply. I'm not sure how to do this. I'm sure any L^R would be accepted by some language because it is constructed out of the same 'alphabet' and so will also be a regular language. I'm not sure how to go about proving it though, or how to draw an example. – Cat Aug 18 '12 at 16:40
Welcome! For such basic questions that smack of homework assignments, we like if the question contains (significant) prior work of the questioner. You certainly have tried something you can share (which we can then use to guide you in the correct direction). If not, I suggest you recheck your definitions and heed Gilles' advice. – Raphael Aug 18 '12 at 17:13
@Victoria "it is constructed out of the same 'alphabet' and so will also be a regular language" -- oh, nonono. $\{a^nb^ma^o \mid n,m,o \in \mathbb{N} \}$, $\{a^nb^ma^n \mid n,m \in \mathbb{N}\}$ and $\{a^nb^na^n \mid n \in \mathbb{N}\}$ are all defined over the same alphabet but fall into very different language classes. – Raphael Aug 18 '12 at 17:13
The other question at the end of the chapter asks me to prove that no finite automaton can accept all palindromes over a given alphabet. I think that the proof for this hinges on the fact that there are an infinite number of states if we are considering all possible palindromes (no length limit), whereas the machine is a finite state machine. – Cat Aug 18 '12 at 20:07
show 8 more comments

## 3 Answers

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}$.

-
 Thank you so much Luke - I think I understand what you've said. You're spot on - I have absolutely no practical experience with finite automata! I'd 'up vote' you but I don't have enough points, apparently. Sorry about that! – Cat Aug 19 '12 at 15:01 That's fine, you should be able to "accept" answers you like (there should be a tick mark below the vote buttons). Also Saadtaame's more formal answer is an excellent next step after mine. – Luke Mathieson Aug 20 '12 at 0:36 To assume there is only one accepting state we either must allow $\epsilon$-transitions, or have $\epsilon\notin L$. Both are not real restrictions, I know, so the answer is OK. – Hendrik Jan Jan 2 at 0:46

You have to show that you can always construct a finite automaton that accepts strings in $L^R$ given a finite automaton that accepts strings in $L$. Here is a procedure to do that.

1. Reverse all the links in the automaton
2. Add a new state (call it $q_s$)
3. Draw a link labeled with $\epsilon$ from state $q_s$ to every final state
4. Turn all the final states into normal states
5. Turn the initial state into a final state
6. Make $q_s$ the initial state

Let's formalize all of this; we start by stating the theorem.

Theorem. If $L$ is a regular language, then so is $L^{R}$.

Let $A = (Q_A, \Sigma_A, \delta_A, q_A, F_A)$ be a NFA and let $L = L(A)$. The $\epsilon$-NFA $A^{R}$ defined below accepts the language $L^{R}$.

1. $A^{R} = (Q_A \cup \{q_s\}, \Sigma_A, \delta_{A^R}, q_s, \{q_A\})$ and $q_s \notin Q_A$
2. $p \in \delta_A(q, a) \iff q \in \delta_{A^R}(p, a)$, where $a \in \Sigma_A$ and $q, p \in Q_A$
3. $\epsilon-closure(q_s) = F_A$

Proof. First, we prove the following statement: $\exists$ a path from $q$ to $p$ in $A$ labeled with $w$ if and only if $\exists$ a path from $p$ to $q$ in $A^R$ labeled with $w^R$ (the reverse of $w$) for $q, p \in Q_A$. The proof is by induction on the length of $w$.

1. Base case: $|w| = 1$
Holds by definition of $\delta_{A^R}$
2. Induction: assume the statement holds for words of length $\lt n$ and let $|w| = n$ and $w = xa$
Let $p \in \delta_A^*(q, w) = \delta_A^*(q, xa)$
We know that $\delta_A^*(q, xa) = \cup_{p'}\delta_A(p', a)$ $\forall p' \in \delta_A^*(q, x)$
$x$ and $a$ are words of fewer than $n$ symbols. By the induction hypothesis, $p' \in \delta_{A^R}(p, a)$ and $q \in \delta_{A^R}^*(p', x^R)$. This implies that $q \in \delta_{A^R}^*(p, ax^R) \iff p \in \delta_A^*(q, xa)$.

Letting $q = q_A$ and $p = s$ for some $s \in F_A$ and substituting $w^R$ for $x^Ra$ guarantees that $p \in \delta_{A^R}^*(s, w^R)$ $\forall s \in F_A$. Since there is a path labeled with $\epsilon$ from $q_s$ to every state in $F_A$ (3. in the definition of $A^R$) and a path from every state in $F_A$ to the state $q_A$ labeled with $w^R$, then there is a path labeled with $\epsilon w^R = w^R$ from $q_s$ to $q_A$. This proves the theorem.

Notice that this proves that $(L^R)^R = L$ as well.

Please edit if there are any formatting errors or any flaws in my proof.

-

To add to the automata-based transformations described above, you can also prove that regular languages are closed under reversal by showing how to convert a regular expression for $L$ into a regular expression for $L^R$. To do so, we'll define a function $REV$ on regular expressions that accepts as input a regular expression $R$ for some language $L$, then produces a regular expression $R'$ for the language $L^R$. This is defined inductively on the structure of regular expressions:

1. $REV(\epsilon) = \epsilon$
2. $REV(\emptyset) = \emptyset$
3. $REV(a) = a$ for any $a \in \Sigma$
4. $REV(R_1 R_2) = REV(R_2) REV(R_1)$
5. $REV(R_1 | R_2) = REV(R_1) | REV(R_2)$
6. $REV(R*) = REV(R)*$
7. $REV((R)) = (REV(R))$

You can formally prove this construction correct as an exercise.

Hope this helps!

-