Preface

Contents

Index

Glossary

Models

Rogues

Nondeterministic Finite State Automata

Nondeterminism plays a key role in the theory of computing.  A nondeterministic finite state automaton is one in which the current state of the machine and the current input do not uniquely determine the next state.  This just means that a number of subsequent states (zero or more) are possible next states of the automaton at every step of a computation.

Of course, nondeterminism is not realistic, because in real life, computers must be deterministic.  Still, we can simulate nondeterminism with deterministic programs. Furthermore, as a mathematical tool for understanding computability, nondeterminism is invaluable.   

As with deterministic finite state automata, a nondeterministic finite state automaton has five components.

1. a set of states

2. a finite input alphabet from which input strings can be constructed

3. a transition function that describes how the automaton changes states as it processes an input string

4. a single designated starting state

5. a set of accepting states

The only difference lies in the transition function, which can now target subsets of the states of the automaton rather than a single next state for each state, input pair.  Formally,  a nondeterministic finite state automaton can be defined as follows:

Definition

A nondeterministic finite state automaton (nfsa) is a five-tuple, M = (Q, S, d, q₀, F), where Q is a finite set of states, S is a finite input alphabet, d is a transition function, d: Q ´ S ® 2^Q, q₀ Î Q is the starting state, and F--a subset of Q--is a set of accepting states.

Notice how the definition of the transition function differs from that for a deterministic finite state automaton.