Hi, I was wondering if anyone knew much about non-deterministic finite automata (NFA's)? I am working on a grad project and keep running into a question I can't answer. Basically, when an NFA is "reading" input from it's alphabet, it is moving through a series of states. Because, this is an NFA, multiple branches or threads (actually, copies of itself) can all be running simultaneously checking all possible states given the input. If at least one of those branches is in accept state when the input is done, then the string is accepted by the NFA and thus part of its language. However, this being an NFA, some branches can terminate prematurely. Some states will have no where to go on a give letter of the input, they will just freeze and that branch will die. My question is if that is allowed to happen for all branches? Can all threads of the NFA just freeze or halt before the input is read completely? In that case all the states would be unable to transition to another state given the next input letter. Can that happen to an NFA? If it does, would the input simply not be accepted as part of the language defined by the NFA?
