Computability Theory - NFA Question

[nova-CS]

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?

[erikduop]

Classical computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930's, and includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, subrecursive hierarchy classifications, computable structures, and complexity theory relating to the preceding.

There are still very many open questions, both of a technical nature, concerning extensions of what is known about the Turing degrees and their context in the enumeration degrees, and similar questions for other natural reducibility degree structures, and less well-defined questions concerning the scope of relevance of such work.

______________

VLC Player

Edited November 30, 2010 by erikduop

[glitch]

Im not sure exactly what erikduop said, but my understanding is that any NFA will not accept a string that is prematurely terminated. The advantage of NFA is that there are several paths which can be taken, allowing us to choose the right path in retrospect. If all paths terminate without reaching a final state, the string will not be accepted as part of the language.

[khaled]

NFA is a graph where vertices define connection between alphabets that can come in order to form a word in a dictionary ...

 

NFA can be formed from a Regular Expression ...

 

NFA can be transformed into Lexical Analyzer, directly or throught DFA ...

 

Good luck,