# regular language

**Definition.** A
non-deterministic automaton $(Σ,S,ϕ,i,f)$ is given by a set of symbols $Σ$, a set of states $S$, a pair of initial and final states $i,f ∈ S$, and a transition relation $ϕ_t ⊆ S × S$ for each symbol $t ∈ Σ$. Note that the transition function $ϕ﹕ Σ → Rel(S;S)$ extends to a function $ϕ^\ast ﹕ Σ^\ast → Rel(S;S)$.

A word $w ∈ Σ^{\ast}$ is accepted if there exists a transition to the final state, $f ∈ ϕ^\ast_w(i)$. A regular language is a set of words $L ⊆ Σ^\ast$ that arises as the set of words accepted by an automaton.