DFA（或 NFA、$\varepsilon$-NFA）接受的语言称正则语言。正则语言可以用正则表达式来表示，即正则表达式表示语言的能力和 DFA 等价。

正则表达式

在字母表 $\Sigma$ 上，正则表达式是这样定义的：

• $\varnothing$ 是一个正则表达式，表示空语言。
• $\varepsilon$ 是一个正则表达式，表示语言 $\{\varepsilon\}$。
• $\Sigma$ 中的任意字母都是一个正则表达式。
• 对于正则表达式 $a$ 和 $b$，$a+b$、$ab$、$a^*$ 和 $(a)$ 都是正则表达式。

例如：

• $(a+b)^*(a+bb)$ 表示一种「由 $a$ 和 $b$ 组成，仅以 $a$ 或 $bb$ 结尾」的语言。
• $(0+\varepsilon)(1+10)*$ 表示一种没有连续两个 $0$ 的语言。

从 DFA 到正则表达式（递归构造法）

将 DFA 中的状态用 $\{1, 2, \cdots, n\}$ 编号，记正则表达式 $R_{ij}^{(k)}$ 表示这样的字符串：能使状态 $i$ 到状态 $j$，而且在途中除了 $i$ 和 $j$ 外，不再经过其他编号高于 $k$ 的状态。

$R_{ij}^{(k)}$ 有如下的递推公式：

$$ \begin{aligned} R_{ij}^{(k)}&=R_{ij}^{(k-1)}\cup R_{ik}^{(k-1)}(R_{kk}^{(k-1)})^*R_{kj}^{(k-1)} \end{aligned} $$

从 DFA 到正则表达式（状态消除法）

按下面的规则从 DFA 中逐个删除起始状态和接受状态外的所有其他状态：

从正则表达式到 DFA（构造 $\varepsilon$-NFA）

按下面的规则从外到内构造 $\varepsilon$-NFA：