自动机理论 • 基本概念

字母表（Alphabet）

字母表是一个有限、非空的符号集合，常用 $\Sigma$ 表示。

字母表的幂（Power）

某个字母表 $\Sigma$ 的 $k$ 次幂就是由该字母表中的字母组成的，长度为 $k$ 的所有串组成的集合，记作 $\Sigma^k$。

字母表的 Kleene 闭包（克莱尼星号， Kleene star）

Kleene 星号，或称 Kleene 闭包，德语称 Kleensche Hülle，在数学上是一种适用于字符串或符号及字元的集合的一元运算。 —— Wikipedia

某个字母表 $\Sigma$ 在进行 Kleene 星号运算后的结果就是这个字母表可以表示的所有字符串（包含空串）组成的集合，记作 $\Sigma^*$。

将其中的空串去掉之后的集合记作 $\Sigma^+$。

我们有：

$$ \Sigma^+ = \bigcup^{+\infty}_1 \Sigma^k $$

$$ \Sigma^* = \bigcup^{+\infty}_0 \Sigma^k = \Sigma^+ \cup \{\epsilon\} $$

串（String）

串是一个由从某个字母表中选取的符号组成的序列。

空串是一个没有符号的串，常常用 $\epsilon$ 表示。

串的长度

串的长度是指串中符号位置¹的数量。

串的拼接（Concatenation）

设有两个串 $x = a_1a_2\cdots a_n$ 和 $y = b_1b_2\cdots b_m$，则 $$ xy = a_1a_2\cdots a_nb_1b_2\cdots b_m $$

语言（Language）

对于某个字母表 $\Sigma$，一个语言指其 Kleene 闭包的一个子集。

问题 （Problem）

在自动机理论中，一个问题是一个判定一个给定的串是否属于某个语言的问题（question）。