A tiny little overview of finite automata

The basic theory of automata was developed to answer very theoretical questions about the foundations of mathematics by German mathematician David Hilbert in 1900. English mathematician and logician Alan Turning furthered this work on automata in the mid-1930s, producing work important to the development of computers.

A finite-state automaton is a very simple machine which is defined by a set of states, an input alphabet, and a function that defines what happens for each input. There must always be an initial state, the state the machine begins in, and at least one final state, which signifies the input has been accepted.

An automaton is a mathematical model of a system with discrete inputs and outputs, given by (Q, å, d, q₀, F ), where:

Q : set of states
å : input alphabet
d : transition function, mapping Q x å to Q
q₀ : initial state
F: final states

For example:

Given A = (Q, å, d, q₀, q₂), where
Q = q₀, q₁, q₂
å = 0, 1

q₀ is the initial state and q₂ is the final state.

The Language accepted by A is the set of any strings of 0s and 1s that end in 01:
L(A) = (01)* + 01