Nondeterministic finite state machine

From Free net encyclopedia

In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states.

Contents

[edit]

Intuitive explanations

A NFA consumes a string of input symbols. For each input symbol it transforms to a new state until all input symbols have been consumed.

It is non-deterministic because it may encounter a situation where there are multiple transformations out of a state by using the same letter. For NFA-lambda it is also possible to transform to a new state without consuming any input symbols. For example, if it's in state 1, with the next input symbol an a, it can move to state 2 without consuming any input symbols and can enter state 3 by consuming an a. It is unable to determine the correct state to enter.

Transformations to new states without consuming an input symbol are called lambda transitions. They are usually labelled with the Greek letter λ.

When the last input symbol is consumed the NFA accepts if and only if there is some set of transitions it could make that will take it to an accepting state. Equivalently, it rejects if no matter what choices it makes it would not end in an accepting state.

[edit]

Formal definition

A Nondeterministic Finite State Automaton (NFA) is a 5-tuple, {S, Σ, T, s0, A}, consisting of

  • a finite set of states (S)
  • a finite set of input symbols (Σ)
  • a transition function (T : S × (Σ ∪{ε}) → P(S)).
  • a set of states s0 distinguished as initial (or start) states (s0 ⊆ S)
  • a set of states A distinguished as accepting (or final) states (A ⊆ S)

where P(S) is the power set of S, ε is the empty string, and Σ is the input symbol alphabet.

Let M be an NFA such that M = (S, Σ, T, s0, A), and X be a string over the alphabet Σ. M accepts the string X if there exist both a representation of X of the form x1x2 ... xn, xi ∈ (Σ ∪{ε}), and a sequence of states r0,r1, ..., rn, ri ∈ S, meeting the following conditions:

  1. r0 ∈ s0
  2. ri ∈ T(ri-1, xi ), for i = 1, ..., n
  3. rn ∈ A.

The machine starts in an arbitrary initial state and reads in a string of symbols from its alphabet. The automaton uses the transition relation T to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in" [1]. If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.

The set of all strings accepted by an NFA is the language the NFA accepts. This language is a regular language.

For every NFA a deterministic finite state machine (DFA) can be found that accepts the same language. Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the powerset construction which may lead to an exponential raise in the number of necessary states. Such determinization however is necessary to build a complement automaton.

[edit]

Implementation

There are many ways to implement a NFA:

  • Convert to the equivalent DFA. In some cases this may cause exponential blowup in the size of the automaton, but the simulation stage requires only constant auxiliary space.
  • Keep a set data structure of all states which the machine might currently be in. On the consumption of the last input symbol, if one of these states is a final state, the machine accepts the string. In the worst case, this may require auxiliary space proportional to the number of states in the NFA.
  • Create multiple copies. For each n way decision, the NFA creates up to <math>n-1</math> copies of the machine. Each will enter a separate state. On the consumption of the last input symbol and one copy of the NFA is in the accepting state the NFA will accept.
[edit]

Example

The following example explains a NFA M, with a binary alphabet, which determines if the input contains an even number of 0s or an even number of 1s.

M = (S, Σ, T, s0, A) where

  • Σ = {0, 1},
  • S = {S0, S1, S2, S3, S4},
  • s0 = {S0},
  • A = {S1, S3}, and
  • The transition function T can be defined by this state transition table:
0
1
ε
S0
{}
{}
{S1, S3}
S1
{S2}
{S1}
{}
S2
{S1}
{S2}
{}
S3
{S3}
{S4}
{}
S4
{S4}
{S3}
{}

The state diagram for M is:

Image:NFAexample.png

M can be viewed as the union of two DFAs: one with states {S2, S1} and the other with states {S3, S4}.

The language of M can be described by the regular language given by this regular expression:

<math>(1^*(01^*01^*)^*) \cup (0^*(10^*10^*)^*) </math>
[edit]

References

it:Automa a stati finiti non deterministico he:אוטומט סופי לא דטרמיניסטי ja:非決定性有限オートマトン pl:Niedeterministyczny automat skończony

Retrieved from "http://www.netipedia.com/index.php/Nondeterministic_finite_state_machine"