Fix a finite set$V$ (serving as the alphabet) and denote its free monoid by $V^\star$. A language$L \subseteq V^\star$ is regular whenever there is a formal grammar$G = (V, X, R, s)$ that generates it (i.e. $L(G) = L$) such that all rules in $R$ are of the form $x \to w x'$ for a terminal $w \in V$ and non-terminal symbols $x, x' \in X$.

Properties

Regular languages can be characterised by regular expressions. Regular expressions are inductively generated by the following rules:

For each terminal $w \in V$, $w$

Basic expressions $\emptyset$, $\epsilon$

For each pair of regular expressions $R_1,R_2$, $R_1|R_2$ and $R_1 \cdot R_2$

For each regular expression $R$ the Kleene star $R^\star$.

$L(\epsilon)$ consists of only the empty string, $L(R_1\cdot R_2) = \{\alpha \in V^\star \vert \exists \beta \in L(R_1), \gamma \in L(R_2) \cdot \alpha = \beta \gamma \}$. This is a de-categorified version of the Day convolution monoidal structure.

$L(R^\star) = \{ \alpha \in V^\star \vert \exists n \in \mathbb{N}. \exists\beta_0,\ldots,\beta_{n-1} \in L(R). \alpha = \beta_0\cdots\beta_{n-1} \}$. In category theoretic terms this is the least solution to the recurrence equation $L(R^\star) = L(\epsilon| (R\cdot R^\star))$, and can be constructed by Kleene's fixed point theorem as an $\omega$-colimit.

Every regular language can is denoted by some regular expression in this way.

Equivalently, a language is regular if it can be recognised by a finite-state automaton.