# Automaton

https://en.wikipedia.org/wiki/Automata\_theory#Automata

General definition of _automaton_ (p. automata), which restricts a broader definition of system to one viewed as acting in discrete time-steps, with its state behavior and outputs defined at each step by unchanging functions of only its state and input.

## Informal description

An automaton runs when it is given some _sequence of inputs_ in discrete (individual) time steps or steps. An automaton processes one input picked from a set of symbols or letters, which is called an _input alphabet_. The symbols received by the automaton as input at any step are a _sequence of symbols called words_. An automaton has a _set of states_. At each moment during a run of the automaton, the automaton is in one of its states. When the automaton receives new input it _transitions to another state_ based on a _transition function that takes the previous state and current input symbol as params_.

At the same time, another function called the _output function_ produces symbols from the _output alphabet_, also according to _the previous state and current input symbol_. The automaton reads the symbols of the input word and transitions between states until the word is read completely, if it is finite in length, at which point the automaton halts. A state at which the automaton halts is called _the final state_.

To investigate the possible state/input/output sequences in an automaton using formal language theory, a machine can be assigned a _starting state_ and a set of _accepting states_. Then, depending on whether a run starting from the starting state ends in an accepting state, the automaton can be said to accept or reject an input sequence.

The set of all the words accepted by an automaton is called _the language recognized by the automaton_. A familiar example of a machine recognizing a language is an electronic lock which accepts or rejects attempts to enter the correct code.

## Formal definition

### Automaton

An automaton can be represented formally by a 5-tuple, `M = (Σ, Γ, Q, δ, λ)`

* `Σ` finite set of symbols, called the _input_ alphabet of the automaton
* `Γ` finite set of symbols, called the _output_ alphabet of the automaton
* `Q` a set of _states_, `q₀` is the initial state, final state `qₙ`
* `δ` the _transition_ (or next-state) function, `δ : Q × Σ → Q` mapping state-input pairs to successor states
* `λ` is the _next-output_ function, `λ : Q × Σ → Γ` mapping state-input pairs to outputs.

If `Q` is finite, then `M` is a _finite automaton_.

### Input word

An automaton reads a finite string of symbols, `a₁ … aₙ` where `aᵢ ∈ Σ`, which is called an _input word_. The _set of all words_ is denoted by `Σ*`.

### Run

A sequence of states, `q₀ … qₙ` where `qᵢ ∈ Q` such that `qᵢ = δ (qᵢ˗₁, aᵢ)` for `0 < i <= n`, is a run of the automaton on an input `a₁ … aₙ ∈ Σ*` starting from the initial state, `q₀`. In other words, initially, an automaton is at the start state q₀ and receives input a₁.

### Acceptor

In order to study an automaton with the theory of formal languages, an automaton may be considered as an acceptor, replacing the output alphabet and function Γ and λ with

* `q₀ ∈ Q` as the start state
* `F`, a set of states of Q, `F ⊆ Q`, called _acceptor states_

This allows the following to be defined:

### Accepting word

### Recognized language

The language `L ⊆ Σ*` recognized by an automaton is the set of all the words that are accepted by the automaton, `L = { w ∈ Σ* | δ (q₀, w) ∈ F }`.

### Recognizable languages

The recognizable languages are the set of languages that are recognized by some automaton. For finite automata the recognizable languages are _regular languages_. For different types of automata, the recognizable languages are different.
