# How do you prove that two languages are equivalent?

How can you show that the Language accepted by an NFA and the reverse NFA is the same?

For a language $L$, there is an $L^R=\{ w^R \mid w \in L\}$

Let's say that $w^R$ is the string obtained by reversing the string $w$.

I know that it involves using induction on the length of the input, but I would really appreciate some help.

• I don't understand the statement; as I read it, it is trivially false as in general $L \neq L^R$. – Raphael Oct 2 '12 at 20:02
• @codebrah Do you want to prove the statement for some particular NFA or for any NFA? That's not true in general. – saadtaame Oct 2 '12 at 22:12
• The way I get this question is, "how do I prove that two languages $A$ and $B$ are equal". The answer: show $A\subseteq B$ as well as $B\subseteq A$. – Ran G. Oct 2 '12 at 22:12
• As others commented, the question does not make sense as is. Yuval Filmus answered one of the questions which you might have wanted to ask: “How do we prove that the class of languages accepted by an NFA is the same as the class of languages whose reversal is accepted by an NFA?” – Tsuyoshi Ito Oct 3 '12 at 22:53

There's an algorithm for this. Construct a DFA from you NFA, construct the reverse DFA, and check whether the two DFAs accept the same language (for example, you could construct the DFA for the symmetric difference and see if it accepts anything). If you want a more serious answer, you'll need to tell us more about your $L$.