Finite Automata

Definition

A finite automaton (or machine, deterministic finite automaton) $M = (Q, \Sigma , \delta , q_0, F)$ is a list where $Q$ and $\Sigma $ are alphabets (nonempty finite sets), $\delta : Q \times \Sigma \to Q$, $q_0 \in Q$ and $F \subset Q$.

We call $Q$ the states, $\Sigma $ the alphabet, $\delta $ the transition function, $q_0$ the start state (initial state), and $F$ the accept states (or final states). An input $u \in \str(\Sigma )$ results in a state sequence $x \in \str(Q)$ with $x_1 = q_0$ and $x_{i+1} = \delta (x_i, u_i)$ for $i = 1, \dots , \num{u}$. $M$ accepts $x$ if $x_{\num{x}+1} \in F$. The set of all strings that $M$ accepts is the language of the machine $M$. We say that $M$ recognizes or accepts this set. Although a language may accept many different strings, it only ever accepts one language. For example, if the machine accepts no strings, then it accepts the language $\varnothing$.

A $L \subset \str(\Sigma )$ is called regular if there exists a finite automaton that recognizes it.