An NFA (nondeterministic finite automaton) is acyclic if there is no path from a state to itself.(adsbygoogle = window.adsbygoogle || []).push({});

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# NP-Complete question

**Physics Forums | Science Articles, Homework Help, Discussion**