home

Finite automata

A finite automaton is a simple mathematical machine. It is a representation of how computations are performed with limited memory space.

Notation

Symbol Term Description
\(\Sigma\) alphabet a non-empty set of symbols, for example \(\Sigma = \{0,1\}\) is the binary alphabet
\(x\) (or any variable) string a finite sequence of symbols from an alphabet
\(\epsilon\) empty string strings with zero letters
\(\lvert x\rvert\) length the length of the string \(x\)
\(\Sigma^*\) all strings the set of all strings of \(\Sigma\), for example \(\Sigma = {0,1} \implies \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, \ldots\}\)
\(\Sigma^+\) non-empty strings all non-empty strings of \(\Sigma\) (\(\Sigma^* - \epsilon\))
\(\Sigma^k\) strings of lenght \(k\) string in \(\Sigma\) with length \(k\)

Formal expression

An automaton \(M\) is a 5-tuple: \[ \langle Q, \Sigma, \delta, q_0, F \rangle \] where \[ \begin{align} Q &: \text{finite set of states} \\ \Sigma &: \text{alphabet of inputs} \\ \delta &: \text{transition function in the form } Q \times \Sigma \to Q \\ q_0 &: \text{start start, where } q_0 \in Q \\ F &: \text{set of accept states, where } F \subseteq Q \end{align} \] ## Accept states When parsing an input, the automaton continues to read until the end of input is reached. If an accept state is reached during this process, computation continues. The final output of accept/reject is only provided at the end of computation, when the input is exhausted.

Language

The set of all strings accepted by an automaton is called the language of that automaton.

If \(M\) is an automaton on alphabet \(\Sigma\), then \(\mathcal{L}(M)\) is the language of \(M\). \[ \mathcal{L} = \{w \in \Sigma^* \ |\ M \text{ accept } w \} \] Languages that can represented by a finite automaton are termed Regular languages.