DFA#

介绍了文法之后，我们来介绍 有限自动机 (Finite Automaton, FA)。有限自动机是一种抽象的计算模型，它可以识别特定的语言。想象一个只有有限数量 内存的机器，它 读取输入串，并根据读取到的符号从一个状态转换到另一个状态。

有限自动机主要分为两种类型：确定性有限自动机 (Deterministic Finite Automaton, DFA) 和 非确定性有限自动机 (Nondeterministic Finite Automaton, NFA)

DFA 是一个五元组，表示为 $M = (Q,\ \Sigma,\ \delta,\ s,\ F)$，其中：

• $Q$ (States)：$Q$ 是一个有限的状态集合。自动机在任何时刻都处于这些状态中的某一个。

• $\Sigma$ (Alphabet)：$\Sigma$ 是一个有限的输入字母表。这是自动机可以接收的所有输入符号的集合。

• $\delta$ (Transition function)：$\delta$ 是转移函数，它定义了自动机在给定状态和输入符号下如何转移到下一个状态。 对于 DFA 来说，这个转移是确定 的，也就是说，对于任何一个状态 $q \in Q$ 和任何一个输入符号 $a \in \Sigma$，都唯一对应着一个下一个状态。 我们可以将转移函数表示为 $\delta:\ Q × Σ → Q$。 例如，$\delta(q, a) = p$ 表示当自动机处于状态 $q$，并且读取到输入符号 $a$ 时，它会转移到状态 $p$。

• s (Start state)：$s$ 是起始状态，也称为初始状态。它是自动机开始处理输入之前的状态。$s \in Q$。

• F (Final states)：$F$ 是接受状态的集合，也称为终止状态。$F ⊆ Q$。如果自动机在读取完整个输入字符串后，停留在某个接受状态，那么我们就说这个 DFA 接受了该输入字符串。

对于一个 DFA $M$，它所接受的语言 $L(M)$ 定义为所有能让 DFA 从起始状态开始，经过一系列状态转移，最终停留在接受状态的输入字符串的集合。它可以表示为：$L(M) = \{ w \in \Sigma^* \mid \delta^*(s, w) \in F \}$，$\delta^*$ 是对转移函数 $\delta$​ 的扩展，使其可以处理字符串输入。

这里的转移函数可以嵌套，例如：$\delta^*(q, wa) = \delta^*(\delta^*(q,\ w),\ a)$

从非形式化的角度来看，DFA 的工作方式可以这样理解：

1. 输入准备：首先，将要被处理的输入字符串放在一个“纸带”上，通常是左对齐的。
2. 初始状态：DFA 从起始状态开始运行。
3. 头字符定位：一个“header”指针指向纸带上最左边的符号，也就是输入字符串的第一个符号。
4. 循环处理：DFA 进入一个循环，直到整个输入字符串被读取完毕。
5. 查阅转移表：在每一步，DFA 根据当前的 状态 (s) 和读头指向的 输入符号 (σ) 查阅它的 转移表。
6. 状态转移：根据转移表中的指示，DFA 转换到下一个状态。转移表可以看作是一个函数，输入是当前状态和输入符号，输出是下一个状态。
7. 接受或拒绝：当整个输入字符串被读取完毕后，DFA 停止运行。如果 DFA 当前所处的状态是 接受状态 (final state)，那么 DFA 就 接受 这个输入字符串。 否则，如果 DFA 停留在非接受状态，则 拒绝 该字符串。

DFA 可以用 状态转移图 (state transition diagram) 来直观地表示。状态转移图由以下元素组成：

• 状态 (States)：DFA 的每个状态都用一个 圆圈 表示。
• 转移 (Transitions)：状态之间的转移用 带箭头的有向边 表示。 箭头从一个状态指向另一个状态，箭头上的 标签 是触发该转移的 输入符号。 例如，如果从状态 $q1$ 到状态 $q2$ 有一个标有 ‘a’ 的箭头，表示当 DFA 处于状态 $q1$ 并读取到输入符号 ‘a’ 时，会转移到状态 $q2$。
• 起始状态 (Start state)：起始状态用一个 指向该状态的三角形 表示，箭头没有起点。
• 接受状态 (Final states)：接受状态用 双层圆圈 表示。

例如下面这个例子：$L = \{w \in \{a, b\}^* \mid w \text{ has even length and start with a end with b}\}$​

• 状态 (States)：

  • q0: 初始状态，可以理解为“已读取的字符长度为 0 (偶数)”
  • q1: 标记为 “end with a, odd length”，可以理解为“已读取的字符长度为奇数，且最后一个字符是 ‘a’”
  • q2: 接受首次输入为 ‘b’ 时跳转，此处不符合由 ‘a’ 开头的接收状态。
  • q3: 标记为 “end_a_even”，可以理解为“已读取的字符长度为偶数，且最后一个字符是 ‘a’”
  • q4: 标记为 “end_b_even”，并且是 接受状态，可以理解为“已读取的字符长度为偶数，且最后一个字符是 ‘b’”
  • q5: 标记为 “end_b_odd”，可以理解为“已读取的字符长度为奇数，且最后一个字符是 ‘b’”

• 转移 (Transitions)：

  • from 0 to 1 on a: 在初始状态 q0 读到 ‘a’，转移到 q1 (长度变为奇数)

  • from 0 to 2 on b: 在初始状态 q0 读到 ‘b’，转移到 q2

  • from 1 to 3 on a: 在状态 q1 读到 ‘a’，转移到 q3 (长度变为偶数)

  • from 3 to 1 on a: 在状态 q3 读到 ‘a’，转移到 q1 (长度变为奇数)

  • from 1 to 4 on b: 在状态 q1 读到 ‘b’，转移到 q4 (长度变为偶数，且以 ‘b’ 结尾，是接受状态)

  • from 3 to 5 on b: 在状态 q3 读到 ‘b’，转移到 q5 (长度变为奇数)

  • from 4 to 1 on a: 在状态 q4 读到 ‘a’，转移到 q1 (长度变为奇数)

  • from 5 to 3 on a: 在状态 q5 读到 ‘a’，转移到 q3 (长度变为偶数)

  • from 4 to 5 on b: 在状态 q4 读到 ‘b’，转移到 q5 (长度变为奇数)

  • from 5 to 4 on b: 在状态 q5 读到 ‘b’，转移到 q4 (长度变为偶数，且以 ‘b’ 结尾，是接受状态)

NFA#

在之前学习 DFA 的时候，我们强调了“确定性”，即在任何给定状态下，对于任何输入的符号，DFA 要转换到的下一个状态是唯一的。

而 NFA (Nondeterministic Finite Automaton) 的核心特点就是它的“非确定性”。可以把 NFA 想象成一个在多个方向上同时进行计算的机器，在某个状态下，对于同一个输入符号，NFA 可以有 多个 下一个状态。

与 DFA 类似，一个 NFA 也可以用一个五元组来定义：$M = (Q,\ \Sigma,\ \delta,\ q_0,\ F)$​

• $Q$(States)：有限的状态集合，与 DFA 相同。
• $\Sigma$ (Alphabet)：有限的输入字母表，与 DFA 相同。
• $\delta$ (Transition function)：对于 NFA 来说，转移函数 $\delta$ 的输入是一个状态和一个输入符号，输出是一个状态的集合。$\delta: Q \times \Sigma → P(Q)$，其中 $P(Q)$ 表示 $Q$ 所有子集的集合。从一个状态读取一个符号后，NFA 可以转移到多个可能的状态。例如，$\delta(q, a) = \{p₁,\ p₂,\ p₃\}$ 表示当 NFA 处于状态 $q$，读取到输入符号 a 时，它可以同时转移到状态 $p₁,\ p₂,\ p₃$。
• $q_0$ (Start state)：起始状态，与 DFA 相同。
• $F$ (Final states)：接受状态的集合，与 DFA 相同。

当 NFA 接收一个输入字符串时，它会从起始状态开始，根据输入的符号进行状态转移。由于 NFA 的非确定性，对于每个输入符号，NFA 可能会同时探索多条可能的计算路径。

一个 NFA 接受一个输入字符串，当且仅当存在 至少一条 从起始状态到某个接受状态的路径，使得这条路径上的符号与输入字符串匹配。只要存在一种可能的计算路径能够成功到达接受状态，NFA 就认为该字符串是被接受的。

下面是一个NFA的设计问题例子：$L = \{ w\ |\ w \in \{a, b\}^*,\ w\ \text{ends with aaabb}\}$​

这个语言包含所有以字符串 “aaabb” 结尾的由 ‘a’ 和 ‘b’ 组成的字符串。

• 状态 (States)：
  • q0: 起始状态。 在读取 “aaabb” 的任何前缀之前。这个状态有一个自环，遇到 ‘a’ 或 ‘b’ 仍然回到自身，可以在开始时读取任意数量的 ‘a’ 和 ‘b’。
  • q1: 表示到目前为止，可能已经读取了 “a”。
  • q2: 表示到目前为止，可能已经读取了 “aa”。
  • q3: 表示到目前为止，可能已经读取了 “aaa”。
  • q4: 表示到目前为止，可能已经读取了 “aaab”。
  • q5: 接受状态。 表示已经成功读取了 “aaabb”。
• 转移 (Transitions)：
  • from 0 to 0 on a: 在 q0 状态读取 ‘a’，仍然保持在 q0 (可以读取任意数量的 ‘a’ 开头)。
  • from 0 to 0 on b: 在 q0 状态读取 ‘b’，仍然保持在 q0 (可以读取任意数量的 ‘b’ 开头)。
  • from 0 to 1 on a: 在 q0 状态读取 ‘a’，可以转移到 q1 (开始匹配 “aaabb” 的第一个 ‘a’)。 注意这里从 q0 读取 ‘a’ 有两个可能的转移，这就是非确定性的体现。
  • from 1 to 2 on a: 在 q1 状态读取 ‘a’，转移到 q2 (匹配到 “aaabb” 的前两个 ‘a’)。
  • from 2 to 3 on a: 在 q2 状态读取 ‘a’，转移到 q3 (匹配到 “aaabb” 的前三个 ‘a’)。
  • from 3 to 4 on b: 在 q3 状态读取 ‘b’，转移到 q4 (匹配到 “aaabb” 的前四个字符 “aaab”)。
  • from 4 to 5 on b: 在 q4 状态读取 ‘b’，转移到接受状态 q5 (成功匹配 “aaabb”)。

通常情况下，对于同一个正则语言，描述它的 NFA 所需的状态数量往往比等价的 DFA 更少，或者至多相等。因为 NFA 的非确定性允许它在状态转移时“猜测”正确的路径，从而可以用更简洁的方式来描述模式。

在NFA中，存在一种特殊的转换，称为 $\lambda$ 转换。指的是在自动机中，不消耗任何输入符号就能发生的状态转移。可以把它想象成一种“自由移动”，自动机可以在不读取任何输入的情况下，从一个状态瞬间转移到另一个状态。

例如，如果一个 NFA 从状态 $q_1$ 有一个 $\lambda$ 转换到状态 $q_2$，那么当 NFA 处于状态 $q_1$ 时，它可以“选择”立即转移到 $q_2$，而不需要读取任何输入.

Regular Expression#

正则表达式是描述正则语言的一种形式化工具，它与有限自动机（NFA 和 DFA）以及正则文法等价。正则表达式是用来描述正则语言的一种形式化工具。给定一个字母表 $\Sigma$​，正则表达式的定义如下 ：

• $\emptyset$：表示空集，即不包含任何字符串的语言。
• $\lambda/\epsilon$：表示只包含空串的语言，即$\{\lambda\}$。与 $\emptyset$ 的区别是，$\emptyset$ 是一个集合，而 $\lambda$ 是一个元素。
• $a$：对于字母表 $\Sigma$ 中的每个符号 $a$，表示包含该符号的语言，例如，如果 $\Sigma = \{a, b\}$，那么 $a$ 表示语言 $\{a\}$，$b$ 表示语言 $\{b\}$。

通过组合已有的正则表达式，我们可以构建更复杂的正则表达式。如果 $r_1$ 和 $r_2$ 是正则表达式，那么以下也是正则表达式：

• $r_1 + r_2$：表示 $r_1$ 和 $r_2$ 的并集，即 $L(r_1) \cup L(r_2)$。
• $r_1 \cdot r_2$：表示 $r_1$ 和 $r_2$ 的连接，，即由 $r_1$ 中的字符串后跟 $r_2$ 中的字符串组成的所有字符串的集合 $L(r_1)L(r_2)$。
• $r_1^*$：表示 $r_1$ 的克莱尼星号 (Kleene star)，即由 $r_1$ 中的字符串连接任意多次（包括零次）组成的所有字符串的集合。例如，如果 $L(r_1) = \{a\}$，那么 $L(r_1^*) = \{\lambda, a, aa, aaa, ...\}$。
• $(r_1)$：表示 分组，用于改变运算的优先级，或者使表达式更清晰。例如，$a(b+c)$ 表示语言 $\{ab, ac\}$，而 $ab+c$ 表示语言 $\{ab, c\}$​。

每个正则表达式都代表一个特定的语言：

• $L(\emptyset) = \{\}$ (空集)
• $L(\lambda) = \{\lambda\}$
• $L(a) = \{a\}$，对于每个 $a \in \Sigma$
• $L(r_1 + r_2) = L(r_1) \cup L(r_2)$
• $L(r_1 \cdot r_2) = L(r_1) L(r_2)$ （$L(r_1)$ 和 $L(r_2)$ 的连接）
• $L((r_1)) = L(r_1)$
• $L(r_1^*) = (L(r_1))^*$ （$L(r_1)$ 的克莱尼闭包）

为了避免歧义，正则表达式的运算符有以下优先级规则（和我们日常使用差不多）：

1. 克莱尼星号 ($*$) 优先级最高。
2. 连接 ($\cdot$) 优先级次之。
3. 并集 ($+$) 优先级最低。

例如，$a + b \cdot c$ 等价于 $a + (b \cdot c)$，而不是 $(a + b) \cdot c$。可以使用括号来显式地改变优先级。

正则表达式和非确定性有限自动机 (NFA) 在表达能力上是等价的。

对于任何正则表达式 $r$，存在一个 NFA $M$，使得 $L(M) = L(r)$。因此，$L(r)$ 是一个正则语言。

对于基本正则表达式 $\emptyset$, $\lambda$, 和 $a$，可以直接构造出简单的 NFA。对于复合正则表达式，可以通过组合其子表达式对应的 NFA 来构建。例如，

• 对于 $r_1 + r_2$，可以将 $r_1$ 和 $r_2$ 对应的 NFA 并联起来；
• 对于 $r_1 r_2$，可以将它们串联起来；
• 对于 $r_1^*$，可以添加 $\lambda$​ 转移来形成闭环

接下来，我们通过两个例子来说明他们之间的转换关系。

假设这是一个NFA的语言：$L = \{w \in \{0, 1\}\ \mid\ \text{w has exactly one pair of consecutive zeros} \}$

语言 $L$ 包含所有由 0 和 1 组成的字符串，且这些字符串中恰好有一对连续的 0。这意味着：

• 字符串中必须包含子串 00。
• 字符串中不能包含更多的 00 子串。

假设一个串中间为”00”，则前缀/后缀部分不能包含 00 和 10，因此前缀/后缀可以是任意数量的 1 或 01。所以可以写为：$(1+01)*00(1+01)*$

下面还有一个例子：给定字母表 $\Sigma = \{a, b, c\}$，正则表达式 $(a + b \cdot c)^* \cdot (c + \emptyset)$ 表示的语言是什么？

$(a + b \cdot c)^*$ 表示由 $a$ 或 $bc$ 组成的任意长度的字符串，$(c + \emptyset)$ 表示 $c$ 或空串。因此，整个正则表达式表示由 $a$ 或 $bc$ 组成的字符串，最后可能以 $c$​ 结尾。

Regular Languages#

上下文无关文法（Context-Free Grammar, CFG）是一种形式文法，其特点是每个产生式的左侧只有一个非终结符，右侧可以是任意长度的终结符和非终结符的组合，形式化定义如下：

$G = (V, T, S, P)$

• $V$：非终结符集合（变量）。
• $T$：终结符集合（字母表）。
• $S$：起始符号，$S \in V$。
• $P$：产生式规则集合，形式为 $A \rightarrow \alpha$，其中 $A \in V$，$\alpha \in (V \cup T)^*$。

CFG 的关键特征在于其产生式规则的形式。每个产生式规则的左侧必须只有一个非终结符。规则形式通常为 $A \rightarrow \alpha$，其中 $A \in V$，$\alpha \in (V \cup T)^*$ (由终结符和非终结符组成的任意字符串)。“上下文无关”意味着无论非终结符出现在何种上下文中，都可以应用该规则进行替换。

例如，这是一个 CFG 的规则: $S \rightarrow aSb \mid \lambda$ 表示非终结符 $S$ 可以被替换为 $aSb$ 或空串 $\lambda$，其中 $a$ 和 $b$ 是终结符，$S$ 是非终结符。

而正则文法 (Regular grammar) 是上下文无关文法的一个子集，它具有更严格的产生式规则形式。正则文法分为两种类型：

1. 右线性文法 (Right-Linear Grammar): 所有产生式规则都具有以下形式之一:

   • $A \rightarrow xB$
   • $A \rightarrow x$ 其中 $A, B \in Var$，而 $x \in T^*$ (由终结符组成的字符串)。也就是说，右侧最多出现一个变量B，且必须位于最右端。

2. 左线性文法 (Left-Linear Grammar): 所有产生式规则都具有以下形式之一:

   • $A \rightarrow Bx$
   • $A \rightarrow x$ 其中 $A, B \in Var$，而 $x \in T^*$。 也就是说，右侧最多出现一个变量B，且必须位于最左端。

一个文法如果既是右线性的又是左线性的，那么它生成的语言是正则语言 (Regular Language)。正则语言可以使用正则表达式、DFA 或 NFA 来描述，这四种描述方式是等价的。

线性文法是上下文无关文法的一个子集，其产生式规则中右侧最多只有一个非终结符，且没有位置限制，例如：

• $S \rightarrow aS\ |\ A$
• $A \rightarrow Ab\ |\ λ$

下面是一个例子：找到一个正则文法，该文法生成由{a,b}组成的偶数长度串的组成的语言。

假设是右线性文法，由偶数长度组成的串有如下可能：aa | ab | ba | bb，之后也不能加入其他的字符串了，所以文法可以是：$S \rightarrow aaS\ |\ abS\ |\ baS\ |\ bbS\ |\ λ$​

当然，如果是奇数长度的，我们可以在偶数的基础上修改为：$S \rightarrow aaS\ |\ abS\ |\ baS\ |\ bbS\ |\ a\ |\ b$，这是在之后直接偶数后加入一个字符为奇数。

Design DFA/NFA#

根据一个语言描述去设计DFA/NFA以识别特定语言的问题，是我们最常见的问题之一。以下是通用的解决方案：

1. 理解问题

• 明确语言的定义：例如，语言是否要求字符串中 a 的数量为偶数，或者是否包含特定子串 w。
• 确定输入符号：通常为 {a, b}，但也可以是其他符号。

2. 确定状态

• 状态表示：每个状态表示自动机在读取输入时的某种“记忆”。
• 状态数量：尽量使用最少的状态，以提高自动机的效率。

3. 确定转移函数

• 转移规则：根据输入符号和当前状态，确定下一个状态。
• 处理特殊情况：例如，如何处理未定义的输入符号。

4. 确定接受状态

• 接受条件：哪些状态表示字符串被接受。
• 拒绝条件：哪些状态表示字符串被拒绝。

常见的问题有：

1. 计数问题：偶数/奇数个 ‘a’ 和/或 偶数/奇数个 ‘b’

• 核心思想：状态表示奇偶性

  最基本的情况是只考虑一个字符的奇偶性，例如，设计一个DFA识别包含偶数个 ‘a’ 的字符串。我们需要两个状态：一个表示当前已读入偶数个 ‘a’，另一个表示已读入奇数个 ‘a’。

  当需要同时考虑 ‘a’ 和 ‘b’ 的奇偶性时，我们需要组合这些状态。例如，识别包含偶数个 ‘a’ 且 偶数个 ‘b’ 的字符串，我们需要四个状态，分别表示 (偶数 a, 偶数 b), (偶数 a, 奇数 b), (奇数 a, 偶数 b), (奇数 a, 奇数 b)。

• 状态转移

  根据读入的字符，在表示不同奇偶性的状态之间转移。例如，在“偶数 a，偶数 b”状态下读入 ‘a’，则转移到“奇数 a，偶数 b”状态。

• 起始状态和接受状态

  起始状态通常表示初始状态（例如，还未读入任何字符，‘a’ 和 ‘b’ 的计数都为零，即偶数）。

  接受状态取决于具体的要求。例如，对于“偶数个 ‘a’”，所有 ‘a’ 计数为偶数的状态都是接受状态。

2. 包含子串问题：至少包含一个子串 w

• 核心思想：状态跟踪匹配进度

  设计DFA的关键在于记住已经读入的、可能是目标子串前缀的部分。

  对于子串 “ab”，我们需要以下状态：

  • 初始状态：尚未匹配到任何部分。
  • 状态1：已读入 ‘a’。
  • 状态2：已读入 “ab”。

  当读入的字符与子串的下一个字符匹配时，状态向前推进。

• 状态转移

  • 如果当前状态表示已读入子串的前缀 P，并且下一个输入字符 c 使得 Pc 仍然是子串的前缀，则转移到表示 Pc 的状态。
  • 如果输入字符不匹配，则需要转移到一个表示最长已匹配前缀的状态。例如，在匹配 “aaab” 时，如果当前在 “aa” 状态读入 ‘b’，则转移到 “a” 状态，因为 “ab” 是 “aaab” 的一个前缀。

• 起始状态和接受状态

  起始状态是初始状态。接受状态是表示完整子串 w 的状态。一旦到达该状态，后续任何输入都可以保持在该状态，因为已经满足了“包含子串 w”的条件。

• 位置限制

  • 开头：DFA的结构会强制从起始状态开始匹配子串。
  • 结尾：在匹配到子串后，需要确保后续没有其他字符。这通常需要在匹配到子串的状态后，添加额外的状态来拒绝任何后续输入。
  • 中间：允许子串前后存在其他字符，一旦匹配到子串，就可以进入接受状态。

3. 不包含子串问题：不包含子串 w

• 核心思想：状态跟踪“不匹配”的状态

  这种问题可以转化为“在任何时候都不能形成子串 w”。

  我们可以构建一个类似于“包含子串 w”的DFA，但其接受状态是除了表示完整子串 w 之外的所有状态。

• 状态和转移

  状态和状态转移与“包含子串 w”的问题类似，用于跟踪可能形成 w 的前缀。

• 起始状态和接受状态

  起始状态是初始状态。接受状态是所有不是表示完整子串 w 的状态。一旦到达表示完整子串 w 的状态，就应该进入一个非接受的“错误”状态，并且后续任何输入都停留在该状态。

下面是一个例子，$L=\{w\in \{0,1\}^* \mid \text{start with 1, end with 0, contain 110}\}$

对于这样的一个问题，第一步先分析给出的条件：前缀为1，后缀为0，中间包含了110.

那么可以很快得出初始状态下对前缀的处理为：初始状态输入1进入q2，而输入0进入一个废弃状态q1. 当q2输入0的时候则打断了110的组合，此时重新计数，返回q0，输入1的话将继续转移到下一个状态。

下一步，进一步构造中间项110，直到接受状态。

最后，补充其他状态的转移情况，保证所有状态的转移都有对应。

Describe DFA/NFA#

如何用自然语言去描述所给的DFA/NFA的自动机转移图呢？核心在于理解自动机的结构和状态转移。我们可以采用如下步骤：

1. 观察状态和转移：分析 DFA/NFA 的状态和转移函数，理解其行为。
2. 确定接受状态：明确哪些状态是接受状态。可以找到5-10个可接受的答案，寻找规律。
3. 总结模式：根据状态和转移，总结出被接受字符串的共同特征。一般来说可以从前缀，中间字符串，后缀来看。实在找不到可以描述具体的答案，使用：like this .... or that ..... or that.....

下面是一个例子：

这是一个NFA，因为存在 λ 转移。起始状态是 q4，然后马上转移到q0，接受状态是 q3（双圈表示）。我们可以追踪从 q4 到 q3 的路径来找到被接受的字符串：

• q4 —λ—> q0 —0—> q1 —1—> q2 —0—> q3 => 010
• q4 —λ—> q0 —0—> q1 —0—> q2 —1—> q3 => 001
• q4 —0—> q4 —λ—> q0 —0—> q1 —1—> q2 —0—> q3 => 0010
• q4 —0—> q4 —λ—> q0 —0—> q1 —0—> q2 —1—> q3 => 0001
• q4 —1—> q4 —λ—> q0 —0—> q1 —1—> q2 —0—> q3 => 1010
• q4 —1—> q4 —λ—> q0 —0—> q1 —0—> q2 —1—> q3 => 1001
• q4 —0—> q4 —0—> q4 —λ—> q0 —0—> q1 —1—> q2 —0—> q3 => 00010
• q4 —0—> q4 —0—> q4 —λ—> q0 —0—> q1 —0—> q2 —1—> q3 => 00001

观察以上被接受的字符串，我们可以发现一些模式：

• 所有字符串都以 010 或 001 结尾。
• 在 010 或 001 之前可以有任意数量的 0 或 1（包括零个）。

根据以上分析，我们可以用自然语言描述该NFA接受的语言：该自动机接受所有由 '0' 和 '1' 组成的字符串，且这些字符串以子串 010 或 001 结尾。

NFA to DFA#

NFA 和 DFA 在识别语言能力上是等价的，任何 NFA 识别的语言都可以用某个 DFA 来识别。由于 DFA 的确定性，它更容易被实现。将 NFA 转换为 DFA 的常用方法是 子集构造法 (Subset Construction)。

它的核心思想是：DFA 的每个状态对应 NFA 的一个状态集合。

具体步骤如下：

1. 创建 DFA 的初始状态：DFA 的初始状态是 NFA 初始状态的 λ-闭包。λ-闭包指的是从某个状态出发，不读取任何输入符号（只通过λ-转移）能够到达的所有状态的集合。
2. 生成 DFA 的状态和转移：
   • 对于当前 DFA 的每个状态（一个 NFA 状态的集合），以及输入字母表中的每个符号，计算从这个 NFA 状态集合出发，经过该符号可以到达的所有 NFA 状态的集合，作为 DFA 的新状态。
   • 如果新状态尚未存在于 DFA 中，则将其添加到 DFA 中。
3. 确定 DFA 的接受状态：如果 DFA 的某个状态包含 NFA 的任何一个接受状态，则该 DFA 状态也是接受状态。

下面通过一个例子来解释这个过程。有个NFA的图和定义如下：

• 状态：$\{q_0, q_1, q_2\}$
• 输入字母表：$\{a, b\}$
• 初始状态：$q_0$
• 接受状态：$\{q_1\}$
• 转移函数：
  • $\delta(q_0, a) = \{q_1\}$​
  • $\delta(q_0, b) = \emptyset$
  • $\delta(q_1, a) = \{q_1, q_2\}$​
  • $\delta(q_1, b) = \emptyset$
  • $\delta(q_1, \lambda) = \{q_2\}$
  • $\delta(q_2, a) = \emptyset$
  • $\delta(q_2, b) = \{q_0\}$

1. DFA 的初始状态: NFA 的初始状态是 $q_0$。 从 $q_0$ 出发，没有 $\lambda$ 转移可以直接到达其他状态。所以 DFA 的初始状态是 $\{q_0\}$。

2. 构建 DFA 的状态和转移: 我们从 DFA 的初始状态开始，逐步构建 DFA 的其他状态和转移。对于 DFA 的每个已存在的状态（一个 NFA 状态的集合），以及输入字母表中的每个符号，我们计算从该状态出发，经过该符号转移后能够到达的 NFA 状态的集合，并将这个集合作为 DFA 的一个新状态。

   1. 从 DFA 状态 $\{q_0\}$ 出发：读取输入符号 $a$：$\delta_N^*( \{q_0\}, a ) = \{q_1, q_2\}$。它能到达$q_1$，随后可以通过 $\lambda$ 转移到达状态 $q_2$。我们创建 DFA 的一个新状态 $S_1 = \{q_1, q_2\}$，并添加从 $\{q_0\}$ 到 $\{q_1, q_2\}$ 的标有 $a$ 的转移。读取输入符号 $b$: $\delta_N^*( \{q_0\}, b ) = \emptyset$。我们创建 DFA 的一个新状态 $S_2 = \emptyset$，并添加从 $\{q_0\}$ 到 $\emptyset$ 的标有 $b$​ 的转移。

      

   2. 从 DFA 状态 $\{q_1, q_2\}$ 出发：在NFA中，$\delta(q_1, a) = \{q_1, q_2\}$, $\delta(q_2, a) = \emptyset$. 读取输入符号 $a$：$\delta_N^*( \{q_1, q_2\}, a ) = \{q_1, q_2\}$。（即集合中每个状态分别的转移函数的交集）转移到已存在的 DFA 状态 $\{q_1, q_2\}$。在NFA中，$\delta(q_1, b) = \emptyset$, $\delta(q_2, b) = \{q_0\}$。读取输入符号 $b$：$\delta_N^*( \{q_1, q_2\}, b ) = \{q_0\}$。转移到已存在的 DFA 状态 $\{q_0\}$​。

      

   3. 从 DFA 状态 $\emptyset$ 出发：读取输入符号 $a$：$\delta_N^*( \emptyset, a ) = \emptyset$。 转移到自身。读取输入符号 $b$：$\delta_N^*( \emptyset, b ) = \emptyset$​​。 转移到自身。

      

3. 确定 DFA 的接受状态: NFA 的接受状态是 $\{q_1\}$​。DFA 的接受状态是所有包含 NFA 至少一个接受状态的 DFA 状态。因此，DFA 的接受状态是：$\{q_1, q_2\}$​

在这个转换过程中，我们首先确定了DFA 的初始状态：NFA 初始状态的 λ-闭包 （只通过λ-转移能够到达的所有状态的集合）。接下来从初始状态开始，一步步构建 DFA 的状态和转移。基本原则是上一状态集合的所有子状态在NFA中的最大转换结果（包含 $\lambda$ 转换）的并集。最后，确定 DFA 的接受状态：是所有包含 NFA 至少一个接受状态的 DFA 状态。

Write the regular expression#

我们可以通过如下的步骤去分解语言到正则表达式：

1. 理解语言的定义：检查语言是否要求字符串以特定子串开头或结尾，或者是否包含特定模式。确定输入符号，通常为 {0, 1}/{a, b}或其他符号。

2. 分解语言：将语言分解为多个部分，开头部分、中间部分和结尾部分。分别设计正则表达式, 为每个部分设计正则表达式，然后将它们组合起来。

3. 组合正则表达式：使用正则表达式运算符：

   • +：表示“或”。

   • *：表示“零次或多次”。

   • .：表示“连接”（可以省略）。

   • λ/ε：表示空字符串。

4. 最后考虑到有没有前后重复覆盖的情况，特例的情况。例如前缀中已经包含了后缀的，需要在后面添加这个特例。

下面是一个例子：$L=\{w\ |\ w \in \{0, 1\}^*,\ \text{w start with 110 or 00 or 0, end with 0} \}$

第一步我们分解这个语言，将其分为开头，中间和结尾三个部分：

• 开头部分：字符串以 110 或 00 或 0 开头。
• 中间部分：可以是任意数量的 0 或 1。
• 结尾部分：字符串以 0 结尾。

接下来就是分别给他们设计正则表达式：

• 开头：110 或 00 或 0 可以表示为 (110 + 00 + 0)。
• 中间: 任意数量的 0 或 1 可以表示为 (0 + 1)*。
• 结尾：以 0 结尾可以表示为 0。

将这几部分连接在一起，得到：(110 + 00 + 0)(0 + 1)*0

我们并没有考虑到如果开头的这几种情况直接接受了，所以补上一个特殊情况得到：(110 + 00 + 0)(0 + 1)*0 + (110 + 00 + 0)

当然，我们在考虑中间项和结尾的正则表达式时，也可以使用空字符串表示，这样可以得到：(110 + 00 + 0)(λ/ε + (0 + 1)*0)

Computation Tasks#

编译器有几个重要阶段：词法分析器（Scanner），语法分析器（Parser），语义分析器（Semantic Analyzer）和代码生成器（Code Generator）。

1. 词法分析器 (Scanner)

• 输入 (Input): 词法分析器的输入是文本文件 (text file)，也就是源代码文件。

• 输出 (Output): 词法分析器的输出是词法单元列表 (linked list of tokens)。每个词法单元代表源代码中的一个有意义的单元，例如关键字、标识符、运算符、常量等。

• 主要数据结构 (Main data structure): 词法分析器在内部可以使用确定有限自动机 (DFA) 来进行计算。DFA 可以有效地识别源代码中的词法单元。此外，为了检测括号是否匹配，可以使用栈 (stack) 这种数据结构。当遇到左括号（[, {, (）时，将其压入栈中；当遇到右括号时，从栈顶弹出元素并检查是否匹配。

• 可能出现的错误 (Errors that can be found): 词法分析器主要负责识别源代码中的非法字符或不符合词法规则的模式。一个例子是在 C 语言中使用了不允许的字符，例如 @xy。 另一个例子是括号不匹配，例如 (] 或 {)。

2. 语法分析器 (Parser)

• 输入 (Input): 语法分析器的输入是词法单元列表 (token list)，这是词法分析器的输出。

• 输出 (Output): 语法分析器的输出是语法分析树 (parse tree)。语法分析树以树状结构表示源代码的语法结构，它反映了词法单元之间的层次关系。

• 主要数据结构 (Main data structure): 语法分析树的节点 (node) 是其主要的数据结构。每个节点代表一个语法结构，例如表达式、语句等。节点的具体结构取决于所使用的语法分析方法。

• 可能出现的错误 (Errors that can be found): 语法分析器负责检查词法单元序列是否符合编程语言的语法规则。常见的错误包括语法错误，例如 while ( ) x >y; y = x / ; 中缺少条件表达式或运算符。

3. 语义分析器 (Semantic Analyzer)

• 输入 (Input): 语义分析器的输入是语法分析树 (parse tree)，这是语法分析器的输出。
• 输出 (Output): 语义分析器的输出是带有语义信息的语法分析树或者中间表示形式。 这通常包括类型信息、符号表信息等。
• 主要数据结构 (Main data structure): 符号表 (symbol table) 是语义分析器最重要的数据结构之一。符号表用于存储程序中使用的标识符的信息，例如变量名、函数名、类型、作用域等。符号表通常以哈希表 (hash table) 的形式实现，以便快速查找。
• 可能出现的错误 (Errors that can be found): 语义分析器负责检查程序的语义是否正确，例如类型不匹配、未声明的变量、函数调用参数不匹配等。

4. 代码生成器 (Code Generator)

• 输入 (Input): 代码生成器的输入是带有语义信息的语法分析树或者中间表示形式，这是语义分析器的输出。
• 输出 (Output): 代码生成器的输出是目标代码 (target code)。目标代码可以是汇编代码、机器代码或者其他中间语言。
• 主要数据结构 (Main data structure): 代码生成器可能需要维护一些数据结构来管理寄存器分配、内存分配等信息。
• 可能出现的错误 (Errors that can be found): 代码生成器可能遇到的错误包括无法分配寄存器、目标平台不支持的操作等。例如，对于一个简单的加法操作 x + y，代码生成器会生成相应的汇编指令，例如 add r2, r2, r3。

常见的输出有：List of Tokens (Scanner), Parse Tree (Parser), Symbol Table (Semantic Analyzer)，下面是一些例子用于表示他们。

对于一个if语句，如下：

1
if (x > y) {
2
    x = 1;
3
    x = x + y;
4
}

我们可以很快得到如下的语法树：

1
      if_stmt
2
        / \
3
  (x > y)  cmpd_stmt
4
=>
5
      if_stmt
6
       /   \
7
     >     cmpd_stmt
8
   /  \       |
9
 x     y      =     <--->   =
10
             / \           / \
11
            x   1         x   =
12
                             / \
13
                            x   y

其中，我们把if的语句分成了左右两个部分，分别是判断的语句和复合的处理语句。接下来再对它们进行细分。在每一项中，采用中序遍历（左根右） 的形式写出这个树。其中，<--->展示兄弟姊妹关系。

而对于Symbol Table，它是一个链表数组，数组是一个哈希数组，链表中记录着每一个名字的定义。然后链表的节点中又有一个链表去记录该名字的其他信息，例如行数等，如下例子：

1
array of buckets
2
[]
3
[]
4
[]             bucketListRec
5
[]---{}---{}---{x}---{}
6
[]              \()
7
                 \() lineListRec.
8
                  \()

其中，这里的哈希数组可以嵌套，例如我们可以给一个作用域一个Symbol Table，作用域内的作用域嵌套Symbol Table。

Interpreter vs Compiler#

还有一个常见的问题是：解释器（Interpreter）和编译器（Compiler） 的相同点和区别。

相同点 (Similarities)

• 都是翻译器 (Both are translators): 解释器和编译器本质上都是翻译器，它们都将源代码（通常是高级语言）转换为另一种形式。
• 都需要进行词法分析，语法分析，语义分析等步骤: 无论是解释器还是编译器，都需要对源代码进行词法分析，语法分析，语义分析等步骤，以理解源代码的结构和含义。

区别 (Differences)

简单来说：

• 编译器将整个程序翻译成机器可以理解的目标代码，然后执行。
• 解释器逐行或逐语句翻译并执行代码。

Boot Strapping#

我们的目标是产生一个效率高的编译器，如下表示：

1
Goal: (X:[all] --> M:[high] ) / M:[high]

自举的过程通常包含以下几个步骤：

1. 写一个简单的编译器

   我们首先需要用高级语言 (X) 编写一个编译器 (1)。 这个编译器可以把一种高级语言 (X) 高效地翻译成机器语言 (M)。这个编译器 (1) 的描述可以表示为：

1
(1): (X:[all] --> M:[high] ) / X: (correct & high)

• X 表示输入语言，M 表示输出语言。
• X:[all] 表示这个编译器可以处理所有用 X 语言编写的程序。
• M:[high] 表示生成的机器代码的质量较高（效率较高）。
• / X: (corrent & high) 表示编译器 (1) 本身是用 X 语言编写的，且质量也较高。

这个编译器是用于生成与编译器相同的高级语言的翻译的。

2. 用 X 语言编写一个更强大的编译器

   接下来，我们使用机器语言去编写一个简单的编译器 (2)。 这个编译器 (2) 可以把编译器 (1)的代码翻译成机器语言 M。这个编译器 (2) 的描述可以表示为：

1
(2) (X:[only for (1)] --> M:[low] ) / M: (correct & low)

• X:[only for (1)] 表示这个编译器只能处理特定的 X 语言程序，即编译器 (1) 的源代码。
• M:[low] 表示生成的机器代码的质量较低（效率较低）。
• / M: (correct & low) 表示编译器 (2) 本身是用机器语言编写的，且效率和质量也较低。

这个编译器 (2) 的目标是能够编译步骤 1 中的编译器 (1) 的源代码。所以，即使编译器 (2) 本身功能不强，但只要能编译编译器 (1) 就足够了。

3. 运行编译器 (2) 编译编译器 (1)

   现在，我们使用编译器 (2) 去编译编译器 (1) 的代码。 这会生成一个新的编译器 (3)，它的描述可以表示为：

1
(3) (X:[all] --> M:[high] ) /M:[low]

• 这个编译器 (3) 的功能是去编译编译器 (1) 的代码，所以保持编译器 (1) 的输入输出，并保持编译器 (2) 的body。
• M:[low] 表示编译器 (3) 本身是用机器语言编写的，且质量较低。

编译器 (3) 是用机器码，因为此时是使用了编译器(2)编译的，所以编译编译器 (1) 的效率是低的。这是在低效地生成可直接运行的高效编译器 (1).

1. 用编译器 (3) 编译编译器 (1)

   运行编译器 (3)，并将编译器 (1) 的源代码再次作为输入。这将生成最终的编译器 (4)

1
(4) (X:[all] --> M:[high] ) /M:[high]

• 这个编译器 (4) 的功能和编译器 (1) 相同，即把 X 语言翻译成 M 语言，并且可以处理所有用 X 语言编写的程序。

• M:[high] 表示编译器 (4) 本身是用机器语言编写的，且质量也较高。 编译器 (3) 编译了编译器 (1)，生成了一个高效的编译器 (4)，因为 (1) 在 X 下是高效的，直接运行 (4) 便是高效地编译原语言 X。

通过以上步骤，我们成功地使用一个简单的编译器 “自举” 出一个更强大的编译器 (4) 去翻译这个 X。

Hashing#

在编译器中的语义分析器Semantic Analyzer，我们使用哈希表作为Symbol Table，哈希函数将字符串转换成数字的下标进行存储，常见的哈希函数如下：

1
#define SIZE ... // 哈希表的大小
2
int hash (char * key) {
3
    int val = 0;
4
    int i = 0;
5
    while (key[i] != '\0'){
6
        val = ((val << 4) + key[i]) % SIZE;  // 相当于将哈希值乘以 16, 然后加上当前字符的 ASCII 值, 最后取模
7
        i ++;
8
    }
9
    return val;
10
}

Design Grammar for Language#

如何设计一个尊重运算符优先级和结合性的语法呢？

设计方法遵循：

1. 将高优先级的运算符放在语法规则的较低层级。
2. 运算符结合性决定了相同优先级的运算符的计算顺序。

例如：对于一个支持加法、减法、乘法和除法的语法。

1
expr   -> expr addop term | term    // 加法和减法，优先级较低。
2
term   -> term mulop factor | factor    //乘法和除法，优先级较高。
3
factor -> NUMBER | ( expr )    // 处理数字和括号表达式。
4
addop  -> + | -
5
mulop  -> * | /

例如：3 + 5 * 2

1
    +
2
   / \
3
  3   *
4
     / \
5
    5   2

乘法节点 * 位于加法节点 + 的下方，表示乘法先计算。

还有一个例子是一个支持幂运算的语法，幂运算是右结合的。

1
expr   -> term addop expr | term
2
term   -> factor mulop term | factor
3
factor -> power | NUMBER | ( expr )
4
power  -> NUMBER powop power | NUMBER    // 处理幂运算，通过右递归实现右结合性。
5
powop  -> ^

对于2 ^ 3 ^ 2，幂运算节点 ^ 是右结合的，因此 3 ^ 2 先计算，再计算 2 ^ (3 ^ 2)。

1
    ^
2
   / \
3
  2   ^
4
     / \
5
    3   2

此外还有逻辑与、逻辑或这样的类似语法，逻辑与优先级高于逻辑或。

Write Parse Functions#

给定一个语句，我们需要写出自顶向下的Parse Function 去生成这样的Parse Tree。

1. 创建节点：在函数开始时，创建一个表示当前非终结符的语法树节点。

   例如：Node *result = newNode("while");

2. 匹配终结符：对于产生式右部的每个终结符，使用 checkMove 或类似的函数检查当前输入的词法单元是否匹配。如果匹配，则移动到下一个词法单元；如果不匹配，则报告语法错误。 例如：在解析 while 语句时，需要匹配 WHILE 关键字和左右括号，我们使用顺序遍历每个需要解析的单元。

   1
   if (checkMove(WHILE)) {
   2
        if (checkMove(LPAR)) {
   3
            ...
   

3. 调用非终结符对应的函数：对于产生式右部的每个非终结符，调用相应的解析函数来解析该非终结符。被调用函数返回的语法树节点成为当前节点的子节点。

   例如：while 语句的语法规则中包含 expression 和 statement 两个非终结符，需要调用相应的解析函数

   1
   if((result->child[0] = expression(f, &s)) , s == TRUE)
   

4. 处理错误：在任何匹配或解析失败时，报告语法错误，并进行适当的错误处理（例如，同步到下一个可能正确的词法单元）。

5. 返回节点：如果解析成功，则返回创建的语法树节点；如果失败，则返回 NULL 或指示错误的值。

6. 维护状态：使用状态变量来指示解析是否成功

例子在Parser处。

Building a Symbol Table#

符号表通常被组织成一个由桶 (buckets) 组成的数组，每个桶可以链接一个记录列表 (BucketListRec)。 为了处理作用域 (scope)，每个符号表可能会有一个指向其父作用域符号表的链接 (parent)。 这种结构可以有效地支持符号的查找和管理，特别是对于存在嵌套作用域的语言。

构建符号表通常在语义分析阶段进行，并且通常使用对抽象语法树 (AST) 的先序遍历 (pre-order traversal) （根左右，因为先声明后使用）。以下是构建符号表的主要步骤：

1. 创建顶层作用域的符号表: 在开始遍历语法树之前，首先为全局作用域创建一个符号表，并将其设置为当前符号表。
2. 先序遍历语法树: 从语法树的根节点开始进行先序遍历。对于遍历到的每个节点，执行以下操作：
   • 遇到声明: 如果当前节点表示一个声明（例如，变量声明、函数声明），则检查该符号是否已经在当前作用域中声明过。
     • 如果已经声明过，则报告重复声明错误。
     • 如果没有声明过，则创建一个新的符号表条目（BucketListRec），并将符号的相关信息（例如，符号名、类型、作用域等）存储在该条目中。然后将该条目插入到当前符号表中对应的桶中。 同时，将该符号表条目的地址关联到语法树节点。
   • 进入新的作用域: 如果当前节点引入一个新的作用域（例如，函数声明、复合语句），则创建一个新的符号表，并将当前符号表的 parent 指针指向旧的符号表，然后将新的符号表设置为当前符号表。
   • 离开作用域: 当完成对一个作用域内所有节点的处理后（在先序遍历的相应返回点），将当前符号表恢复为父符号表。

下面是一个检查是否声明的例子：

1
BucketListRec *lookup(const char *name, SymbTab *tb) {
2
    int v = hash(name);
3
    BucketListRec *p = searchInBucket(name, tb->array[v]);    // 在指定的桶中查找符号
4
    while (p == NULL && tb != NULL) {    // 没找到
5
        tb = tb->parent;    // 查找父符号表
6
        p = searchInBucket(name, tb->array[hash(name)]);
7
    }
8
    return p;
9
}

Type Checking#

类型检查是编译器语义分析阶段的一个重要组成部分。它的主要目标是验证程序中的操作是否符合语言的类型规则，从而确保程序在运行时不会出现类型错误。

类型检查通常在构建符号表之后进行，并且通常使用对抽象语法树 (AST) 的后序遍历 (post-order traversal) （左右根，因为先检查子类型）

1. 后序遍历语法树: 从语法树的叶子节点开始进行后序遍历。对于遍历到的每个节点，执行以下操作：
   • 基本类型: 如果当前节点表示一个常量或标识符，则根据其字面值或符号表中的信息确定其类型。
   • 表达式: 如果当前节点表示一个表达式，则根据其子节点的类型和运算符的类型规则来推断当前表达式的类型。
     • 例如，对于一个二元运算表达式 E1 op E2，首先递归地检查 E1 和 E2 的类型。然后，根据运算符 op 的定义，检查 E1 和 E2 的类型是否与 op 兼容。 如果兼容，则确定整个表达式的类型；否则，报告类型错误。
   • 语句: 如果当前节点表示一个语句，则检查语句中涉及的表达式的类型是否符合语句的语义规则。
     • 例如，对于赋值语句 variable = expression，需要检查 expression 的类型是否与 variable 的类型兼容2。
     • 对于函数调用，需要检查实际参数的类型和数量是否与函数声明的形式参数匹配。
   • 类型等价性: 在类型检查过程中，经常需要判断两个类型是否相同。类型等价性的判断可以有多种方式，例如名称等价 (name equivalence) 和 结构等价 (structural equivalence)。
2. 错误报告: 如果在类型检查过程中发现任何违反类型规则的情况，编译器将报告类型错误。