Automata Theory Part 2

Three Kinds of Finite Automata:

Deterministic Finite Automata (DFA)
Each state has a transition for every symbol in the alphabet.

Nondeterministic Finite Automata (NDFA)
States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from q₀ to a state in F labeled with the input word. If a transition is undefined, so that the automaton does not know how to keep on reading the input, the word is rejected.


Nondeterministic Finite Automata, with ε Transitions
Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with ε, then the NFA can be in any of the states reached by the ε-transitions, directly or through other states with ε-transitions. The set of states that can be reached by this method from a state q, is called the ε-closure of q.