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

1. 1.

$(S,\Sigma,\delta)$ is a semiautomaton,

2. 2.

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

3. 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\lx@stackrel{{\scriptstyle a}}{{\longrightarrow}}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\Sigma$ to $S$.

If $S$ and $\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, $\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 \@unrecurse