2 threads accepted at the same time Assuming we have an automaton that simultaneously accepts a string on two paths. Would this mean that the construction of the NFA might be faulty?  In other words; at the end of any string over any alphabet, does the NFA have to end up accepting one single path only? Or could it accept several at the same time?
A NFA is defined so that if there is any accepting path for the given input string, it will accept. It's perfectly allowable for an NFA to have two paths to acceptance. If no path accepts, then the NFA doesn't accept.