Automaton

automata-theory

Definition

Automaton

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

where:

• is a set of states,
• is the input alphabet,
• is the transition function,
• is the set of initial states, and
• is the set of accepting (final) states (subset of ).

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

Visual Representation

The following diagram illustrates a deterministic finite automaton:

Transition Function

Definition

Transition Function (Automata Theory)

The transition function is a mapping that takes a current state and an input symbol and returns the subsequent state .

Link to original

Extended Transition Function

Definition

Extended Transition Function

The extended transition function describes the state reached by an automaton after processing an entire input string . It is defined recursively over the length of the string:

Intuitively, is the state the automaton is in after starting in state and reading all symbols of sequentially.

Link to original

Formal Concepts

Empty String

Definition

Empty String

The empty string is the unique string of length and is denoted as :

Link to original

Language

Definition

Accepted Language

The accepted language of an automaton over alphabet is the set of all strings that the automaton accepts, i.e. strings for which has a successful run according to its acceptance criterion. It’s denoted as .

Link to original

Equivalence

Definition

Automaton Equivalence

Two automata and are equivalent if they accept the same language, i.e., .

Link to original