automaton

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,\mathrm{\Sigma },\delta ,I,F)$, where

1. $(S,\mathrm{\Sigma },\delta )$ is a semiautomaton,

2. a non-empty set $I\subseteq S$ of starting states, and

3. a set $F\subseteq S$ of final states or terminating states.

A triple $(s,a,t)$ is called a transition if $t\in \delta (s,a)$, and is written $s\stackrel{a}{⟶}t$. The set $\delta (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 $\delta (s,a)$ is a singleton for every $(s,a)$, and $I$ is a singleton, then $A$ is said to be deterministic. In a deterministic automaton, $\delta$ can be viewed as a function from $S\times \mathrm{\Sigma }$ to $S$.

If $S$ and $\mathrm{\Sigma }$ are both finite, then $A$ is called a finite-state automaton, or FSA for short.

The state diagram $G_A$ of a finite-state automaton $A$ is constructed as if $A$ is being treated as a semiautomaton. In addition, 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=\{\sigma ,s,t\}$, where $\sigma$ is the starting state, and $t$ the final state, $\mathrm{\Sigma }=\{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	configuration
Defines	acceptor
Defines	automata
Defines	deterministic automaton