\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Formal Languages
Finite Automata
Needed by:
Nondeterministic Finite Automata
Regular Expressions
Sheet PDF
Graph PDF

Regular Languages


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

Regular operations

Let $A, B \subset \str(\Sigma )$ be languages in $\Sigma $.


The union (alternation) of $A$ and $B$ is, as usual, the set $A \cup B$.


The concatenation of $A$ and $B$ is the set $\Set{xy}{x \in A \text{ and } y \in B}$, where $xy$ denotes length $\num{x}+\num{y}$ string which is the concatenation of $x$ and $y$


The star (Kleene star, multi-concatenation) of $A$ is the set

\[ \Set{x \in \str(\Sigma )}{\exists k \geq 0, x = y_1y_2 \cdots y_k, y_i \in A}. \]

By this definition we do mean to include the empty string $\varnothing$ in $A^*$, regardless of $A$.


We denote the alternation of $A$ and $B$ by $A \cup B$ as usual, but other notations include $A + B$, $A\mid B$, and $A \lor B$. We denote the concatenation of $A$ and $B$ by $AB$, but other notations include $A \circ B$. We denote the star of $A$ by $A^*$.

Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view