字母表(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$ 表示。

串的长度

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

串的拼接(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)。

1

符号位置数量不等于符号数量,比如串 "101010" 中的符号位置数量为 6,但符号数量(只有 0 和 1 )为 2。