An automaton is a semiautomaton with two types of special states: starting states, and final states. Specifically, an automaton A is is a five-tuple (S,Σ,δ,I,F), where

  1. 1.

    (S,Σ,δ) is a semiautomaton,

  2. 2.

    a non-empty set IS of starting states, and

  3. 3.

    a set FS of final states or terminating states.

A triple (s,a,t) is called a transition if tδ(s,a), and is written sat. The set δ(s,a) may contain more than one element (or none at all), which is why an automaton is also said to be non-deterministic. If on the other hand δ(s,a) is a singleton for every (s,a), and I is a singleton, then A is said to be deterministicMathworldPlanetmath. In a deterministic automaton, δ can be viewed as a function from S×Σ to S.

If S and Σ are both finite, then A is called a finite-state automaton, or FSA for short.

The state diagramMathworldPlanetmath GA of a finite-state automaton A is constructed as if A is being treated as a semiautomaton. In additionPlanetmathPlanetmath, a vertex corresponding to a starting state has an incoming arrow without a source, and a vertex corresponding to a final state has an outgoing arrow without a destination (alternatively, it may be represented by a double circle). This is illustrated in the following example:

Let A be given by S={σ,s,t}, where σ is the starting state, and t the final state, Σ={a,b}, with the transition function given by the following table

Title automaton
Canonical name Automaton
Date of creation 2013-03-22 12:26:34
Last modified on 2013-03-22 12:26:34
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 42
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45
Synonym next-state function
Synonym terminating state
Synonym FSA
Synonym start state
Synonym recognizer
Related topic DeterministicFiniteAutomaton
Related topic NonDeterministicFiniteAutomaton
Related topic PushdownAutomaton
Related topic Semiautomaton
Defines finite-state automaton
Defines transition function
Defines starting state
Defines final state
Defines configurationMathworldPlanetmath
Defines acceptor
Defines automata
Defines deterministic automaton