Automaton

automata-theory

Definition

Automaton

An automaton is a formal mathematical model of a computational system, typically defined as a quintuple:

$$\mathcal{A}=(Q,\Sigma ,\delta ,I,F)$$

where:

• $Q$ is a set of states,
• $\Sigma$ is the input alphabet,
• $\delta$ is the transition function,
• $I\subseteq Q$ is the set of initial states, and
• $F\subseteq Q$ is the set of accepting (final) states (subset of $Q$).

An automaton processes input symbols from $\Sigma$ by transitioning between states according to $\delta$ and determines acceptance based on whether the computation terminates in a state belonging to $F$.

Visual Representation

The following diagram illustrates a deterministic finite automaton:

Transition Function

Definition

Transition Function

The transition function $\delta :Q\times \Sigma \to Q$ is a mapping that takes a current state $q\in Q$ and an input symbol $x\in \Sigma$ and returns the subsequent state $q^{\prime }\in Q$.

Link to original

Extended Transition Function

Definition

Extended Transition Function

The extended transition function ${\delta }^{\ast }:Q\times {\Sigma }^{\ast }\to Q$ describes the state reached by an automaton after processing an entire input string $w\in {\Sigma }^{\ast }$. It is defined recursively over the length of the string:

$${\delta }^{\ast }(q,w)=\{\begin{array}{ll}q& \text{if }w=\epsilon \\ \delta ({\delta }^{\ast }(q,u),a)& \text{if }w=ua\text{ for }u\in {\Sigma }^{\ast },a\in \Sigma \end{array}$$

Intuitively, ${\delta }^{\ast }(q,w)$ is the state the automaton is in after starting in state $q$ and reading all symbols of $w$ sequentially.

Link to original

Formal Concepts

Empty String

Definition

Empty String

The empty string a string of length $0$ and is denoted as $\epsilon$:

$$|\epsilon |=0$$

Link to original

Language

Definition

Accepted Language

The accepted language of an automaton $A$ over alphabet $\Sigma$ is the set of all strings that the automaton accepts, i.e. strings for which $A$ has a successful run according to its acceptance criterion. It’s denoted as $\mathcal{L}(A)$.

$$\mathcal{L}(A)=\{w\in {\Sigma }^{\ast }\mid {\delta }^{\ast }(q_0,w)\cap F\ne \{\}\}$$

Link to original

Equivalence

Definition

Automaton Equivalence

Two automata $\mathcal{A}$ and $\mathcal{B}$ are equivalent if they accept the same language, i.e., $L(\mathcal{A})=L(\mathcal{B})$.

Link to original