A finite automaton is a simple mathematical machine. It is a representation of how computations are performed with limited memory space.
| 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\) |
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 state, where } q_0 \in Q \\ F &: \text{set of accept states, where } F \subseteq Q \end{align} \]
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.
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.