1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don't understand the statement; as I read it, it is trivially false as in general $L \neq L^R$. $\endgroup$ – Raphael♦ Oct 2 '12 at 20:02
  • $\begingroup$ @codebrah Do you want to prove the statement for some particular NFA or for any NFA? That's not true in general. $\endgroup$ – mrk Oct 2 '12 at 22:12
  • $\begingroup$ 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$. $\endgroup$ – Ran G. Oct 2 '12 at 22:12
  • $\begingroup$ 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?” $\endgroup$ – Tsuyoshi Ito Oct 3 '12 at 22:53
5
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Another way to check the equivalence of two DFAs is just to minimize them and check they are isomorphic. Isomorphism check runs in O(n) and minimization leads to a canonical normal form. $\endgroup$ – antti.huima Oct 3 '12 at 8:28
  • $\begingroup$ @antti.huima This strategy includes determinising which can cause exponential blow-up. Therefore, it might not be a feasible strategy (if you need only a single proof). $\endgroup$ – Raphael♦ Oct 3 '12 at 8:47
  • 1
    $\begingroup$ @Raphael So? DFA isomorphism is not the same problem as NFA isomorphism. DFA isomorphism is easy because all outgoing arcs have unique labels, because there are no e-transitions. Every outgoing transition from a state has a distinct label, which makes isomorphism check for DFAs simple. If you would read my answer more carefully you would obviously note that I wrote "another way to check the equivalence of two DFAs..." $\endgroup$ – antti.huima Oct 3 '12 at 14:35
  • $\begingroup$ @antti.huima Right, my mistake. No need to be snappy... I'll edit the comment and delete your answer as well as this one later. $\endgroup$ – Raphael♦ Oct 3 '12 at 15:30
  • $\begingroup$ Checking for equality of two regular expressions (= representations for regular languages) in general is a computationally complex process, so exponential blow-up might not mean that the solution is suboptimal. $\endgroup$ – antti.huima Oct 4 '12 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.