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!