NP-Complete Problem: Determine if NFAs A and B Accept Same Language

[complexity9]

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!

 

[-Job-]

Consider an instance of SAT - you're given a specific boolean formula and are asked whether a variable assignment exists that evaluates to true.

How many such possible assignments are there, for a specific SAT instance? You might say that each SAT instance itself has a language: the language composed of all distinct variable assignments that evaluate to true.

Additionally, under this interpretation, all unsatisfiable SAT instances have the same language - an empty language - given that there are no assignments that evaluate to true.

Do you see a way to solve SAT by using a solution to the problem of determining whether two NFAs have the same language?