形式语言与自动机理论-01-语言

\(\newcommand{\card}[1]{\big| #1 \big|}\)

字母表,字符串,语言

取一非空有限集合,记为 \(\Sigma\),称集合中的元素为字符,称 \(\Sigma\) 为字母表,或符号集。我们用一个手写/计算机字符表达 \(\Sigma\) 中的某一元素,如 \(\Sigma = \{a, b, c, \dots\}\), \(\Sigma = \{\alpha, \beta, \gamma, \dots\}\)

约定:为了避免当后文引入更多定义时造成冲突,我们在形式上避免用多于一个字符的序列来表达 \(\Sigma\) 中的元素,如 \(\Sigma = \{letter1, letter2\, \dots\}\)。在英文字母,希腊字母不足够使用时,也使用形如 \(a_i, a^\bullet\) 等记号表示字符。

\(\Sigma\) 中元素(可重复)组成的任意有限长有序集组成的集合称为字符串。特别地,记号 \(\varepsilon\) 表示长度为 0 的字符串。

不失一般性地,假设 \(\varepsilon \not\in \Sigma\)

注:上述“不失一般性地”短语可理解为,由于我们并非在讨论某个具体的语言,而仅仅是抽象地讨论“语言”这个概念,因此仅需分别为字母表里的各个符号选择逐不相同的记号,因此我们仅需避开使用 \(\varepsilon\) 表示 \(\Sigma\) 中的某一字符。

注意,由于我们是在讨论抽象的概念,因此某个语言中的字符串对人类来说并不一定具有某种含义。仅在讨论某些具体的语言(字符串集合)时,该语言中的字符串才会具备可被解读的意义。

约定:在不产生歧义的情况下,我们记字符串 \((\sigma_1, \sigma_2, \dots, \sigma_n)\)\(\sigma_1\sigma_2\dots\sigma_n\)

约定:除非是在讨论某一具体字母表及其上的语言,我们使用希腊字母表示字符,拉丁字母表示字符串。

记号 \(\card{s}\) 表示 \(s\) 的长度,因此有

  1. \(\card\varepsilon = 0\).

  2. 若我们稍微滥用一下符号,同时记 \(\Sigma\) 为由字母表 \(\Sigma\) 组成的所有长度为 1 的字符串的集合,那么有 \(\forall s \in \Sigma, \card{s} = 1\).

称由 \(\Sigma\) 组成的某些字符串集合为定义于 \(\Sigma\) 上的语言。

记不包含任何字符串的语言为 \(\emptyset = \{\}\).

注意,空语言不等于语言 \(\{\varepsilon\}\),由于后者至少含有一个字符串。

例如,定义在英文字母表 \(\Sigma = \{a, b, \dots, z\}\) 上的语言 \(L = \{\varepsilon, a, b, \dots, aa, ab, \dots, zzzz\dots\}\) 包含所有由英文字母排列组合得到的字符串,其因此包含字符串 \(xyxxy\)。然而该字符串并没有任何意义,该语言也并不是任何一门人类使用的语言。有定义在同样字母表上的英文语言为 \(L\) 的子集。

本系列文章不打算讨论人类使用的自然语言,因为很难具体定义英文语言的集合,即给定一个字符串,我们并不一定可以轻而易举地决定该字符串是否在英文语言中。然而对于编程语言这一类的形式语言来说,我们总是有严格的界限判定由某一字母表组成的给定字符串是否在定义在该字母表上的语言中。当然我们将要在可计算理论部分中看到,有严格的界限并不一定意味着存在具体的一系列可被执行的判定步骤。1

字符串集合上的运算

我们定义一系列在字符串集合上的运算。

二元运算 \(s_1 \cdot s_2\) 为字符串 \(s_1\)\(s_2\) 的串联。即 \(s_1 \cdot s_2\) 的结果为先按顺序写下 \(s_1\) 中的符号,紧接着按顺序写下 \(s_2\) 中的符号。

观察表达式 \(ab\),我们既可以将其理解为一个长度为 2 的字符串,又可以明显看出他可能是由长度皆为 1 的两个字符串 \(a\), \(b\) 串联得到。因此我们有理由在方便的时候记 \(s_1s_2 = s_1 \cdot s_2\).

于是有关于串联的性质如下:

  1. \(\varepsilon\) 为串联运算的运算幺元(单位元)。

    \(\varepsilon s = s \varepsilon\).

    由于我们以类似数的乘法的记号表示串联,于是可以认为空字符串 \(\varepsilon\) 具有类似于数 1 在乘法中的性质,因此称这样的元素其为幺元。

  2. 串联运算是结合的。

    \((xy)z = x(yz)\).

    因此我们不必使用括号来表达数个串联运算之间的运算顺序。

因此有字母表 \(\Sigma\) 及定义其上的运算 \(\cdot_\Sigma\) 构成幺半群 \((\Sigma, \cdot_\Sigma)\)。在无歧义的情况下我们记 \(\cdot = \cdot_\Sigma\)。注意串联运算不可逆,即除非 \(s = \varepsilon\),否则不存在 \(t\) 使得 \(ts = st = \varepsilon\).

\(s\) 为一字符串, \(n \in \mathbb{N}\),定义 \(s^n\)\(n\)\(s\) 串联。形式化地,有如下归纳定义:

\[ s^n = \begin{cases} \varepsilon, &n = 0\\ ss^{n-1}, &\text{否则} \end{cases} \]

为了方便讨论,我们另做出如下定义:

若可以将 \(s\) 写为 \(xy\) 的形式,则称 \(x\)\(s\) 的前缀, \(y\)\(s\) 的后缀。

若可以将 \(s\) 写为 \(xyz\) 的形式,则称 \(y\)\(s\) 的子字符串或者中缀。

另一种定义前缀的方法为,若存在 \(y\) 使得 \(xy = s\),则称 \(x\)\(s\) 的前缀。而后缀和中缀也可以用类似的方法定义。

有以下关于前缀,后缀,中缀的性质:

\(s\)\(\varepsilon\)\(s\) 的前缀,后缀,中缀。

语言上的运算

\(L_1\), \(L_2\) 皆定义在字母表 \(\Sigma\) 上,定义 \(L_1 + L2\) 由两语言中所有字符串组成的语言,即若视语言为集合,则 \(L1 + L2\) 仅仅是我们用来表达 \(L_1 \cup L_2\) 的方法。

我们可以将该运算进行拓展。若 \(L_1\) 为定义在 \(\Sigma_1\) 上的语言,\(L_2\) 为定义在 \(\Sigma_2\) 上的语言,则有 \(L_1 + L_2\) 为定义在 \(\Sigma_1 \cup \Sigma_2\) 上的语言。

类似地可以使用集合论定义语言上的交与补运算。其中用来定义补运算的全集将是稍后将要定义的记作 \(\Sigma^*\) 的语言。

并运算构成幺半群,幺元为 \(\emptyset\).

交运算构成幺半群,幺元为 \(\Sigma^*\).

我们将串联运算拓展至语言上:

定义 \(L_1 \cdot L_2 := \{s_1s_2 | s_1 \in L_1, s_2 \in L_2\}\)。同样有 \(L_1L_2 := L_1 \cdot L_2\).

定义在语言上的串联运算同样构成幺半群,其运算幺元为 \(\{\varepsilon\}\)

注意语言上的串联运算的幺元并非 \(\emptyset = \{\}\),由于有 \(\emptyset L = L \emptyset = \emptyset \ne L\).

类似地,可以将幂运算拓展至语言上。

根据对串联的定义可知,串联运算是封闭的,即任意两个语言的串联仍然是语言。因此可得知幂运算也是封闭的。因此我们可以定义所谓的封闭运算如下:

\[ \begin{aligned} L^* &= L^0 \cup L^1 \cup L^2 \cup \dots\\ &= \bigcup_{n \in \mathbb{N}} L^n \end{aligned} \]

其中有 \(L^0 = \{\varepsilon\}\)

少见地也有定义如下定义

\[ L^+ = \bigcup_{n \in \mathbb{N}^+} L^n \]

因此 \(L^* = L^0 \cup L^+ = \{\varepsilon\} \cup L^+\).

特别地,有 \(\emptyset^* = \{\varepsilon\}\).

特别地,有 \(\Sigma^*\) 为任何定义在 \(\Sigma\) 上的语言的超集。事实上,该集合为定义在 \(\Sigma\) 上的字符串的集合。


  1. 在不追求严谨的现在,我们可以称这样的步骤为算法↩︎