<Q,I,delta,q0,F>; where:
Q is a finite set of states;
I is a finite set of input symbols;
delta is the, possibly partial, transition function delta:Q X I->P(Q), where P(Q) is the set of all subsets of Q
q0 element of Q is called the initial state;
F contained in Q is called the set of final states
The above definition states that a nondeterministic finite automaton can exhibit several different transition sequences for a given state and a given input.
An input string is accepted by a nondeterministic finite automaton if and only if at least one of the possible transition sequences, defined by the input, leads to a final state.
As language recognizer devices, nondeterministic automata are not more powerful than their deterministic counterpart, indeed they accept the same class of languages, that is to say they are equivalent. However, they are very often more convenient to use. In many cases, the most direct formalization of a problem is in terms of a nondeterministic automaton.
Back to Index