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 $\delta_{\text{DFA} }:Q\times\Sigma\rightarrow Q$ - 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 $\delta_{\text{NFA} }:Q\times\Sigma\rightarrow$$\mathcal{P}(Q)$, 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, $A$, for:

• $A:\eq(Q,\Sigma,\delta,q_0)$ where
  • $Q$ is a finite set of states - just as in a DFA
  • $\Sigma$ is the alphabet of the NFA, a finite set of symbols which appear in "strings" - just as in a DFA
  • $\delta:Q\times\Sigma\rightarrow$$\mathcal{P}$$(Q)$ is called the "transition function"
    • This is differs from DFAs as described above, notice it maps $(\text{state},\text{symbol})$ to a set of states, this is the "non-deterministic" part.
    • Also, unlike a DFA, $\delta$ may map to the empty set, $\emptyset$, any states which may trap an NFA is called a "dead configuration"
  • $q_0\in Q$ - the "initial state" or "starting state" of the automaton
• In an "acceptor" type - as with a DFA - there's an addition item, $F$, with $F\subseteq Q$, 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:

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