regular language

Definition. A non-deterministic automaton $(\Sigma ,S,\varphi ,i,f)$ is given by a set of symbols $\Sigma$, a set of states $S$, a pair of initial and final states $i,f\in S$, and a transition relation ${\varphi }_t\subseteq S\times S$ for each symbol $t\in \Sigma$. Note that the transition function $\varphi ﹕\Sigma \to Rel(S;S)$ extends to a function ${\varphi }^{\ast }﹕{\Sigma }^{\ast }\to Rel(S;S)$.

A word $w\in {\Sigma }^{\ast }$ is accepted if there exists a transition to the final state, $f\in {\varphi }_w^{\ast }(i)$. A regular language is a set of words $L\subseteq {\Sigma }^{\ast }$ that arises as the set of words accepted by an automaton.