# Non-deterministic finite automaton

**Stub grade: A****

## Contents

## 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*"^{[1]}

- This is differs from DFAs as described above, notice it maps [ilmath](\text{state},\text{symbol})[/ilmath] to a
- [ilmath]q_0\in Q[/ilmath] - the "initial state" or "starting state" of the automaton

- [ilmath]Q[/ilmath] is a finite set of states -
- 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.

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

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".

## Notes

## References

- ↑ Like with this page: Formal Languages and Automata, Fourth edition, Peter Linz