nLab regular language

Idea

Regular languages are a simple kind of formal languages, the least expressive in the Chomsky hierarchy.

Definition

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:

1. For each terminal $w \in V$, $w$
2. Basic expressions $\emptyset$, $\epsilon$
3. For each pair of regular expressions $R_1,R_2$, $R_1|R_2$ and $R_1 \cdot R_2$
4. For each regular expression $R$ the Kleene star $R^\star$.

These can be given a semantics in the poset of languages $P(V)$ by universal properties.

1. $L(\emptyset) = \emptyset$ and $L(R_1 | R_2) = L(R_1) \cup L(R_2)$. These are nullary and binary joins.
2. $L(w) = \{ w \}$. These are representable viewing languages as de-categorified presheaves.
3. $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.
4. $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.

Related entries

• context-free grammar