Automata theory

An automaton runs when it is given some sequence of inputs in discrete (individual) time steps (or just 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 moves to another state (or transitions) based on a transition function that takes the previous state and current input symbol as parameters. 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.

Automaton

An automaton can be represented formally by a quintuple ${\displaystyle M=\langle \Sigma ,\Gamma ,Q,\delta ,\lambda \rangle }$, where:

• ${\displaystyle \Sigma }$ is a finite set of symbols, called the input alphabet of the automaton,
• ${\displaystyle \Gamma }$ is another finite set of symbols, called the output alphabet of the automaton,
• ${\displaystyle Q}$ is a set of states,
• ${\displaystyle \delta }$ is the next-state function or transition function ${\displaystyle \delta :Q\times \Sigma \to Q}$ mapping state-input pairs to successor states,
• ${\displaystyle \lambda }$ is the next-output function ${\displaystyle \lambda :Q\times \Sigma \to \Gamma }$ mapping state-input pairs to outputs.

If ${\displaystyle Q}$ is finite, then ${\displaystyle M}$ is a finite automaton.[5]

Input word

An automaton reads a finite string of symbols ${\displaystyle a_{1}a_{2}...a_{n}}$, where ${\displaystyle a_{i}\in \Sigma }$, which is called an input word. The set of all words is denoted by ${\displaystyle \Sigma ^{*}}$.

Run

A sequence of states ${\displaystyle q_{0},q_{1},...,q_{n}}$, where ${\displaystyle q_{i}\in Q}$ such that ${\displaystyle q_{i}=\delta (q_{i-1},a_{i})}$ for ${\displaystyle 0<i\leq n}$, is a run of the automaton on an input ${\displaystyle a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$ starting from state ${\displaystyle q_{0}}$. In other words, at first the automaton is at the start state ${\displaystyle q_{0}}$, and receives input ${\displaystyle a_{1}}$. For ${\displaystyle a_{1}}$ and every following ${\displaystyle a_{i}}$ in the input string, the automaton picks the next state ${\displaystyle q_{i}}$ according to the transition function ${\displaystyle \delta (q_{i-1},a_{i})}$, until the last symbol ${\displaystyle a_{n}}$ has been read, leaving the machine in the final state of the run, ${\displaystyle q_{n}}$. Similarly, at each step, the automaton emits an output symbol according to the output function ${\displaystyle \lambda (q_{i-1},a_{i})}$.

The transition function ${\displaystyle \delta }$ is extended inductively into ${\displaystyle {\overline {\delta }}:Q\times \Sigma ^{*}\to Q}$ to describe the machine's behavior when fed whole input words. For the empty string ${\displaystyle \varepsilon }$, ${\displaystyle {\overline {\delta }}(q,\varepsilon )=q}$ for all states ${\displaystyle q}$, and for strings ${\displaystyle wa}$ where ${\displaystyle a}$ is the last symbol and ${\displaystyle w}$ is the (possibly empty) rest of the string, ${\displaystyle {\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)}$.[10] The output function ${\displaystyle \lambda }$ may be extended similarly into ${\displaystyle {\overline {\lambda }}(q,w)}$, which gives the complete output of the machine when run on word ${\displaystyle w}$ from state ${\displaystyle q}$.

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 ${\displaystyle \Gamma }$ and ${\displaystyle \lambda }$ with

• ${\displaystyle q_{0}\in Q}$, a designated start state, and
• ${\displaystyle F}$, a set of states of ${\displaystyle Q}$ (i.e. ${\displaystyle F\subseteq Q}$) called accept states.

This allows the following to be defined:

Accepting word

A word ${\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$ is an accepting word for the automaton if ${\displaystyle {\overline {\delta }}(q_{0},w)\in F}$, that is, if after consuming the whole string ${\displaystyle w}$ the machine is in an accept state.

Recognized language

The language ${\displaystyle L\subseteq \Sigma ^{*}}$ recognized by an automaton is the set of all the words that are accepted by the automaton, ${\displaystyle L=\{w\in \Sigma ^{*}\ |\ {\overline {\delta }}(q_{0},w)\in F\}}$.[13]

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.

Normally automata theory describes the states of abstract machines but there are discrete automata, analog automata or continuous automata, or hybrid discrete-continuous automata, which use digital data, analog data or continuous time, or digital and analog data, respectively.