An NFA (nondeterministic finite automaton) is acyclic if there is no path from a state to itself.
Decision problem: Given two acyclic NFAs A and B, does L(A)=L(B), i.e. does A accept the same language as B.
Show that the above decision problem is NP-Complete.
I am unable to show that it is either NP or NP-hard, but was told that we may use a reduction from SAT to show NP-Hardness. Any help would be appreciated, I have been thinking about this for a while and don't know where to start!