Non-deterministic finite automaton

Stub grade: A**

This page is a stub

This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:

Needs a "see also" section before demotion

Definition: Relative to DFAs

NFAs have an almost-identical to to that of a DFA the only difference is in the "transition function", which in DFAs is of the form [ilmath]\delta_{\text{DFA} }:Q\times\Sigma\rightarrow Q[/ilmath] - ordered pairs of a state and a letter of the alphabet the machine is over which are mapped to other states - is instead of the form [ilmath]\delta_{\text{NFA} }:Q\times\Sigma\rightarrow[/ilmath][ilmath]\mathcal{P}(Q)[/ilmath], which is to say it maps pairs of a state and an symbol of the input alphabet to a set of states instead.

Definition

A non-deterministic-finite-automaton is a tuple of 4-items, [ilmath]A[/ilmath], for:

• [ilmath]A:\eq(Q,\Sigma,\delta,q_0)[/ilmath] where
  • [ilmath]Q[/ilmath] is a finite set of states - just as in a DFA
  • [ilmath]\Sigma[/ilmath] is the alphabet of the NFA, a finite set of symbols which appear in "strings" - just as in a DFA
  • [ilmath]\delta:Q\times\Sigma\rightarrow[/ilmath][ilmath]\mathcal{P} [/ilmath][ilmath](Q)[/ilmath] is called the "transition function"
    • This is differs from DFAs as described above, notice it maps [ilmath](\text{state},\text{symbol})[/ilmath] to a set of states, this is the "non-deterministic" part.
    • Also, unlike a DFA, [ilmath]\delta[/ilmath] may map to the empty set, [ilmath]\emptyset[/ilmath], any states which may trap an NFA is called a "dead configuration"
  • [ilmath]q_0\in Q[/ilmath] - the "initial state" or "starting state" of the automaton
• In an "acceptor" type - as with a DFA - there's an addition item, [ilmath]F[/ilmath], with [ilmath]F\subseteq Q[/ilmath], the "final" or "accepting" states.
  • Unlike a DFA (which can only be in one state) an NFA can be in several "at the same time" or may just take different paths on each run, as such given a string if it may be in any state which is accepting then the NFA itself is "accepting".

There are two "defined" types of automaton, of which NFA is a kind, just as for DFAs:

1. Acceptor type automaton and
2. Transducer type automaton

NFAs are rarely encountered "in practice" (I've never seen code to actually run an NFA, just code to turn it into a DFA), so it doesn't really right discussing these types.

A discussion can be found on the DFA's page "definition" section - I defer to that here.

We discuss only "acceptor type" below as information on accepting states is used when transforming an NFA acceptor into a DFA "acceptor".

Non-deterministic finite acceptor automaton

As with DFAs, it's either a 5-tuple:

• [ilmath]A:\eq(Q,\Sigma,\delta,q_0,F)[/ilmath] (or perhaps an ordered pair, [ilmath]A:\eq(A',F)[/ilmath] for [ilmath]A'[/ilmath] an NFA as defined above) with the terms exactly as above except for an additional item:
  • [ilmath]F\subseteq Q[/ilmath] which is a set of "accepting" states or "final states".