1. COMS W3261 Fall 2024 Midterm Review

这部分是文档的标题和作者信息。

• COMS W3261 Fall 2024 Midterm Review: 这明确了文档的性质和所属课程。
• COMS W3261: 这是课程编号，代表“计算机科学理论”（Computer Science Theory）这门课程。COMS 是哥伦比亚大学计算机科学系课程的通用前缀。W3261 是课程的具体编号，通常 W 开头的课程表示主要面向本科生。
• Fall 2024: 这表示文档适用于2024年秋季学期。
• Midterm Review: 这说明文档内容是为期中考试准备的复习材料。
• Yizhi Huang 和 Owen Terry: 这两位是这份复习资料的作者，很可能是课程的助教（TA）或讲师。
• 2024年10月14日: 这是文档的发布或最后修订日期。这个日期很重要，因为它告诉学生这份资料是在期中考试前某个时间点创建的，内容具有时效性。

这部分详细说明了期中考试的考察范围和一些重要的考试规则。

• “期中考试将涵盖截至第9讲（2024-10-03）课堂上显示的所有材料，除非讲师另有明确说明。”
• 第9讲（2024-10-03）: 这是一个明确的时间节点，界定了考试内容的截止范围。所有在这之前课堂上讲过的内容都可能成为考点。
• “课堂上显示的所有材料”: 这包括讲义（slides）、板书、口头讲解等。
• “除非讲师另有明确说明”: 这是一个免责声明，强调最终解释权在讲师手中。如果讲师在后续课程或通知中更改了考试范围，应以最新通知为准。

• “具体来说，对于上下文无关语言（CFL），不会有深奥的问题，因为它从未在测验或作业中出现过。”
• 上下文无关语言 (Context-Free Language, CFL): 这是计算理论中的一个核心概念，比正则语言更复杂。
• “不会有深奥的问题”: 这句话给学生吃了一颗定心丸。它表明虽然 CFL 在概念上可能已经被介绍过，但考试不会涉及复杂的证明或深入的应用。考察形式可能仅限于基本定义或简单的判断。
• “因为它从未在测验或作业中出现过”: 这解释了为什么不会考得太深。课程的评估设计通常是一致的，作业和测验是考试的风向标。既然之前没有练习过，考试也不会突然增加难度。

• “你可以直接使用课堂上给出的定理和例子而无需证明，但你必须明确说明它们是课堂上给出的。”
• “直接使用...而无需证明”: 这是一条非常重要的规则，可以大大节省考试时间。例如，在证明某个语言是正则的时，如果用到“正则语言在并集下是封闭的”这个定理，你不需要在试卷上重新证明这个定理本身。
• “但你必须明确说明”: 这是使用该规则的前提。你必须写清楚你引用的是哪个课堂上讲过的定理。例如，可以写“根据课堂上讲过的正则语言的并集封闭性...”。

• “请记住，你可以携带 2 张双面信纸大小的纸张。”
• 这指的是所谓的“cheat sheet”或参考纸。这是一个重要的考试策略信息。
• “2 张双面信纸大小”: 这明确了参考纸的数量和规格。信纸大小（Letter size）是北美常用标准，约为8.5 x 11英寸。双面意味着总共有4面的空间。
• “所以你不需要背诵东西，但理解定义和概念很重要。”: 这句话指明了参考纸的正确用法。它不是用来代替学习的，而是用来存放公式、定义、标准构造方法等记忆性内容的。考试的核心在于考察你是否能“理解”并“运用”这些知识来解决问题。

• “测验和作业的解答已发布在 Courseworks 上。”
• Courseworks: 这是哥伦比亚大学使用的课程管理系统平台名称（类似 Blackboard, Canvas）。
• 这句话提醒学生，复习时最重要的资料之一就是过去的作业和测验及其标准答案。

• “助教们从未见过真正的期中试卷，也不会在你们看到之前看到它。”
• 这是一个诚信和公平性声明。它告诉学生，助教编写的这份复习资料是基于他们对课程内容的理解，而不是基于他们提前看到了考题。因此，学生不应该期望这份复习资料能“押中”原题。

• “2 要点总结”: 这是本章节的标题，预示着接下来会是对期中考试核心知识点的梳理和浓缩。
• “请参阅课程网页上的讲义，了解更详细的复习和示例问题。”: 这是一个引导性说明。它提醒读者，这个“要点总结”只是一个大纲或索引，它不能替代详细的课程讲义。要想深入理解和掌握所有细节、看到更多的例题，还是需要回到原始的学习材料中去。这是一种免责，也是一种正确的学习方法指导。

本节介绍计算理论中最基础、最核心的三个概念：字母表、字符串和语言，以及一个重要的符号表示法。这些是后续所有理论的基石。

• “字母表是一个有限的非空字符集合。”
• 字母表 (Alphabet): 在计算理论中，字母表通常用希腊字母 $\Sigma$ (Sigma) 表示。它是一组“原子”符号的集合。
• 有限的 (finite): 字母表中的符号数量必须是有限的，比如 $\{0, 1\}$，$\{a, b, c\}$。你不能有一个包含无限个符号的字母表。
• 非空 (non-empty): 字母表里必须至少有一个符号。一个空的字母表是无意义的，因为它无法构成任何字符串。
• 字符 (characters/symbols): 这里的“字符”是广义的，可以是数字、字母、甚至其他符号，只要它们是明确区分的单个元素即可。

• “（在某个字母表上的）字符串是该字母表中字符的有限序列。”
• 字符串 (String): 字符串是由字母表中的符号拼接而成的序列。
• 有限序列 (finite sequence): 字符串的长度必须是有限的。计算理论通常不讨论无限长的字符串。
• 序列 (sequence): 顺序很重要。如果字母表是 $\Sigma = \{a, b\}$，那么字符串 "ab" 和 "ba" 是两个不同的字符串。

• “（在某个字母表上的）语言是该字母表中字符串的集合。（语言不一定是有限的。）”
• 语言 (Language): 一个语言是一个字符串的集合。这个集合是字母表上所有可能字符串的集合（记作 $\Sigma^*$, 读作 "Sigma star"）的一个子集。
• “语言不一定是有限的”: 这是非常关键的一点。一个语言可以包含有限个字符串，例如 $L_1 = \{ "01", "10" \}$。也可以包含无限个字符串，例如 $L_2 = \{ \text{所有以0开头的字符串} \}$。计算理论的主要研究对象之一就是如何描述和识别这些无限的语言。

• “对于一个字符或字符串 $x, k \geq 0, x^{k}$ 是字符串 $x \circ x \circ \cdots \circ x$，其中 $x$ 重复 $k$ 次。特别地，$x^{0}$ 是空字符串 $\varepsilon$。（这里它不具有“$x$ 的 $k$ 次幂”的含义。）”
• $x^k$: 这被称为字符串的幂 (power) 运算，但更准确的理解是重复连接 (concatenation)。
• $x$: 这里的 $x$ 可以是单个字符，也可以是一个字符串。
• $k \geq 0$: 重复的次数 $k$ 是一个非负整数。
• $\circ$: 这个符号代表字符串的连接 (concatenation) 操作，通常是省略不写的。例如 "ab" $\circ$ "cd" 就是 "abcd"。
• $x^0 = \varepsilon$: 这是一个非常重要的定义。任何字符串的0次重复都是空字符串 $\varepsilon$ (epsilon)。空字符串是指不包含任何字符的、长度为0的字符串。
• “不具有‘$x$ 的 $k$ 次幂’的含义”: 这是一个提醒，避免与数字的幂运算混淆。$10^2$ 是 100，但如果 '10' 是一个字符串，那么 $('10')^2$ 是 "1010"。

这一节定义了计算理论的第一个主要语言类别——正则语言 (Regular Languages)，并阐述了其核心特征。

• “一个语言是正则的，当且仅当它可以被以下之一识别：”
• 正则 (Regular): 这是对一类语言的称谓。这类语言具有一个非常好的特性：它们的结构相对简单，可以用非常有限的计算资源（如有限的内存）来判断一个字符串是否属于该语言。
• 当且仅当 (if and only if): 这是一个非常强的逻辑声明，意味着以下列出的三个条件是完全等价的。如果一个语言满足其中任何一个条件，它就必然满足另外两个。这三者共同定义了什么是正则语言。
• 识别 (recognize): 这里的“识别”意味着一个计算模型（如 DFA 或 NFA）或者一个描述（如正则表达式）能够精确地描述这个语言所包含的所有字符串，不多也不少。

• - 一个 DFA $\left(Q, \Sigma, \delta, q_{0}, F\right)$。
• DFA (Deterministic Finite Automaton): 确定性有限自动机。它是一个数学模型，可以想象成一个简单的流程图。
• $Q$: 一个有限的状态 (states)集合。
• $\Sigma$: 输入字母表。
• $\delta$: 转移函数 (transition function)。它告诉你在当前状态下，读到一个输入字符后，应该转移到哪一个“唯一”的下一个状态。这是“确定性”的体现。$\delta: Q \times \Sigma \to Q$。
• $q_0$: 起始状态 (start state)，是 $Q$ 中的一个特殊状态。
• $F$: 接受状态 (accept/final states)的集合，是 $Q$ 的一个子集。
• DFA 识别一个语言意味着，所有属于该语言的字符串输入到 DFA 后，DFA 最终会停在一个接受状态；而所有不属于该语言的字符串输入后，最终会停在一个非接受状态。

• - 一个 NFA $\left(Q, \Sigma, \delta, q_{0}, F\right)$。
• NFA (Nondeterministic Finite Automaton): 非确定性有限自动机。它与 DFA 非常相似，但是更灵活。
• 其转移函数 $\delta$ 的不同之处在于：

1. 从一个状态读入一个字符，可以转移到“多个”下一个状态。
2. 允许空转移 (epsilon transitions)，即不读入任何字符就可以从一个状态跳转到另一个状态。
   • NFA 的转移函数形式为 $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$，其中 $\mathcal{P}(Q)$ 是 $Q$ 的幂集（所有子集的集合）。
   • NFA 接受一个字符串，只要存在“至少一条”从起始状态开始的、消耗掉整个字符串的路径，最终能到达一个接受状态。

• - 一个正则表达式。
• 正则表达式 (Regular Expression): 这是一种使用文本模式来描述语言的强大工具。它由字母表中的字符以及三个基本运算构成：

1. 并集 (Union): 用 | 或 + 表示，意为“或”。
2. 连接 (Concatenation): 直接写在一起，意为“然后”。
3. 星号闭包 (Kleene Star): 用 * 表示，意为“重复零次或多次”。

• “上述三种表示形式是等价的...”
• 等价 (Equivalent): 这是计算理论中一个里程碑式的结论（克林定理 Kleene's Theorem）。它意味着 DFA、NFA 和正则表达式 这三种看起来截然不同的工具，其描述能力是完全相同的。任何一个 DFA 能识别的语言，也一定能用 NFA 和正则表达式来描述，反之亦然。
• 转换方法:
• NFA 到 DFA (子集构造法 Subset Construction): 这是将一个 NFA 转换为等价 DFA 的标准算法。其核心思想是，DFA 的每一个状态对应 NFA 的一个状态集合。
• NFA 到 正则表达式 (GNFA 方法): 通过引入一个广义非确定性有限自动机 (Generalized Nondeterministic Finite Automaton, GNFA)，然后通过逐步状态移除 (state ripping/elimination) 的过程，最终得到一个等价的正则表达式。
• 正则表达式 到 NFA: 这是一个递归的构造过程（Thompson构造法），可以为任何正则表达式构建一个等价的 NFA。基本字符、并集、连接和星号都有对应的标准 NFA 模块，可以像搭积木一样组合起来。

• “请注意，具有正则性是语言的一种属性，我们不能说一个字符串是正则的或非正则的。”
• 这是一个非常重要的概念辨析。正则性是用来描述一个“字符串集合”（即语言）的特征的。一个单独的字符串，比如 "0011"，它本身谈不上正则或非正则。它可以属于一个正则语言（例如 $L_1 = \{ \text{所有0和1组成的字符串} \}$），也可以属于一个非正则语言（例如 $L_2 = \{0^n1^n \mid n \ge 0\}$，其中 $n=2$ 时就是 "0011"）。
• 这就好比说，“可被3整除”是整数的一个属性。我们可以说集合 $\{3, 6, 9, \dots\}$ 里的数都有这个属性。但对于单个数字“6”本身，我们说“6可以被3整除”，而不是说“6是可被3整除的”。

• “对于任何 DFA/NFA/正则表达式，恰好有一个由其识别的语言...然而，对于一个语言，可以有许多 DFA/NFA/正则表达式识别它。”
• 一对一关系: 一个具体的自动机或正则表达式，其定义的规则是死的，所以它能接受的字符串集合是唯一确定的。
• 多对一关系: 同一个语言（同一个字符串集合）可以用多种不同的方式来描述。例如，语言 $L = \{a\}$ 可以被一个两状态的 DFA 识别，也可以被一个三状态的 DFA 识别。正则表达式 $a(b|c)$ 和 $ab|ac$ 描述的是同一个语言。

本节系统地总结了证明一个语言是正则语言的几种常用策略。

• - 设计一个识别该语言的 DFA/NFA/正则表达式。
• 这是最直接、最根本的证明方法。根据正则语言的定义，只要你能成功构造出这三者中的任何一个，就直接证明了该语言的正则性。
• DFA (确定性有限自动机): 构造 DFA 通常需要更严谨的逻辑，因为每个状态对每个输入的转移都必须是唯一的。
• NFA (非确定性有限自动机): 构造 NFA 通常更简单、更直观，因为它允许“猜测”和“多路径”。在证明正则性时，构造 NFA 往往是首选，因为只要构造出来就足够了，不需要再转成 DFA。
• 正则表达式: 对于一些模式非常明显的语言，直接写出正则表达式是最快捷的方法。

• “注意，我们不仅需要证明...”
• 这是一个关于证明完备性的重要提醒。一个正确的构造性证明包含两个方向：

1. 正确性 (Soundness): 证明你构造的机器或表达式所接受的任何字符串，都确实属于目标语言 $L$。即 $L(\text{Machine}) \subseteq L$。
2. 完备性 (Completeness): 证明目标语言 $L$ 中的任何字符串，都确实能被你构造的机器或表达式接受。即 $L \subseteq L(\text{Machine})$。
   • 这两个条件合在一起，才能证明 $L(\text{Machine}) = L$。在实际答题中，虽然不总是要求写出严格的两个方向的归纳证明，但你在设计自动机或正则表达式时，必须在脑中验证这两个方面。

• - 使用封闭性 (Closure Properties)：...
• 这是一个更高级、更强大的证明技巧。它利用了“正则语言家族”的一个优良特性：正则语言经过某些运算后，其结果仍然是正则语言。这个特性被称为封闭性。
• 已知的封闭运算包括：
• 补集 (Complement): $\bar{L}$
• 交集 (Intersection): $L_1 \cap L_2$
• 并集 (Union): $L_1 \cup L_2$
• 连接 (Concatenation): $L_1 \circ L_2$
• Kleene 星号 (Kleene Star): $L^*$
• 证明思路是：将目标语言 $L$ 分解成一个或多个已知的正则语言，通过这些封闭运算组合而成。如果所有基础语言都是正则的，并且所有运算都是封闭的，那么最终结果 $L$ 也必然是正则的。

• “- 作为使用并集封闭性的一个特例，每个有限语言都是正则的。”
• 有限语言: 只包含有限个字符串的语言。
• 为什么是正则的？假设一个有限语言 $L = \{w_1, w_2, \dots, w_n\}$。对于其中任何一个字符串 $w_i$，语言 $\{w_i\}$ 显然是正则的（可以为它构造一个简单的链状 DFA，或者直接就是正则表达式 $w_i$）。因为 $L = \{w_1\} \cup \{w_2\} \cup \dots \cup \{w_n\}$，而正则语言在并集下是封闭的，所以 $L$ 是正则的。

• “- 为了证明对正则语言的一些新运算会导致正则语言...”
• 这部分讨论的是如何证明一个新的运算也是封闭的。例如，让你证明正则语言在 Reverse 运算（将语言中所有字符串反转）下是封闭的。
• 证明方法通常是构造性的：

1. 从 DFA/NFA 开始: 假设你有一个识别原始语言 $L$ 的 DFA 或 NFA。然后你对这个自动机进行一系列修改（比如，颠倒所有转移箭头，交换起始和接受状态），构造出一个新的 NFA，并证明这个新 NFA 恰好识别 Reverse(L)。
2. 从正则表达式开始: 对识别 $L$ 的正则表达式 $R$ 进行结构化修改，得到一个新的正则表达式 $R'$，并证明 $R'$ 识别 Reverse(L)。
3. 使用已知封闭性组合: 将新运算表达为已知封闭运算的组合。例如，交集的封闭性可以通过德摩根定律由并集和补集的封闭性证明：$L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$。既然正则语言在补集和并集下封闭，那么它们在交集下也必然封闭。

• “- Myhill-Nerode 定理...”
• Myhill-Nerode 定理: 这是一个更深刻的、关于正则语言的代数特性的定理。它提供了一个判断语言是否正则的充分必要条件。其核心思想是定义一个等价关系 $R_L$，如果由这个关系导出的等价类数量是有限的，那么语言 $L$ 就是正则的，并且等价类的数量恰好是识别 $L$ 的最小 DFA 的状态数。
• “这不属于期中考试要求的材料”: 这是一个明确的提示，告诉学生不需要花时间去深入学习这个定理用于期中考试。它在这里被提及是为了知识的完整性。

本节介绍了证明一个语言“不是”正则语言的两种主要方法：泵引理和封闭性。这通常比证明它是正则的要更复杂。

• - 泵引理 (Pumping Lemma)
• 核心思想: 泵引理描述了所有正则语言都必须具备的一个固有属性。这个属性源于 DFA 的内存有限性（状态数量有限）。如果一个正则语言包含足够长的字符串，那么在处理这些字符串时，DFA 必定会重复经过某个状态（形成一个环）。一旦有环，我们就可以沿着这个环“循环”任意次数（即“泵送”），产生一系列新的字符串，而所有这些新字符串也必须被 DFA 接受，因此也必须属于同一个正则语言。
• 引理的正式陈述:
• 如果 (IF) $L$ 是一个正则语言，
• 那么 (THEN) 存在一个泵长度 $p$ (通常是 DFA 的状态数)，
• 对于所有 (FOR ALL) 属于 $L$ 且长度至少为 $p$ 的字符串 $w$，
• 存在 (THERE EXISTS) 一种将 $w$ 分割成 $xyz$ 的方式，满足三个条件：

1. $|xy| \le p$ (第一个环路必须在前 $p$ 个字符内出现)
2. $|y| > 0$ (环路本身不能为空)
3. 对于所有 (FOR ALL) $i \ge 0$，字符串 $xy^iz$ (泵送 $y$ $i$ 次) 都必须在 $L$ 中。
   • 如何使用泵引理进行反证: 我们的目标是证明某个语言 $L$ 不是 正则的。我们使用反证法：
4. 假设 $L$ 是正则的。
5. 那么泵引理一定成立，存在某个泵长度 $p$。
6. 我们的任务是，针对这个任意的 $p$，找出一个“反例”。即，构造一个特殊的字符串 $w \in L$ 且 $|w| \ge p$。
7. 然后我们证明，无论这个 $w$ 如何被分割成满足条件 (1) 和 (2) 的 $xyz$，我们总能找到一个 $i \ge 0$ (通常 $i=0$ 或 $i=2$ 就够了)，使得泵送后的字符串 $xy^iz$ 不在 $L$ 中。
8. 这就产生了一个矛盾 (泵引理说 $xy^iz$ 必须在 $L$ 中，而我们证明了它不在)。
9. 因此，最初的假设“$L$是正则的”是错误的。结论：$L$ 不是正则的。

• 常见错误: 这部分指出了使用泵引理时新手易犯的错误，这实质上是一个“游戏”的策略指南。对手（代表泵引理）和我方（证明者）的博弈：
• 对手先出招：给一个任意的 $p > 0$。
• 我方出招：必须选择一个 $w \in L$ 且 $|w| \ge p$。这个 $w$ 的选择至关重要，通常要依赖于 $p$ (例如，选择 $w = a^p b^p$)。
• 没有构造一个对于所有 p>0 满足 |w|≥p 的字符串 w: 你的 $w$ 必须能应对任何 $p$。
• 没有构造一个在 L 中的字符串 w: 你的反例 $w$ 必须是语言内的成员。
• 对手再出招：将我方的 $w$ 以满足 $|xy| \le p$ 和 $|y| > 0$ 的所有可能方式进行分割。
• 我方最后一击：必须证明对于所有这些分割，我方都能找到一个 $i$ 来“泵出”一个不在 $L$ 中的字符串。
• 没有考虑解析 w=xyz 的每种可能方式: 这是最常见的错误。你不能只选择一种对你有利的分割来反驳。你必须证明所有合法的分割都会导致矛盾。这里的技巧是，利用 $|xy| \le p$ 这个条件，来限制 $y$ 的可能形式。例如，如果 $w = a^p b^p$，因为 $|xy| \le p$，所以 $y$ 必然只包含 $a$。
• 没有选择一个使得 xy^iz ∉ L 的 i: 你需要找到一个 $i$（比如 $i=0$ 或 $i=2$），使得泵送后的字符串破坏了语言 $L$ 的定义规则。

• - 使用封闭性 (反证法)
• 这是另一种强大的反证法。
• 思路:

1. 假设目标语言 $L$ 是正则的。
2. 将 $L$ 与一个或多个你已知是正则的语言 $L_{reg}$ 进行封闭运算（如交集、并集、补集等）。
3. 因为正则语言在这些运算下是封闭的，所以运算结果 $L_{new} = L \text{ op } L_{reg}$ 也必须是正则的。
4. 但是，如果你能证明 $L_{new}$ 实际上是一个你已知的非正则语言（比如 $\{0^n1^n \mid n \ge 0\}$），那么就产生了矛盾。
5. 这个矛盾说明，最初的假设“$L$是正则的”是错误的。结论：$L$ 不是正则的。

• - Myhill-Nerode 定理
• 再次提到这个定理，并指明它可以用来证明非正则性。方法是证明其可区分字符串的等价类有无限多个。
• 再次强调不属于期中考试范围。

• “泵引理是必要但不充分条件”
• 必要条件 (Necessary Condition): 如果一个语言是正则的，它必须满足泵引理。 (L is regular $\implies$ L satisfies Pumping Lemma)。
• 不充分条件 (Not Sufficient): 一个语言满足泵引理，并不能保证它就是正则的。 (L satisfies Pumping Lemma $\not\implies$ L is regular)。存在一些狡猾的非正则语言，它们恰好也能通过泵引理的测试。
• 这意味着，泵引理只能用来证明一个语言“不是”正则的（通过证明它不满足引理），但绝对不能用来证明一个语言“是”正则的。

本节介绍了证明一个语言“不是”正则语言的两种主要方法：泵引理和封闭性。这通常比证明它是正则的要更复杂。

• - 泵引理 (Pumping Lemma)
• 核心思想: 泵引理描述了所有正则语言都必须具备的一个固有属性。这个属性源于 DFA 的内存有限性（状态数量有限）。如果一个正则语言包含足够长的字符串，那么在处理这些字符串时，DFA 必定会重复经过某个状态（形成一个环）。一旦有环，我们就可以沿着这个环“循环”任意次数（即“泵送”），产生一系列新的字符串，而所有这些新字符串也必须被 DFA 接受，因此也必须属于同一个正则语言。
• 引理的正式陈述:
• 如果 (IF) $L$ 是一个正则语言，
• 那么 (THEN) 存在一个泵长度 $p$ (通常是 DFA 的状态数)，
• 对于所有 (FOR ALL) 属于 $L$ 且长度至少为 $p$ 的字符串 $w$，
• 存在 (THERE EXISTS) 一种将 $w$ 分割成 $xyz$ 的方式，满足三个条件：

1. $|xy| \le p$ (第一个环路必须在前 $p$ 个字符内出现)
2. $|y| > 0$ (环路本身不能为空)
3. 对于所有 (FOR ALL) $i \ge 0$，字符串 $xy^iz$ (泵送 $y$ $i$ 次) 都必须在 $L$ 中。
   • 如何使用泵引理进行反证: 我们的目标是证明某个语言 $L$ 不是 正则的。我们使用反证法：
4. 假设 $L$ 是正则的。
5. 那么泵引理一定成立，存在某个泵长度 $p$。
6. 我们的任务是，针对这个任意的 $p$，找出一个“反例”。即，构造一个特殊的字符串 $w \in L$ 且 $|w| \ge p$。
7. 然后我们证明，无论这个 $w$ 如何被分割成满足条件 (1) 和 (2) 的 $xyz$，我们总能找到一个 $i \ge 0$ (通常 $i=0$ 或 $i=2$ 就够了)，使得泵送后的字符串 $xy^iz$ 不在 $L$ 中。
8. 这就产生了一个矛盾 (泵引理说 $xy^iz$ 必须在 $L$ 中，而我们证明了它不在)。
9. 因此，最初的假设“$L$是正则的”是错误的。结论：$L$ 不是正则的。

• 常见错误: 这部分指出了使用泵引理时新手易犯的错误，这实质上是一个“游戏”的策略指南。对手（代表泵引理）和我方（证明者）的博弈：
• 对手先出招：给一个任意的 $p > 0$。
• 我方出招：必须选择一个 $w \in L$ 且 $|w| \ge p$。这个 $w$ 的选择至关重要，通常要依赖于 $p$ (例如，选择 $w = a^p b^p$)。
• 没有构造一个对于所有 p>0 满足 |w|≥p 的字符串 w: 你的 $w$ 必须能应对任何 $p$。
• 没有构造一个在 L 中的字符串 w: 你的反例 $w$ 必须是语言内的成员。
• 对手再出招：将我方的 $w$ 以满足 $|xy| \le p$ 和 $|y| > 0$ 的所有可能方式进行分割。
• 我方最后一击：必须证明对于所有这些分割，我方都能找到一个 $i$ 来“泵出”一个不在 $L$ 中的字符串。
• 没有考虑解析 w=xyz 的每种可能方式: 这是最常见的错误。你不能只选择一种对你有利的分割来反驳。你必须证明所有合法的分割都会导致矛盾。这里的技巧是，利用 $|xy| \le p$ 这个条件，来限制 $y$ 的可能形式。例如，如果 $w = a^p b^p$，因为 $|xy| \le p$，所以 $y$ 必然只包含 $a$。
• 没有选择一个使得 xy^iz ∉ L 的 i: 你需要找到一个 $i$（比如 $i=0$ 或 $i=2$），使得泵送后的字符串破坏了语言 $L$ 的定义规则。

• - 使用封闭性 (反证法)
• 这是另一种强大的反证法。
• 思路:

1. 假设目标语言 $L$ 是正则的。
2. 将 $L$ 与一个或多个你已知是正则的语言 $L_{reg}$ 进行封闭运算（如交集、并集、补集等）。
3. 因为正则语言在这些运算下是封闭的，所以运算结果 $L_{new} = L \text{ op } L_{reg}$ 也必须是正则的。
4. 但是，如果你能证明 $L_{new}$ 实际上是一个你已知的非正则语言（比如 $\{0^n1^n \mid n \ge 0\}$），那么就产生了矛盾。
5. 这个矛盾说明，最初的假设“$L$是正则的”是错误的。结论：$L$ 不是正则的。

• - Myhill-Nerode 定理
• 再次提到这个定理，并指明它可以用来证明非正则性。方法是证明其可区分字符串的等价类有无限多个。
• 再次强调不属于期中考试范围。

• “泵引理是必要但不充分条件”
• 必要条件 (Necessary Condition): 如果一个语言是正则的，它必须满足泵引理。 (L is regular $\implies$ L satisfies Pumping Lemma)。
• 不充分条件 (Not Sufficient): 一个语言满足泵引理，并不能保证它就是正则的。 (L satisfies Pumping Lemma $\not\implies$ L is regular)。存在一些狡猾的非正则语言，它们恰好也能通过泵引理的测试。
• 这意味着，泵引理只能用来证明一个语言“不是”正则的（通过证明它不满足引理），但绝对不能用来证明一个语言“是”正则的。

本节介绍了证明一个语言“不是”正则语言的两种主要方法：泵引理和封闭性。这通常比证明它是正则的要更复杂。

• - 泵引理 (Pumping Lemma)
• 核心思想: 泵引理描述了所有正则语言都必须具备的一个固有属性。这个属性源于 DFA 的内存有限性（状态数量有限）。如果一个正则语言包含足够长的字符串，那么在处理这些字符串时，DFA 必定会重复经过某个状态（形成一个环）。一旦有环，我们就可以沿着这个环“循环”任意次数（即“泵送”），产生一系列新的字符串，而所有这些新字符串也必须被 DFA 接受，因此也必须属于同一个正则语言。
• 引理的正式陈述:
• 如果 (IF) $L$ 是一个正则语言，
• 那么 (THEN) 存在一个泵长度 $p$ (通常是 DFA 的状态数)，
• 对于所有 (FOR ALL) 属于 $L$ 且长度至少为 $p$ 的字符串 $w$，
• 存在 (THERE EXISTS) 一种将 $w$ 分割成 $xyz$ 的方式，满足三个条件：

1. $|xy| \le p$ (第一个环路必须在前 $p$ 个字符内出现)
2. $|y| > 0$ (环路本身不能为空)
3. 对于所有 (FOR ALL) $i \ge 0$，字符串 $xy^iz$ (泵送 $y$ $i$ 次) 都必须在 $L$ 中。
   • 如何使用泵引理进行反证: 我们的目标是证明某个语言 $L$ 不是 正则的。我们使用反证法：
4. 假设 $L$ 是正则的。
5. 那么泵引理一定成立，存在某个泵长度 $p$。
6. 我们的任务是，针对这个任意的 $p$，找出一个“反例”。即，构造一个特殊的字符串 $w \in L$ 且 $|w| \ge p$。
7. 然后我们证明，无论这个 $w$ 如何被分割成满足条件 (1) 和 (2) 的 $xyz$，我们总能找到一个 $i \ge 0$ (通常 $i=0$ 或 $i=2$ 就够了)，使得泵送后的字符串 $xy^iz$ 不在 $L$ 中。
8. 这就产生了一个矛盾 (泵引理说 $xy^iz$ 必须在 $L$ 中，而我们证明了它不在)。
9. 因此，最初的假设“$L$是正则的”是错误的。结论：$L$ 不是正则的。

• 常见错误: 这部分指出了使用泵引理时新手易犯的错误，这实质上是一个“游戏”的策略指南。对手（代表泵引理）和我方（证明者）的博弈：
• 对手先出招：给一个任意的 $p > 0$。
• 我方出招：必须选择一个 $w \in L$ 且 $|w| \ge p$。这个 $w$ 的选择至关重要，通常要依赖于 $p$ (例如，选择 $w = a^p b^p$)。
• 没有构造一个对于所有 p>0 满足 |w|≥p 的字符串 w: 你的 $w$ 必须能应对任何 $p$。
• 没有构造一个在 L 中的字符串 w: 你的反例 $w$ 必须是语言内的成员。
• 对手再出招：将我方的 $w$ 以满足 $|xy| \le p$ 和 $|y| > 0$ 的所有可能方式进行分割。
• 我方最后一击：必须证明对于所有这些分割，我方都能找到一个 $i$ 来“泵出”一个不在 $L$ 中的字符串。
• 没有考虑解析 w=xyz 的每种可能方式: 这是最常见的错误。你不能只选择一种对你有利的分割来反驳。你必须证明所有合法的分割都会导致矛盾。这里的技巧是，利用 $|xy| \le p$ 这个条件，来限制 $y$ 的可能形式。例如，如果 $w = a^p b^p$，因为 $|xy| \le p$，所以 $y$ 必然只包含 $a$。
• 没有选择一个使得 xy^iz ∉ L 的 i: 你需要找到一个 $i$（比如 $i=0$ 或 $i=2$），使得泵送后的字符串破坏了语言 $L$ 的定义规则。

• - 使用封闭性 (反证法)
• 这是另一种强大的反证法。
• 思路:

1. 假设目标语言 $L$ 是正则的。
2. 将 $L$ 与一个或多个你已知是正则的语言 $L_{reg}$ 进行封闭运算（如交集、并集、补集等）。
3. 因为正则语言在这些运算下是封闭的，所以运算结果 $L_{new} = L \text{ op } L_{reg}$ 也必须是正则的。
4. 但是，如果你能证明 $L_{new}$ 实际上是一个你已知的非正则语言（比如 $\{0^n1^n \mid n \ge 0\}$），那么就产生了矛盾。
5. 这个矛盾说明，最初的假设“$L$是正则的”是错误的。结论：$L$ 不是正则的。

• - Myhill-Nerode 定理
• 再次提到这个定理，并指明它可以用来证明非正则性。方法是证明其可区分字符串的等价类有无限多个。
• 再次强调不属于期中考试范围。

• “泵引理是必要但不充分条件”
• 必要条件 (Necessary Condition): 如果一个语言是正则的，它必须满足泵引理。 (L is regular $\implies$ L satisfies Pumping Lemma)。
• 不充分条件 (Not Sufficient): 一个语言满足泵引理，并不能保证它就是正则的。 (L satisfies Pumping Lemma $\not\implies$ L is regular)。存在一些狡猾的非正则语言，它们恰好也能通过泵引理的测试。
• 这意味着，泵引理只能用来证明一个语言“不是”正则的（通过证明它不满足引理），但绝对不能用来证明一个语言“是”正则的。

本节简要介绍了计算理论的第二个主要语言类别——上下文无关语言 (Context-Free Languages, CFLs)，并将其与正则语言进行了对比。

• “一个语言 $L$ 是上下文无关的，当且仅当它满足以下等价定义之一：”
• 上下文无关 (Context-Free): 这个名字来源于上下文无关文法的产生式规则。规则的形式是 $A \to \gamma$，其中 $A$ 是一个非终结符（变量），$\gamma$ 是终结符和非终结符的混合串。这意味着，无论变量 $A$ 出现在什么“上下文”中，它都可以被替换为 $\gamma$。这与上下文相关文法（替换规则依赖于周边的符号）形成对比。
• 等价定义: 类似于正则语言，CFL 也有两种等价的描述方式：一种是生成式的（文法），一种是识别式的（自动机）。

• - $L$ 可以由一个上下文无关文法（CFG）生成。
• 上下文无关文法 (Context-Free Grammar, CFG): 它是一个四元组 $(V, \Sigma, R, S)$。
• $V$: 非终结符 (Non-terminals) 或 变量 (Variables) 的有限集合。
• $\Sigma$: 终结符 (Terminals) 的有限集合，也就是语言的字母表。
• $R$: 产生式规则 (Production Rules) 的有限集合，形式为 $A \to \gamma$，其中 $A \in V$，$ \gamma \in (V \cup \Sigma)^*$。
• $S$: 起始变量 (Start Variable)，是 $V$ 中的一个特殊变量。
• 生成 (generate): 从起始变量 $S$ 开始，通过反复应用产生式规则，将非终结符替换为相应的串，直到所有非终结符都被替换为终结符为止。所有可能通过这种方式推导出的终结符串的集合，就是该 CFG 生成的语言。
• CFG 的能力在于它能“计数”，比如通过递归规则 $S \to aSb$ 来确保 $a$ 和 $b$ 的数量相等。

• - $L$ 可以被一个下推自动机（PDA）识别，它就像一个配备了栈的 NFA。
• 下推自动机 (Pushdown Automaton, PDA): 它在 NFA 的基础上增加了一个无限容量的栈 (stack)。
• 配备了栈的 NFA: PDA 的每一个转移决策不仅取决于当前状态和输入符号（或$\varepsilon$），还取决于栈顶的符号。在转移时，PDA 可以对栈进行 push（压入）或 pop（弹出）操作。
• 这个栈为自动机提供了无限的内存，但访问方式受限（只能在栈顶操作）。这种内存足以用来“记住”之前输入的符号数量，例如，每读一个 'a' 就向栈中压入一个符号，每读一个 'b' 就弹出一个符号。如果最终栈空了，就说明 'a' 和 'b' 的数量相等。这就是 PDA 能识别 $\{a^n b^n\}$ 而 DFA 不能的原因。

• CFL 类的封闭性:
• 封闭于: 并集、连接、星号。这意味着两个 CFL 的并集、连接或星号闭包，结果仍然是一个 CFL。这些证明通常通过构造新的文法或新的 PDA 来完成。
• 不封闭于: 交集、补集。这是一个与正则语言非常关键的区别。
• 交集不封闭: 存在两个 CFL，$L_1$ 和 $L_2$，它们的交集 $L_1 \cap L_2$ 不是 CFL。一个经典的例子是 $L_1 = \{a^n b^n c^m\}$ 和 $L_2 = \{a^m b^n c^n\}$，它们的交集是 $\{a^n b^n c^n\}$，这是一个著名的非 CFL。
• 补集不封闭: 如果 CFL 在补集和并集下都封闭，那么根据德摩根定律 $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$，它们也将在交集下封闭，这与事实矛盾。因此，CFL 在补集下必然不封闭。

• “每个正则语言都是一个 CFL，但反之则不然。”
• 正则语言 $\subset$ CFL: 这是一个层级关系。所有正则语言都可以被看作是上下文无关语言的特例。
• 证明: 任何 DFA 都可以被转换成一个不使用栈的 PDA。任何正则表达式也可以被转换成所谓的右线性文法 (right-linear grammar)，而右线性文法是 CFG 的一种特殊形式。
• 反之则不然: 存在是 CFL 但不是正则语言的语言。最经典的例子就是 $L = \{0^n1^n \mid n \ge 0\}$。我们知道它可以用泵引理证明不是正则的，但它可以由一个简单的 CFG ($S \to 0S1 \mid \varepsilon$) 生成，或者被一个 PDA 识别。
• 这说明 CFG/PDA 的计算能力比 DFA/NFA/Regex 更强。

这部分是练习题的开篇，提出了第一个大类问题：为给定的正则语言设计自动机。

• “问题集：正则语言”: 明确了这组练习题的主题是关于正则语言的。
• “为以下语言设计有限自动机”: 任务要求是进行“构造性”的解答。你需要画出能够“识别”所描述语言的自动机。
• “你可以通过状态转移图给出 DFA/NFA”: 提示了答案的形式。状态转移图 (state transition diagram) 是自动机的可视化表示，用圆圈代表状态，箭头代表转移。并且明确指出，构造 DFA 或 NFA 都是可以接受的。通常，构造 NFA 会更简单直观。
• “注意：在你的状态转移图中，你可以对边上的标签使用简写符号...”: 这是一个为了简化绘图的便利用法说明。
• $\Sigma \setminus \{a\}$: 这个集合符号表示在字母表 $\Sigma$ 中除去字符 $a$ 之外的所有其他字符。如果 $\Sigma = \{a, b, c\}$，那么 $\Sigma \setminus \{a\}$ 就代表 $\{b, c\}$。在图上画一条标有 $\Sigma \setminus \{a\}$ 的边，就等价于画两条边，一条标 'b'，一条标 'c'，都指向同一个目标状态。这大大减少了图的复杂度。
• “确保在你的图中指定起始状态和接受状态”: 这是一个非常重要的评分点。一个完整的状态转移图必须明确：
• 起始状态 (start state): 通常用一个指向它的、没有源头的箭头来表示。
• 接受状态 (accept states): 通常用双层圆圈来表示。

缺少任何一个，自动机的定义都是不完整的。

这是一个典型的自动机设计问题，需要将文字描述的规则转化为机器模型。我们来逐条分析规则并构思自动机的状态。

规则分析:

1. “每个 0 后面紧跟着一个 1，每个 1 后面紧跟着一个 2，每个 2 后面紧跟着一个 0。”
   • 这是一个非常严格的“后继”规则。它定义了一个固定的循环模式： $0 \to 1 \to 2 \to 0 \to \dots$。
   • 这意味着字符串的形式必然是 $(012)^k$, $(120)^k$, $(201)^k$ 的前缀或它们的一部分。例如 "01201", "12012", "201" 等是合法的序列，但 "02", "11", "010" 都是非法的。
   • 这个规则可以用三个状态来建模，分别代表“上一个字符是0/1/2”。
   • 从一个状态（比如叫 $q_0$），读到 '0'，必须转移到状态 $q_1$。
   • 从状态 $q_1$，读到 '1'，必须转移到状态 $q_2$。
   • 从状态 $q_2$，读到 '2'，必须转移到状态 $q_0$。
   • 任何不符合这个模式的转移都应该进入一个“死状态”（trap state），即一个非接受状态，并且所有出边都指向自身。
2. “字符串以相同的符号开始和结束。”
   • 这个规则增加了对字符串整体的约束。它需要我们“记住”字符串的第一个字符是什么，以便在结尾进行比较。
   • 这启发我们，自动机的起始状态之后，需要根据第一个读入的字符（0, 1, 或 2）进入不同的“路径”或“分支”。每个分支负责追踪以特定符号开头的字符串。
   • 例如，如果以 '0' 开头，那么只有当自动机在处理完整个字符串后，恰好停在一个表示“刚刚读入的字符是0”的状态时，这个字符串才可能被接受。
3. “字符串的长度必须至少为 1。”
   • 这意味着空字符串 $\varepsilon$ 不在语言 $L$ 中。
   • 在自动机设计中，这意味着起始状态本身不能是接受状态。必须至少经过一次转移才能到达接受状态。

综合设计思路 (DFA):

我们可以设计一个 DFA。我们需要状态来编码两个信息：(1) 起始符号是什么，以及 (2) 上一个符号是什么，以便验证后继规则。

• 起始状态 $q_{start}$: 初始状态，非接受。
• 分支路径:
• 从 $q_{start}$ 读到 '0'，进入一个以 '0' 开头的路径。我们用状态 $q_{0,end}$ 表示“以0开头，且上一个符号是0”。
• 从 $q_{start}$ 读到 '1'，进入一个以 '1' 开头的路径。我们用状态 $q_{1,end}$ 表示“以1开头，且上一个符号是1”。
• 从 $q_{start}$ 读到 '2'，进入一个以 '2' 开头的路径。我们用状态 $q_{2,end}$ 表示“以2开头，且上一个符号是2”。
• 状态定义:
• $q_{start}$: 起始状态。
• $q_{0, \text{start}}$: 以 0 开头的路径的初始状态。
• $q_{1, \text{start}}$: 以 1 开头的路径的初始状态。
• $q_{2, \text{start}}$: 以 2 开头的路径的初始状态。
• $q_{0,1}$: 以 0 开头，且上一个符号是 0，下一个期望是 1。
• $q_{0,2}$: 以 0 开头，且上一个符号是 1，下一个期望是 2。
• $q_{1,2}$: 以 1 开头，且上一个符号是 1，下一个期望是 2。
• $q_{1,0}$: 以 1 开头，且上一个符号是 2，下一个期望是 0。
• $q_{2,0}$: 以 2 开头，且上一个符号是 2，下一个期望是 0。
• $q_{2,1}$: 以 2 开头，且上一个符号是 0，下一个期望是 1。
• $q_{trap}$: 死状态。

这个状态设计有点复杂。让我们简化一下。状态可以只表示“上一个读到的符号是什么”，然后根据起始符号来决定哪些状态是接受状态。

简化版 DFA 设计思路:

• $q_{start}$: 起始状态。
• $q_0$: 状态，代表“上一个读入的符号是0”。
• $q_1$: 状态，代表“上一个读入的符号是1”。
• $q_2$: 状态，代表“上一个读入的符号是2”。
• $q_{trap}$: 死状态。

转移函数 $\delta$:

• 从 $q_{start}$:
• $\delta(q_{start}, 0) = q_0$
• $\delta(q_{start}, 1) = q_1$
• $\delta(q_{start}, 2) = q_2$
• 从 $q_0$:
• $\delta(q_0, 1) = q_1$ (满足规则 $0 \to 1$)
• $\delta(q_0, 0) = q_{trap}$ (违反规则)
• $\delta(q_0, 2) = q_{trap}$ (违反规则)
• 从 $q_1$:
• $\delta(q_1, 2) = q_2$ (满足规则 $1 \to 2$)
• $\delta(q_1, 0) = q_{trap}$ (违反规则)
• $\delta(q_1, 1) = q_{trap}$ (违反规则)
• 从 $q_2$:
• $\delta(q_2, 0) = q_0$ (满足规则 $2 \to 0$)
• $\delta(q_2, 1) = q_{trap}$ (违反规则)
• $\delta(q_2, 2) = q_{trap}$ (违反规则)
• 从 $q_{trap}$:
• $\delta(q_{trap}, 0) = q_{trap}$
• $\delta(q_{trap}, 1) = q_{trap}$
• $\delta(q_{trap}, 2) = q_{trap}$

这个设计满足了规则1和规则3。但如何处理规则2（起始和结束符号相同）？

上述设计无法区分起始符号。我们需要更复杂的状态。

最终 DFA 设计思路:

• $q_{start}$: 起始状态, 非接受。
• $q_{s0}, q_{s1}, q_{s2}$: 分别代表读入了起始符号 0, 1, 2。
• $q_{s0}$ 是接受状态 (因为长度为1的 "0" 满足所有条件)。
• $q_{s1}$ 是接受状态 (因为长度为1的 "1" 满足所有条件)。
• $q_{s2}$ 是接受状态 (因为长度为1的 "2" 满足所有条件)。
• 中间状态:
• $q_{p1}$: 代表序列是 $...1$
• $q_{p2}$: 代表序列是 $...2$
• $q_{p0}$: 代表序列是 $...0$

这些状态需要区分起始符号来决定是否接受。这太复杂了。

让我们尝试 NFA，它可能更直观。

NFA 设计思路:

我们可以创建三个并行的“轨道”，分别对应以 '0', '1', '2' 开头的合法字符串。

• 轨道0 (为以 '0' 开头的字符串):
• $q_{start} \xrightarrow{0} q_{0,start}$ (状态 $q_{0,start}$ 表示以0开头，且上一个是0，它是接受状态)
• $q_{0,start} \xrightarrow{1} q_{0,1}$ (状态 $q_{0,1}$ 表示以0开头，上一个是1，非接受)
• $q_{0,1} \xrightarrow{2} q_{0,2}$ (状态 $q_{0,2}$ 表示以0开头，上一个是2，非接受)
• $q_{0,2} \xrightarrow{0} q_{0,start}$ (回到接受状态，形成环)

• 轨道1 (为以 '1' 开头的字符串):
• $q_{start} \xrightarrow{1} q_{1,start}$ (状态 $q_{1,start}$ 表示以1开头，上一个是1，是接受状态)
• $q_{1,start} \xrightarrow{2} q_{1,2}$ (非接受)
• $q_{1,2} \xrightarrow{0} q_{1,0}$ (非接受)
• $q_{1,0} \xrightarrow{1} q_{1,start}$ (回到接受状态)

• 轨道2 (为以 '2' 开头的字符串):
• $q_{start} \xrightarrow{2} q_{2,start}$ (状态 $q_{2,start}$ 表示以2开头，上一个是2，是接受状态)
• $q_{2,start} \xrightarrow{0} q_{2,0}$ (非接受)
• $q_{2,0} \xrightarrow{1} q_{2,1}$ (非接受)
• $q_{2,1} \xrightarrow{2} q_{2,start}$ (回到接受状态)

这个 NFA 设计清晰地分离了三种情况。总共需要 1 (起始) + 3*3 = 10个状态。

• States: $Q = \{q_{start}, q_{0,start}, q_{0,1}, q_{0,2}, q_{1,start}, q_{1,2}, q_{1,0}, q_{2,start}, q_{2,0}, q_{2,1}\}$
• Start State: $q_{start}$
• Accept States: $F = \{q_{0,start}, q_{1,start}, q_{2,start}\}$
• Transitions:
• $\delta(q_{start}, 0) = \{q_{0,start}\}$
• $\delta(q_{start}, 1) = \{q_{1,start}\}$
• $\delta(q_{start}, 2) = \{q_{2,start}\}$
• 轨道0: $\delta(q_{0,start}, 1) = \{q_{0,1}\}, \delta(q_{0,1}, 2) = \{q_{0,2}\}, \delta(q_{0,2}, 0) = \{q_{0,start}\}$
• 轨道1: $\delta(q_{1,start}, 2) = \{q_{1,2}\}, \delta(q_{1,2}, 0) = \{q_{1,0}\}, \delta(q_{1,0}, 1) = \{q_{1,start}\}$
• 轨道2: $\delta(q_{2,start}, 0) = \{q_{2,0}\}, \delta(q_{2,0}, 1) = \{q_{2,1}\}, \delta(q_{2,1}, 2) = \{q_{2,start}\}$
• 所有其他未定义的转移都去往一个隐含的死状态。

这个问题描述了一个“禁止模式”的语言。具体来说，禁止出现 "a...a" 这样的片段，而中间的 "..." 部分不包含 'm'。我们可以通过状态来追踪是否刚刚看到了一个 'a' 以及之后是否已经看到了 'm'。

规则分析:

• “任意两个 $a$ 之间至少包含一个 $m$”: 这句话是核心。
• 我们可以把它反过来想：什么样的字符串是“不合法”的？如果一个字符串包含子串 $a x a$，其中 $x$ 是一个不包含 'm' 的字符串（即 $x \in \{a, b, \dots, l, n, \dots, z\}^*$），那么这个字符串就是不合法的。
• 例如，"papa" 中的 "apa" 就是这样一个非法子串 ($x$ 是 'p'，不含 'm')。 "panamerican" 中的 "anamerica" 也是 ($x$ 是 "nameric"，不含 'm')。
• 语言中的合法字符串包括：
• 不包含 'a' 的字符串 (如 "john")。
• 只包含一个 'a' 的字符串 (如 "abc")。
• 包含多个 'a'，但每对 'a' 之间都有 'm' 的字符串 (如 "mama", "american" 中的 "a...m...a")。

DFA 设计思路:

我们可以设计一个 DFA，其状态代表我们当前所处的“危险等级”。

• 状态 0 ($q_0$): “安全”状态。这是起始状态。在这个状态下，我们要么还没见过 'a'，要么上一个 'a' 之后已经见过一个 'm' 了，警报已解除。
• 状态 1 ($q_1$): “危险”状态。我们刚刚看到了一个 'a'，但还没有看到 'm' 来“解除”这个 'a' 的危险。如果在这个状态下再看到一个 'a'，就意味着出现了 "a...a" 且中间没有 'm' 的情况，字符串非法。
• 状态 2 ($q_{trap}$): “死”状态或“陷阱”状态。一旦进入这个状态，就说明我们已经检测到了一个非法的模式，此后的任何输入都无法挽救这个字符串。

状态转移图设计:

• 字母表: $\Sigma = \{a, b, \dots, z\}$。为了简化，我们将 $\Sigma$ 分为三类：$\{a\}$, $\{m\}$, 和 $\Sigma \setminus \{a, m\}$ (我们称之为 "other")。

• States:
• $q_0$: 起始状态，也是接受状态。
• $q_1$: “刚见过 a”状态，也是接受状态（因为字符串可能就在这里结束，例如 "abc a" 是合法的）。
• $q_{trap}$: 死状态，非接受状态。

• Transitions $\delta$:
• 从 $q_0$ (安全状态):
• 读到 'm': 留在 $q_0$。mama 中的第一个 'm'。
• 读到 "other": 留在 $q_0$。john。
• 读到 'a': 进入危险状态 $q_1$。abc 中的 'a'。
• $\delta(q_0, m) = q_0$
• $\delta(q_0, \text{other}) = q_0$
• $\delta(q_0, a) = q_1$

• 从 $q_1$ (危险状态，刚见过 'a'):
• 读到 'm': 危险解除，回到安全状态 $q_0$。mama 中的 'am' 部分。
• 读到 "other": 危险持续，留在 $q_1$。papa 中的 "ap" 部分。
• 读到 'a': 灾难！我们又看到了一个 'a'，但中间没有 'm'。进入死状态 $q_{trap}$。papa 中的 "apa" 部分。
• $\delta(q_1, m) = q_0$
• $\delta(q_1, \text{other}) = q_1$
• $\delta(q_1, a) = q_{trap}$

• 从 $q_{trap}$ (死状态):
• 读到任何字符（'a', 'm', "other"）: 留在 $q_{trap}$。
• $\delta(q_{trap}, \Sigma) = q_{trap}$

• Start State: $q_0$
• Accept States: $F = \{q_0, q_1\}$。为什么 $q_1$ 也是接受状态？因为一个以 'a' 结尾的字符串是合法的，例如 "ma"。在处理完 "ma" 后，自动机停在 $q_1$，它应该被接受。只要没进入死状态，字符串到目前为止就是合法的。

这是一个判断语言正则性的问题。这个语言 $L$ 的定义是“重复自身”的形式，这通常是非正则语言的一个强烈信号。我们需要使用泵引理来证明它。

语言分析:

• $L = \{ww \mid \dots \}$: 语言中的每个字符串都是某个字符串 $w$ 的精确复制。例如，如果 $w = "011"$, 那么 $ww = "011011" \in L$。
• $w \in \{0,1\}^*$: $w$ 是由 0 和 1 组成的任意字符串。
• $w$ 包含至少一个 0 和至少一个 1: 这是对 $w$ 的一个附加条件。这意味着 $w$ 不能是 $0^*$ 或 $1^*$ 形式的。例如，$w="001"$ 是合法的，但 $w="000"$ 或 $w="11"$ 是不合法的。因此，$ww="001001" \in L$，但 "000000" 和 "1111" 不在 $L$ 中（即使它们是 $w'w'$ 的形式，但 $w'$ 不满足条件）。

直觉判断:

要识别这个语言，机器需要读完前半部分 $w$，将其完整地“记住”，然后与后半部分进行逐一比较。有限自动机 (DFA/NFA) 只有有限的状态，无法记住任意长度的 $w$。这暗示 $L$ 不是正则的。我们将使用泵引理来形式化这个直觉。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。那么泵引理成立，存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w_{str} \in L$，使得 $|w_{str}| \ge p$。这是最关键的一步。我们需要选择一个结构化的、与 $p$ 相关的字符串，使得泵送操作会破坏其结构。
   • 一个好的选择是让 $w$ 的形式为 $0^k1^m$。为了满足 $|ww| \ge p$ 并且结构清晰，我们选择一个简单的 $w$。
   • 令 $w = 0^p1$。这个 $w$ 满足条件“包含至少一个0和至少一个1”。
   • 那么，我们用于泵引理的字符串是 $w_{str} = ww = 0^p10^p1$。
   • 这个字符串 $w_{str} \in L$，并且其长度 $|w_{str}| = 2p+2 \ge p$。
3. 应用泵引理的分割: 根据泵引理，$w_{str}$ 可以被分割为 $xyz$，满足以下条件：
   • $w_{str} = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w_{str} = \underbrace{00\dots0}_{p \text{ times}}10^p1$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 '0' 里面。
   • 所以，$x$ 必然是 $0^a$ 的形式，其中 $a \ge 0$。
   • $y$ 必然是 $0^b$ 的形式，其中 $b \ge 1$ (因为 $|y|>0$)。
   • $z$ 则是剩下的部分，即 $0^{p-a-b}10^p1$。
   • $a+b \le p$。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 泵引理声称，对于所有 $i \ge 0$，$xy^iz$ 都必须在 $L$ 中。
   • 我们选择 $i=2$ 进行泵送（增加'y'）。
   • $xy^2z = xyyz = (0^a)(0^b)(0^b)(0^{p-a-b}10^p1) = 0^{p+b}10^p1$。
   • 现在我们需要判断这个新字符串 $0^{p+b}10^p1$ 是否还在 $L$ 中。
   • 一个在 $L$ 中的字符串必须是 $u u$ 的形式。如果 $0^{p+b}10^p1$ 是 $u u$ 的形式，它的总长度必须是偶数。总长度是 $(p+b)+1+p+1 = 2p+b+2$。
   • 它的中点在哪里？在第 $(2p+b+2)/2 = p + b/2 + 1$ 个字符之后。因为 $b \ge 1$ 并且是整数，所以 $b/2$ 不一定是整数，这个分割点很难处理。

让我们换一种更清晰的泵送方式。选择 $i=0$ (删除'y')。

• 选择 $i=0$。
• $xy^0z = xz = (0^a)(0^{p-a-b}10^p1) = 0^{p-b}10^p1$。
• 这个新字符串是 $w' = 0^{p-b}10^p1$。
• 我们来判断 $w'$ 是否在 $L$ 中。如果它在 $L$ 中，它必须能被写成 $u u$ 的形式，其中 $u$ 包含至少一个0和一个1。
• $w'$ 的总长度是 $(p-b)+1+p+1 = 2p-b+2$。
• 要成为 $uu$ 的形式，它必须能被从中间完美地分成两个相同的部分。
• 它的前半部分应该是 $u$，长度为 $(2p-b+2)/2 = p - b/2 + 1$。
• 它的后半部分也应该是 $u$，长度也为 $p - b/2 + 1$。
• 由于 $b \ge 1$，所以 $b$ 是一个正整数。
• 如果 b 是奇数，那么 $b/2$ 不是整数，总长度是奇数，一个奇数长度的字符串永远不可能写成 $uu$ 的形式。所以 $w' \notin L$。
• 如果 b 是偶数，那么总长度是偶数。前半部分 $u$ 的长度是 $p-b/2+1$。
• 前半部分 $u = 0^{p-b}1$。它的长度是 $(p-b)+1$。
• 后半部分是 $0^p1$。它的长度是 $p+1$。
• 为了让 $w'$ 成为 $uu$ 的形式，前半部分必须等于后半部分。
• 但我们有 $b \ge 1$ (实际上，因为 $b$ 是偶数，所以 $b \ge 2$)。
• $p-b+1 < p+1$。
• $0^{p-b}1$ 不可能等于 $0^p1$。
• 因此，即使 $b$ 是偶数，前后两半也不相等。所以 $w' \notin L$。

• 综上所述，无论 $b$ 是奇数还是偶数，只要 $b \ge 1$，泵送后的字符串 $xy^0z$ 都不在 $L$ 中。

1. 结论: 我们找到了一个 $i=0$，使得 $xy^iz \notin L$。这与泵引理矛盾。因此，我们最初的假设“$L$是正则的”是错误的。

最终结论: $L$ 是非正则的。

这是一个判断语言正则性的问题。语言的规则是 $c$ 的数量必须等于 $a$ 的数量加上 $b$ 的数量。这需要进行加法计数，而有限自动机无法存储任意大的计数值。这强烈暗示该语言是非正则的。我们将使用泵引理来证明。

语言分析:

• $L = \{a^i b^j c^k \mid i+j=k\}$: 字符串由三部分组成，先是任意数量的 $a$，然后是任意数量的 $b$，最后是任意数量的 $c$。
• $i,j,k \ge 0$ 是整数。
• 核心约束是：$k = i+j$。$c$ 的数量等于 $a$ 和 $b$ 的数量之和。

直觉判断:

要识别这个语言，机器需要：

1. 读取并计数 $a$ 的数量 (得到 $i$)。
2. 读取并计数 $b$ 的数量 (得到 $j$)。
3. 将这两个计数值相加。
4. 读取并计数 $c$ 的数量，并与前两步的和进行比较。

有限自动机的状态数量是有限的，它无法存储可能无限大的 $i$ 和 $j$ 的值来进行精确的加法和比较。因此，这个语言应该是非正则的。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。根据泵引理，存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w \in L$，使得 $|w| \ge p$。我们需要一个结构化的字符串来破坏 $i+j=k$ 这个平衡。
   • 一个好的选择是固定其中一个变量，让另一个与 $p$ 相关。
   • 令 $i=p$ 并且 $j=0$。那么根据规则， $k = p+0 = p$。
   • 我们选择的字符串是 $w = a^p c^p$。(注意 $b^0 = \varepsilon$ 是合法的)。
   • 这个字符串 $w \in L$ (因为 $i=p, j=0, k=p$，满足 $i+j=k$)。
   • 其长度 $|w| = 2p \ge p$。
3. 应用泵引理的分割: $w$ 可以被分割为 $xyz$，满足：
   • $w = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w = \underbrace{aa\dots a}_{p \text{ times}}\underbrace{cc\dots c}_{p \text{ times}}$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 'a' 里面。
   • 所以，$x$ 必然是 $a^m$ 的形式，其中 $m \ge 0$。
   • $y$ 必然是 $a^n$ 的形式，其中 $n \ge 1$ (因为 $|y|>0$)。
   • $z$ 则是剩下的部分，即 $a^{p-m-n}c^p$。
   • $m+n \le p$。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 泵引理声称，对于所有 $i' \ge 0$，$xy^{i'}z$ 都必须在 $L$ 中。(这里用 $i'$ 以区别于语言定义中的 $i$)
   • 我们选择 $i'=2$ 进行泵送。
   • $xy^2z = xyyz = (a^m)(a^n)(a^n)(a^{p-m-n}c^p) = a^{p+n}c^p$。
   • 现在我们来判断这个新字符串 $w' = a^{p+n}c^p$ 是否还在 $L$ 中。
   • 这个新字符串的形式是 $a^{i_{new}}b^{j_{new}}c^{k_{new}}$。
   • $i_{new} = p+n$
   • $j_{new} = 0$
   • $k_{new} = p$
   • 为了让 $w'$ 在 $L$ 中，必须满足 $i_{new} + j_{new} = k_{new}$。
   • 即 $(p+n) + 0 = p$。
   • 化简得到 $p+n = p$，这意味着 $n=0$。
   • 但是，根据泵引理的条件，$|y|>0$，所以 $n$ (即 $y$ 的长度) 必须大于等于 1。
   • 这就产生了一个矛盾：$n$ 必须为 0，但 $n$ 又必须大于等于 1。
6. 结论: 我们选择 $i'=2$ 泵送后得到的字符串 $xy^2z$ 不满足 $L$ 的条件，因此 $xy^2z \notin L$。这与泵引理矛盾。所以我们最初的假设“$L$是正则的”是错误的。

另一种选择: 我们也可以选择 $w = a^p b^p c^{2p}$，或者 $w = b^p c^p$。使用 $w = a^p c^p$ 的好处是它结构更简单，分割 $y$ 的可能性只有一种。

最终结论: $L$ 是非正则的。

这是一个判断语言正则性的问题。语言的形式是：以 $k$ 个0开头，以 $k$ 个1结尾，中间夹着任意的字符串 $u$。

语言分析:

• $L = \{0^k u 1^k \mid k \ge 1, u \in \Sigma^*\}$
• $k \ge 1$: 开头的0和结尾的1的数量至少是1。
• $u \in \Sigma^*$: 中间的 $u$ 可以是任意由0和1组成的字符串，包括空字符串。
• 核心约束是：开头的0的数量必须和结尾的1的数量完全相等。

直觉判断:

要识别这个语言，机器需要：

1. 读取并计数开头的 $k$ 个0。
2. 将这个计数值 $k$ “记住”。
3. 读过中间任意的字符串 $u$。
4. 读取结尾的1，并与之前记住的 $k$ 进行比较，确保数量恰好为 $k$。

中间的 $u$ 是一个关键的迷惑项。因为 $u$ 可以包含任意的0和1，机器在读 $u$ 的时候，很容易“忘记”之前计数的 $k$ 值。例如，对于字符串 "0010111"，机器如何知道开头的 "00" 应该和结尾的哪两个 "1" 匹配？它无法分辨结尾的 "11" 是属于 $u$ 的一部分还是属于结尾的 $1^k$ 部分。

更重要的是，为了验证结尾 $1^k$ 的数量，机器必须记住开头 $0^k$ 的数量。由于 $k$ 可以是任意大的正整数，有限自动机的有限状态无法记住任意大的 $k$ 值。这强烈暗示语言是非正则的。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w \in L$，使得 $|w| \ge p$。
   • 我们需要一个结构化的字符串，其中 $k$ 的值与 $p$ 相关，并且中间的 $u$ 尽量简单，以避免混淆。最简单的 $u$ 就是空字符串 $\varepsilon$。
   • 令 $k=p$ 并且 $u=\varepsilon$。
   • 我们选择的字符串是 $w = 0^p 1^p$。
   • 这个字符串 $w \in L$ (因为 $k=p \ge 1$, $u=\varepsilon$)。
   • 其长度 $|w| = 2p \ge p$。
3. 应用泵引理的分割: $w$ 可以被分割为 $xyz$，满足：
   • $w = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w = \underbrace{00\dots 0}_{p \text{ times}}\underbrace{11\dots 1}_{p \text{ times}}$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 '0' 里面。
   • 所以，$y$ 必然是 $0^m$ 的形式，其中 $m \ge 1$ (因为 $|y|>0$)。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 泵引理声称，对于所有 $i' \ge 0$，$xy^{i'}z$ 都必须在 $L$ 中。
   • 我们选择 $i'=2$ 进行泵送。
   • $xy^2z = 0^{p+m}1^p$。
   • 现在我们来判断这个新字符串 $w' = 0^{p+m}1^p$ 是否还在 $L$ 中。
   • 为了让 $w'$ 在 $L$ 中，它必须能被写成 $0^j u' 1^j$ 的形式。
   • 在 $w'$ 中，所有0都在所有1的前面，所以 $u'$ 必须是空字符串。
   • 那么 $w'$ 的形式就是 $0^{p+m}1^p$。
   • 为了匹配 $0^j 1^j$ 的形式，开头的0的数量必须等于结尾的1的数量。
   • 即 $p+m$ 必须等于 $p$。
   • 这要求 $m=0$。
   • 但是，根据泵引理的条件，$|y|>0$，所以 $m$ 必须大于等于 1。
   • 这就产生了一个矛盾：$m$ 必须为 0，但 $m$ 又必须大于等于 1。
6. 结论: 泵送后的字符串 $xy^2z$ 不在 $L$ 中。这与泵引理矛盾。因此，我们最初的假设“$L$是正则的”是错误的。

最终结论: $L$ 是非正则的。

这个问题与上一个问题非常相似，但有一个微小而关键的区别。这里的语言是 $\{0^k 1 u 1^k\}$。

语言分析:

• $L = \{0^k 1 u 1^k \mid k \ge 1, u \in \Sigma^*\}$
• $k \ge 1$: 开头的0和结尾的1的数量至少是1。
• $u \in \Sigma^*$: 中间的 $u$ 可以是任意字符串。
• 核心结构是：一段 $0^k$，后面紧跟着一个单个的 '1'，然后是任意字符串 $u$，最后是一段 $1^k$。

直觉判断:

与上一个问题一样，这个问题似乎也需要匹配开头 $0^k$ 和结尾 $1^k$ 的数量。这看起来仍然需要无限的记忆。但是，中间的那个孤立的 '1' 是一个非常重要的“分隔符”或“标记”。

让我们重新思考一下自动机能否识别它。一个非确定性有限自动机 (NFA) 可以做“猜测”。

NFA 能否识别这个语言?

1. NFA 可以先读开头的 $k$ 个0。但它不知道 $k$ 是多少。
2. 然后它读到一个 '1'。这是一个关键点。NFA 可以“猜测”：这个 '1' 是不是那个重要的分隔符 '1'？
3. 猜测1: 假设这个 '1' 就是分隔符。NFA 进入一个新模式。在这个模式里，它需要验证接下来是否有 $k$ 个 '1'。但它已经忘了 $k$ 是多少了。所以这个猜测行不通。

让我们反过来想，从后往前看。

一个 NFA 无法从后往前读。但是，证明一个语言 $L$ 是正则的，等价于证明它的反转语言 $L^R = \{w^R \mid w \in L\}$ 是正则的（因为正则语言在反转操作下是封闭的）。

• $L^R = \{ (0^k 1 u 1^k)^R \mid k \ge 1, u \in \Sigma^* \}$
• $= \{ (1^k)^R u^R (0^k 1)^R \mid k \ge 1, u \in \Sigma^* \}$
• $= \{ 1^k (u^R) 1 0^k \mid k \ge 1, u \in \Sigma^* \}$

令 $v = u^R$。因为 $u$ 可以是 $\Sigma^*$ 中的任意字符串，所以 $u^R$ 也可以是 $\Sigma^*$ 中的任意字符串。所以 $v$ 也是任意字符串。

• $L^R = \{ 1^k v 1 0^k \mid k \ge 1, v \in \Sigma^* \}$

这个反转语言 $L^R$ 是什么样子的？它以 $k$ 个 '1' 开头，然后是任意字符串 $v$，然后是一个 '1'，最后是 $k$ 个 '0'。

这个语言和原始语言 $L$ 几乎一模一样，也需要匹配开头和结尾的数量。所以反转这条路似乎也没能简化问题。

回到最初的判断：它很可能是非正则的。 我们再次尝试使用泵引理。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w \in L$，使得 $|w| \ge p$。
   • 为了突出 $0^k$ 和 $1^k$ 的对应关系，并简化问题，我们选择 $u$ 为空字符串。
   • 令 $k=p$。
   • 我们选择的字符串是 $w = 0^p 1 1^p$。
   • 这个字符串 $w \in L$ (因为 $k=p \ge 1, u=\varepsilon$)。
   • 其长度 $|w| = p+1+p = 2p+1 \ge p$。
3. 应用泵引理的分割: $w$ 可以被分割为 $xyz$，满足：
   • $w = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w = \underbrace{00\dots 0}_{p \text{ times}}11^p$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 '0' 里面。
   • 所以，$y$ 必然是 $0^m$ 的形式，其中 $m \ge 1$ (因为 $|y|>0$)。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 我们选择 $i=2$ 进行泵送。
   • $xy^2z = 0^{p+m} 1 1^p$。
   • 现在我们来判断这个新字符串 $w' = 0^{p+m} 1 1^p$ 是否还在 $L$ 中。
   • 为了让 $w'$ 在 $L$ 中，它必须能被写成 $0^j 1 u' 1^j$ 的形式，其中 $j \ge 1$。
   • $w'$ 的结构是：一串0，跟着一串1。
   • 要匹配 $0^j 1 u' 1^j$ 的形式，它必须有一个孤立的 '1' 作为分隔符。
   • $w' = 0^{p+m} 1^ {p+1}$。这里面根本没有孤立的 '1'，它就是一堆0跟着一堆1。
   • 如果我们要强行匹配，比如我们把 $0^{p+m}$ 当作 $0^j$，把结尾的 $1^p$ 当作 $1^j$，那么 $j$ 就必须同时等于 $p+m$ 和 $p$，这不可能。
   • 更严谨地说，要匹配 $0^j 1 u' 1^j$ 的形式，$w'$ 必须能被分割成 (一串0) + '1' + (任意串) + (一串1)。
   • $w' = 0^{p+m} 1 1^p$。
   • 这里的第一个 '1' 就是那个分隔符 '1'。
   • 那么，开头的0串是 $0^{p+m}$，所以 $j$ 应该是 $p+m$。
   • 结尾的1串是 $1^p$，所以 $j$ 应该是 $p$。
   • 所以，我们需要 $p+m = p$，这意味着 $m=0$。
   • 但是，根据泵引理，$|y|>0$，所以 $m \ge 1$。
   • 这又是一个矛盾。
6. 结论: 泵送后的字符串 $xy^2z$ 不在 $L$ 中。这与泵引理矛盾。因此，假设“$L$是正则的”是错误的。

等一下，这个结论对吗？让我们重新审视一下。

难道这个问题是正则的吗？我刚才的直觉判断和证明似乎都指向非正则。但是这个问题紧跟在问题5后面，形式非常相似，这可能是一个陷阱，暗示答案可能不同。

让我们尝试构造一个正则表达式或自动机。

如果它是正则的，那么一定存在一个正则表达式。

$L = \{0^k 1 u 1^k \mid k \ge 1, u \in \Sigma^*\}$

• $k=1$: $01u1$。 正则表达式: $01(0|1)^*1$。
• $k=2$: $001u11$。 正则表达式: $001(0|1)^*11$。
• $k=3$: $0001u111$。 正则表达式: $0001(0|1)^*111$。
• ...

$L$ 是所有这些的并集: $01(0|1)^*1 \cup 001(0|1)^*11 \cup 0001(0|1)^*111 \cup \dots$

这是一个无限的并集。正则语言只在有限并集下封闭。所以这个思路不能证明它是正则的。

回到泵引理的证明，检查是否有漏洞。

证明过程是：

1. 选 $w = 0^p 1 1^p$。
2. $y$ 在开头的 $0^p$ 里， $y=0^m, m \ge 1$。
3. 泵送得到 $0^{p+m} 1 1^p$。
4. 要求 $p+m = p$，得出 $m=0$ 的矛盾。

这个证明看起来是无懈可击的。它与证明 $\{0^n1^n\}$ 非正则的逻辑是完全一样的。那个孤立的 '1' 并没有改变需要两端计数的本质。

那会不会问题5才是正则的，而问题6是非正则的？

让我们重新检查问题5: $L_5 = \{0^k u 1^k \mid k \ge 1, u \in \Sigma^*\}$

这个语言的证明也是完全一样的逻辑。选 $w = 0^p 1^p$ (即 $u=\varepsilon$)。泵送开头的0，破坏了与结尾1的数量平衡。

结论: 两个语言都是非正则的，并且证明方法基本相同。

也许这组题目的目的就是让学生辨析这种微小差异是否会影响正则性。在这种情况下，这个分隔符 '1' 并没有提供足够的信息来消除对无限内存的需求。

最终确认: 我的泵引理证明逻辑没有问题。问题6的语言是非正则的。

这是一个具有挑战性的问题，需要更深入的分析。我们需要计算两种不同子串 ab 和 ba 的出现次数，并比较它们是否相等。

语言分析:

• $L = \{w \in \{a,b\}^* \mid \text{count}(w, "ab") = \text{count}(w, "ba") \}$
• count(w, "sub") 表示子串 "sub" 在 $w$ 中出现的次数。
• 例如:
• $w = \text{"aabbbaa"}$
• ab 在索引1处出现一次。
• ba 在索引4处出现一次。
• 次数相等 (1=1)，所以 "aabbbaa" $\in L$。
• $w = \text{"ab"}$
• ab 出现1次，ba 出现0次。不等，所以 "ab" $\notin L$。
• $w = \text{"aba"}$
• ab 出现1次，ba 出现1次。相等，所以 "aba" $\in L$。
• $w = \text{"baba"}$
• ba 出现2次，ab 出现1次。不等，所以 "baba" $\notin L$。
• 空字符串 $\varepsilon$: ab 出现0次，ba 出现0次。相等，所以 $\varepsilon \in L$。
• 单个字符: 'a' 或 'b'。ab 和 ba 都出现0次。相等，所以 'a', 'b' $\in L$。
• 单一字符重复: $a^k$ 或 $b^k$。ab 和 ba 都出现0次。相等，所以 $a^k, b^k \in L$。

寻找规律:

让我们观察 ab 和 ba 的出现如何改变计数的差异。令 diff = count("ab") - count("ba")。我们的目标是 diff = 0。

• 在一个字符串的末尾追加一个字符，看 diff 如何变化。
• 假设我们有一个字符串 $w$。
• 如果 $w$ 以 'a' 结尾，我们追加一个 'b'，得到 $wb$。
• ab 的计数增加1。diff 增加1。
• 如果 $w$ 以 'a' 结尾，我们追加一个 'a'，得到 $wa$。
• ab 和 ba 的计数都不变。diff 不变。
• 如果 $w$ 以 'b' 结尾，我们追加一个 'a'，得到 $wa$。
• ba 的计数增加1。diff 减少1。
• 如果 $w$ 以 'b' 结尾，我们追加一个 'b'，得到 $wb$。
• ab 和 ba 的计数都不变。diff 不变。

这个观察非常重要！计数的差异 diff 只在字符串末尾发生 a 和 b 交替时才改变。

• ...a $\to$ ...ab (diff++)
• ...b $\to$ ...ba (diff--)

进一步分析:

• 一个字符串从头开始。
• 扫描字符串，忽略连续相同的字符，只看字符变化的点。
• 'ab' 对应一次从 'a' 到 'b' 的变化。
• 'ba' 对应一次从 'b' 到 'a' 的变化。
• count("ab") 就是字符串中从 'a' 变为 'b' 的次数。
• count("ba") 就是字符串中从 'b' 变为 'a' 的次数。

考虑一个字符串 $w$。

• 如果 $w$ 为空，或 $w$ 只由 'a' 或 'b' 组成，那么 count("ab") = count("ba") = 0。这些字符串在 $L$ 中。
• 如果 $w$ 既有 'a' 也有 'b'，它必然以某个字符开始，以某个字符结束。
• Case 1: $w$ 以 'a' 开头，以 'a' 结尾。
• 例如: a...b...a...b...a。
• 每一次从 'a' 到 'b' 的转换，后续必然会有一次从 'b' 回到 'a' 的转换，才能最终以 'a' 结尾。
• a -> b 的次数必然等于 b -> a 的次数。
• 因此，count("ab") = count("ba")。
• Case 2: $w$ 以 'b' 开头，以 'b' 结尾。
• 同理，b -> a 的次数必然等于 a -> b 的次数。
• count("ab") = count("ba")。
• Case 3: $w$ 以 'a' 开头，以 'b' 结尾。
• 例如: a...b...a...b。
• 第一次转换是 a -> b。为了以 'b' 结尾，最后一次转换必然是 a -> b。
• a -> b 的次数会比 b -> a 的次数多 1。
• count("ab") = count("ba") + 1。
• Case 4: $w$ 以 'b' 开头，以 'a' 结尾。
• 例如: b...a...b...a。
• b -> a 的次数会比 a -> b 的次数多 1。
• count("ba") = count("ab") + 1。

结论:

一个字符串 $w$ 属于语言 $L$ (即 count("ab") == count("ba")) 当且仅当:

1. $w$ 不包含 'a' 或不包含 'b' (例如 $\varepsilon, a, b, aaa, bbb$)。
2. 或者，$w$ 的第一个字符和最后一个字符相同。

这个结论非常简洁和强大。现在我们可以基于这个新的、等价的定义来判断正则性。

证明 $L$ 是正则的:

我们可以把 $L$ 分解成几个简单的正则语言的并集。

• $L_1$: 不包含 'a' 的字符串。正则表达式为: $b^*$。
• $L_2$: 不包含 'b' 的字符串。正则表达式为: $a^*$。
• $L_3$: 以 'a' 开头，并以 'a' 结尾的字符串。正则表达式为: $a(a|b)^*a$。
• $L_4$: 以 'b' 开头，并以 'b' 结尾的字符串。正则表达式为: $b(a|b)^*b$。

但是这个分解不完全正确，它没有包含长度为1的字符串 'a' 和 'b'。

修正后的分解:

• $L_a = \{w \mid w \text{ 以 'a' 开头和结尾} \}$。正则表达式: $a | a(a|b)^*a$。
• $L_b = \{w \mid w \text{ 以 'b' 开头和结尾} \}$。正则表达式: $b | b(a|b)^*b$。
• $L_{no\_ab} = \{w \mid w \text{ 中没有'a'或没有'b'} \}$。正则表达式: $a^* | b^*$。
• $L = L_a \cup L_b \cup L_{no\_ab}$。
• 更准确地， $L$ 就是所有满足“首尾字符相同”或“只含一种字符”的字符串。
• 这个集合可以被描述为：

1. 空字符串: $\varepsilon$
2. 只有一个字符: $a, b$
3. 由单一字符组成: $a^+$ (一个或多个a), $b^+$ (一个或多个b)
4. 以 'a' 开头和结尾，且长度大于1: $a(a|b)^*a$
5. 以 'b' 开头和结尾，且长度大于1: $b(a|b)^*b$

• 一个更简洁的正则表达式可以覆盖所有这些情况：
• $\varepsilon$
• $a(a|b)^*a$
• $b(a|b)^*b$
• $a^+$
• $b^+$
• $a$
• $b$
• 正则表达式 $a(a|b)^*a$ 已经包含了 $a^+$ (当中间都是a时) 和 $a$ (当中间的 $(a|b)^*$ 是 $\varepsilon$ 时，长度为2的 $aa$)，但不包含单个 'a'。
• 所以，一个完整的描述是: $L = \{w \mid w \text{ 的首尾字符相同}\} \cup \{\varepsilon\}$
• 语言 $\{w \mid w \text{ 的首尾字符相同}\}$:
• $a$
• $b$
• $a(a|b)^*a$
• $b(a|b)^*b$
• 所以这个语言的正则表达式是: $\varepsilon | a | b | a(a|b)^*a | b(a|b)^*b$。
• $a^* | b^*$ 这个也可以。$a^*$ 包含 $\varepsilon, a, aa, \dots$。$b^*$ 包含 $\varepsilon, b, bb, \dots$。他们的并集包含了所有单一字符组成的串。
• 那么 $L$ 到底是什么？是 $\{w \mid \text{首尾字符相同}\}$。
• 如果 $w$ 首尾字符相同，count("ab") = count("ba")。
• 如果 $w$ 首尾字符不同，count("ab") 和 count("ba") 相差1。
• 如果 $w$ 是空串或单字符或单字符重复，首尾字符也相同（或未定义但满足条件）。
• 所以， $L = \{ w \in \{a,b\}^* \mid w \text{ 的第一个字符等于最后一个字符} \} \cup \{\varepsilon\}$。
• 这个描述覆盖了所有情况。

构造一个识别 $L$ 的 NFA:

• 状态 $q_{start}$: 起始状态，也是接受状态 (为了接受 $\varepsilon$)。
• 轨道 a:
• $q_{start} \xrightarrow{a} q_a$ ( $q_a$ 是接受状态，接受单个 'a' )
• $q_a \xrightarrow{a,b} q_{mid\_a}$
• $q_{mid\_a} \xrightarrow{a,b} q_{mid\_a}$
• $q_{mid\_a} \xrightarrow{a} q_a$ (回到接受状态)
• 轨道 b:
• $q_{start} \xrightarrow{b} q_b$ ( $q_b$ 是接受状态，接受单个 'b' )
• $q_b \xrightarrow{a,b} q_{mid\_b}$
• $q_{mid\_b} \xrightarrow{a,b} q_{mid\_b}$
• $q_{mid\_b} \xrightarrow{b} q_b$

这个 NFA 有点乱。让我们用 DFA 来追踪 “第一个字符” 和 “上一个字符”。

DFA 设计:

• $q_0$: 起始状态，接受 (for $\varepsilon$)
• $q_A$: 第一个字符是 'a'。接受 (for 'a')
• $q_B$: 第一个字符是 'b'。接受 (for 'b')
• $q_{A\_mid\_a}$: 首字符是 'a', 上一个字符是 'a'。接受。
• $q_{A\_mid\_b}$: 首字符是 'a', 上一个字符是 'b'。非接受。
• $q_{B\_mid\_a}$: 首字符是 'b', 上一个字符是 'a'。非接受。
• $q_{B\_mid\_b}$: 首字符是 'b', 上一个字符是 'b'。接受。

转移:

• $\delta(q_0, a) = q_A$
• $\delta(q_0, b) = q_B$
• $\delta(q_A, a) = q_{A\_mid\_a}$
• $\delta(q_A, b) = q_{A\_mid\_b}$
• $\delta(q_B, a) = q_{B\_mid\_a}$
• $\delta(q_B, b) = q_{B\_mid\_b}$
• $\delta(q_{A\_mid\_a}, a) = q_{A\_mid\_a}$
• $\delta(q_{A\_mid\_a}, b) = q_{A\_mid\_b}$
• $\delta(q_{A\_mid\_b}, a) = q_{A\_mid\_a}$
• $\delta(q_{A\_mid\_b}, b) = q_{A\_mid\_b}$
• $\delta(q_{B\_mid\_a}, a) = q_{B\_mid\_a}$
• $\delta(q_{B\_mid\_a}, b) = q_{B\_mid\_b}$
• $\delta(q_{B\_mid\_b}, a) = q_{B\_mid\_a}$
• $\delta(q_{B\_mid\_b}, b) = q_{B\_mid\_b}$

这个 DFA 太复杂了。简单的正则表达式证明已经足够了。

最终结论: 语言 $L$ 是正则的。

它的等价定义是：所有首尾字符相同的字符串（以及空字符串和单字符字符串）。

一个描述该语言的正则表达式是:

$R = a^* | b^* | a(a|b)^*a | b(a|b)^*b$

• $a^*$: 接受 $\varepsilon, a, aa, \dots$ (首尾相同)
• $b^*$: 接受 $\varepsilon, b, bb, \dots$ (首尾相同)
• $a(a|b)^*a$: 接受以a开头和结尾的，长度至少为2的串。
• $b(a|b)^*b$: 接受以b开头和结尾的，长度至少为2的串。

这个并集覆盖了所有情况。既然 $L$ 可以被一个正则表达式描述，那么 $L$ 是正则的。

本节简要介绍了计算理论的第二个主要语言类别——上下文无关语言 (Context-Free Languages, CFLs)，并将其与正则语言进行了对比。

• “一个语言 $L$ 是上下文无关的，当且仅当它满足以下等价定义之一：”
• 上下文无关 (Context-Free): 这个名字来源于上下文无关文法的产生式规则。规则的形式是 $A \to \gamma$，其中 $A$ 是一个非终结符（变量），$\gamma$ 是终结符和非终结符的混合串。这意味着，无论变量 $A$ 出现在什么“上下文”中，它都可以被替换为 $\gamma$。这与上下文相关文法（替换规则依赖于周边的符号）形成对比。
• 等价定义: 类似于正则语言，CFL 也有两种等价的描述方式：一种是生成式的（文法），一种是识别式的（自动机）。

• - $L$ 可以由一个上下文无关文法（CFG）生成。
• 上下文无关文法 (Context-Free Grammar, CFG): 它是一个四元组 $(V, \Sigma, R, S)$。
• $V$: 非终结符 (Non-terminals) 或 变量 (Variables) 的有限集合。
• $\Sigma$: 终结符 (Terminals) 的有限集合，也就是语言的字母表。
• $R$: 产生式规则 (Production Rules) 的有限集合，形式为 $A \to \gamma$，其中 $A \in V$，$ \gamma \in (V \cup \Sigma)^*$。
• $S$: 起始变量 (Start Variable)，是 $V$ 中的一个特殊变量。
• 生成 (generate): 从起始变量 $S$ 开始，通过反复应用产生式规则，将非终结符替换为相应的串，直到所有非终结符都被替换为终结符为止。所有可能通过这种方式推导出的终结符串的集合，就是该 CFG 生成的语言。
• CFG 的能力在于它能“计数”，比如通过递归规则 $S \to aSb$ 来确保 $a$ 和 $b$ 的数量相等。

• - $L$ 可以被一个下推自动机（PDA）识别，它就像一个配备了栈的 NFA。
• 下推自动机 (Pushdown Automaton, PDA): 它在 NFA 的基础上增加了一个无限容量的栈 (stack)。
• 配备了栈的 NFA: PDA 的每一个转移决策不仅取决于当前状态和输入符号（或$\varepsilon$），还取决于栈顶的符号。在转移时，PDA 可以对栈进行 push（压入）或 pop（弹出）操作。
• 这个栈为自动机提供了无限的内存，但访问方式受限（只能在栈顶操作）。这种内存足以用来“记住”之前输入的符号数量，例如，每读一个 'a' 就向栈中压入一个符号，每读一个 'b' 就弹出一个符号。如果最终栈空了，就说明 'a' 和 'b' 的数量相等。这就是 PDA 能识别 $\{a^n b^n\}$ 而 DFA 不能的原因。

• CFL 类的封闭性:
• 封闭于: 并集、连接、星号。这意味着两个 CFL 的并集、连接或星号闭包，结果仍然是一个 CFL。这些证明通常通过构造新的文法或新的 PDA 来完成。
• 不封闭于: 交集、补集。这是一个与正则语言非常关键的区别。
• 交集不封闭: 存在两个 CFL，$L_1$ 和 $L_2$，它们的交集 $L_1 \cap L_2$ 不是 CFL。一个经典的例子是 $L_1 = \{a^n b^n c^m\}$ 和 $L_2 = \{a^m b^n c^n\}$，它们的交集是 $\{a^n b^n c^n\}$，这是一个著名的非 CFL。
• 补集不封闭: 如果 CFL 在补集和并集下都封闭，那么根据德摩根定律 $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$，它们也将在交集下封闭，这与事实矛盾。因此，CFL 在补集下必然不封闭。

• “每个正则语言都是一个 CFL，但反之则不然。”
• 正则语言 $\subset$ CFL: 这是一个层级关系。所有正则语言都可以被看作是上下文无关语言的特例。
• 证明: 任何 DFA 都可以被转换成一个不使用栈的 PDA。任何正则表达式也可以被转换成所谓的右线性文法 (right-linear grammar)，而右线性文法是 CFG 的一种特殊形式。
• 反之则不然: 存在是 CFL 但不是正则语言的语言。最经典的例子就是 $L = \{0^n1^n \mid n \ge 0\}$。我们知道它可以用泵引理证明不是正则的，但它可以由一个简单的 CFG ($S \to 0S1 \mid \varepsilon$) 生成，或者被一个 PDA 识别。
• 这说明 CFG/PDA 的计算能力比 DFA/NFA/Regex 更强。

这部分是练习题的开篇，提出了第一个大类问题：为给定的正则语言设计自动机。

• “问题集：正则语言”: 明确了这组练习题的主题是关于正则语言的。
• “为以下语言设计有限自动机”: 任务要求是进行“构造性”的解答。你需要画出能够“识别”所描述语言的自动机。
• “你可以通过状态转移图给出 DFA/NFA”: 提示了答案的形式。状态转移图 (state transition diagram) 是自动机的可视化表示，用圆圈代表状态，箭头代表转移。并且明确指出，构造 DFA 或 NFA 都是可以接受的。通常，构造 NFA 会更简单直观。
• “注意：在你的状态转移图中，你可以对边上的标签使用简写符号...”: 这是一个为了简化绘图的便利用法说明。
• $\Sigma \setminus \{a\}$: 这个集合符号表示在字母表 $\Sigma$ 中除去字符 $a$ 之外的所有其他字符。如果 $\Sigma = \{a, b, c\}$，那么 $\Sigma \setminus \{a\}$ 就代表 $\{b, c\}$。在图上画一条标有 $\Sigma \setminus \{a\}$ 的边，就等价于画两条边，一条标 'b'，一条标 'c'，都指向同一个目标状态。这大大减少了图的复杂度。
• “确保在你的图中指定起始状态和接受状态”: 这是一个非常重要的评分点。一个完整的状态转移图必须明确：
• 起始状态 (start state): 通常用一个指向它的、没有源头的箭头来表示。
• 接受状态 (accept states): 通常用双层圆圈来表示。

缺少任何一个，自动机的定义都是不完整的。

这是一个典型的自动机设计问题，需要将文字描述的规则转化为机器模型。我们来逐条分析规则并构思自动机的状态。

规则分析:

1. “每个 0 后面紧跟着一个 1，每个 1 后面紧跟着一个 2，每个 2 后面紧跟着一个 0。”
   • 这是一个非常严格的“后继”规则。它定义了一个固定的循环模式： $0 \to 1 \to 2 \to 0 \to \dots$。
   • 这意味着字符串的形式必然是 $(012)^k$, $(120)^k$, $(201)^k$ 的前缀或它们的一部分。例如 "01201", "12012", "201" 等是合法的序列，但 "02", "11", "010" 都是非法的。
   • 这个规则可以用三个状态来建模，分别代表“上一个字符是0/1/2”。
   • 从一个状态（比如叫 $q_0$），读到 '0'，必须转移到状态 $q_1$。
   • 从状态 $q_1$，读到 '1'，必须转移到状态 $q_2$。
   • 从状态 $q_2$，读到 '2'，必须转移到状态 $q_0$。
   • 任何不符合这个模式的转移都应该进入一个“死状态”（trap state），即一个非接受状态，并且所有出边都指向自身。
2. “字符串以相同的符号开始和结束。”
   • 这个规则增加了对字符串整体的约束。它需要我们“记住”字符串的第一个字符是什么，以便在结尾进行比较。
   • 这启发我们，自动机的起始状态之后，需要根据第一个读入的字符（0, 1, 或 2）进入不同的“路径”或“分支”。每个分支负责追踪以特定符号开头的字符串。
   • 例如，如果以 '0' 开头，那么只有当自动机在处理完整个字符串后，恰好停在一个表示“刚刚读入的字符是0”的状态时，这个字符串才可能被接受。
3. “字符串的长度必须至少为 1。”
   • 这意味着空字符串 $\varepsilon$ 不在语言 $L$ 中。
   • 在自动机设计中，这意味着起始状态本身不能是接受状态。必须至少经过一次转移才能到达接受状态。

综合设计思路 (DFA):

我们可以设计一个 DFA。我们需要状态来编码两个信息：(1) 起始符号是什么，以及 (2) 上一个符号是什么，以便验证后继规则。

• 起始状态 $q_{start}$: 初始状态，非接受。
• 分支路径:
• 从 $q_{start}$ 读到 '0'，进入一个以 '0' 开头的路径。我们用状态 $q_{0,end}$ 表示“以0开头，且上一个符号是0”。
• 从 $q_{start}$ 读到 '1'，进入一个以 '1' 开头的路径。我们用状态 $q_{1,end}$ 表示“以1开头，且上一个符号是1”。
• 从 $q_{start}$ 读到 '2'，进入一个以 '2' 开头的路径。我们用状态 $q_{2,end}$ 表示“以2开头，且上一个符号是2”。
• 状态定义:
• $q_{start}$: 起始状态。
• $q_{0, \text{start}}$: 以 0 开头的路径的初始状态。
• $q_{1, \text{start}}$: 以 1 开头的路径的初始状态。
• $q_{2, \text{start}}$: 以 2 开头的路径的初始状态。
• $q_{0,1}$: 以 0 开头，且上一个符号是 0，下一个期望是 1。
• $q_{0,2}$: 以 0 开头，且上一个符号是 1，下一个期望是 2。
• $q_{1,2}$: 以 1 开头，且上一个符号是 1，下一个期望是 2。
• $q_{1,0}$: 以 1 开头，且上一个符号是 2，下一个期望是 0。
• $q_{2,0}$: 以 2 开头，且上一个符号是 2，下一个期望是 0。
• $q_{2,1}$: 以 2 开头，且上一个符号是 0，下一个期望是 1。
• $q_{trap}$: 死状态。

这个状态设计有点复杂。让我们简化一下。状态可以只表示“上一个读到的符号是什么”，然后根据起始符号来决定哪些状态是接受状态。

简化版 DFA 设计思路:

• $q_{start}$: 起始状态。
• $q_0$: 状态，代表“上一个读入的符号是0”。
• $q_1$: 状态，代表“上一个读入的符号是1”。
• $q_2$: 状态，代表“上一个读入的符号是2”。
• $q_{trap}$: 死状态。

转移函数 $\delta$:

• 从 $q_{start}$:
• $\delta(q_{start}, 0) = q_0$
• $\delta(q_{start}, 1) = q_1$
• $\delta(q_{start}, 2) = q_2$
• 从 $q_0$:
• $\delta(q_0, 1) = q_1$ (满足规则 $0 \to 1$)
• $\delta(q_0, 0) = q_{trap}$ (违反规则)
• $\delta(q_0, 2) = q_{trap}$ (违反规则)
• 从 $q_1$:
• $\delta(q_1, 2) = q_2$ (满足规则 $1 \to 2$)
• $\delta(q_1, 0) = q_{trap}$ (违反规则)
• $\delta(q_1, 1) = q_{trap}$ (违反规则)
• 从 $q_2$:
• $\delta(q_2, 0) = q_0$ (满足规则 $2 \to 0$)
• $\delta(q_2, 1) = q_{trap}$ (违反规则)
• $\delta(q_2, 2) = q_{trap}$ (违反规则)
• 从 $q_{trap}$:
• $\delta(q_{trap}, 0) = q_{trap}$
• $\delta(q_{trap}, 1) = q_{trap}$
• $\delta(q_{trap}, 2) = q_{trap}$

这个设计满足了规则1和规则3。但如何处理规则2（起始和结束符号相同）？

上述设计无法区分起始符号。我们需要更复杂的状态。

最终 DFA 设计思路:

• $q_{start}$: 起始状态, 非接受。
• $q_{s0}, q_{s1}, q_{s2}$: 分别代表读入了起始符号 0, 1, 2。
• $q_{s0}$ 是接受状态 (因为长度为1的 "0" 满足所有条件)。
• $q_{s1}$ 是接受状态 (因为长度为1的 "1" 满足所有条件)。
• $q_{s2}$ 是接受状态 (因为长度为1的 "2" 满足所有条件)。
• 中间状态:
• $q_{p1}$: 代表序列是 $...1$
• $q_{p2}$: 代表序列是 $...2$
• $q_{p0}$: 代表序列是 $...0$

这些状态需要区分起始符号来决定是否接受。这太复杂了。

让我们尝试 NFA，它可能更直观。

NFA 设计思路:

我们可以创建三个并行的“轨道”，分别对应以 '0', '1', '2' 开头的合法字符串。

• 轨道0 (为以 '0' 开头的字符串):
• $q_{start} \xrightarrow{0} q_{0,start}$ (状态 $q_{0,start}$ 表示以0开头，且上一个是0，它是接受状态)
• $q_{0,start} \xrightarrow{1} q_{0,1}$ (状态 $q_{0,1}$ 表示以0开头，上一个是1，非接受)
• $q_{0,1} \xrightarrow{2} q_{0,2}$ (状态 $q_{0,2}$ 表示以0开头，上一个是2，非接受)
• $q_{0,2} \xrightarrow{0} q_{0,start}$ (回到接受状态，形成环)

• 轨道1 (为以 '1' 开头的字符串):
• $q_{start} \xrightarrow{1} q_{1,start}$ (状态 $q_{1,start}$ 表示以1开头，上一个是1，是接受状态)
• $q_{1,start} \xrightarrow{2} q_{1,2}$ (非接受)
• $q_{1,2} \xrightarrow{0} q_{1,0}$ (非接受)
• $q_{1,0} \xrightarrow{1} q_{1,start}$ (回到接受状态)

• 轨道2 (为以 '2' 开头的字符串):
• $q_{start} \xrightarrow{2} q_{2,start}$ (状态 $q_{2,start}$ 表示以2开头，上一个是2，是接受状态)
• $q_{2,start} \xrightarrow{0} q_{2,0}$ (非接受)
• $q_{2,0} \xrightarrow{1} q_{2,1}$ (非接受)
• $q_{2,1} \xrightarrow{2} q_{2,start}$ (回到接受状态)

这个 NFA 设计清晰地分离了三种情况。总共需要 1 (起始) + 3*3 = 10个状态。

• States: $Q = \{q_{start}, q_{0,start}, q_{0,1}, q_{0,2}, q_{1,start}, q_{1,2}, q_{1,0}, q_{2,start}, q_{2,0}, q_{2,1}\}$
• Start State: $q_{start}$
• Accept States: $F = \{q_{0,start}, q_{1,start}, q_{2,start}\}$
• Transitions:
• $\delta(q_{start}, 0) = \{q_{0,start}\}$
• $\delta(q_{start}, 1) = \{q_{1,start}\}$
• $\delta(q_{start}, 2) = \{q_{2,start}\}$
• 轨道0: $\delta(q_{0,start}, 1) = \{q_{0,1}\}, \delta(q_{0,1}, 2) = \{q_{0,2}\}, \delta(q_{0,2}, 0) = \{q_{0,start}\}$
• 轨道1: $\delta(q_{1,start}, 2) = \{q_{1,2}\}, \delta(q_{1,2}, 0) = \{q_{1,0}\}, \delta(q_{1,0}, 1) = \{q_{1,start}\}$
• 轨道2: $\delta(q_{2,start}, 0) = \{q_{2,0}\}, \delta(q_{2,0}, 1) = \{q_{2,1}\}, \delta(q_{2,1}, 2) = \{q_{2,start}\}$
• 所有其他未定义的转移都去往一个隐含的死状态。

这个问题描述了一个“禁止模式”的语言。具体来说，禁止出现 "a...a" 这样的片段，而中间的 "..." 部分不包含 'm'。我们可以通过状态来追踪是否刚刚看到了一个 'a' 以及之后是否已经看到了 'm'。

规则分析:

• “任意两个 $a$ 之间至少包含一个 $m$”: 这句话是核心。
• 我们可以把它反过来想：什么样的字符串是“不合法”的？如果一个字符串包含子串 $a x a$，其中 $x$ 是一个不包含 'm' 的字符串（即 $x \in \{a, b, \dots, l, n, \dots, z\}^*$），那么这个字符串就是不合法的。
• 例如，"papa" 中的 "apa" 就是这样一个非法子串 ($x$ 是 'p'，不含 'm')。 "panamerican" 中的 "anamerica" 也是 ($x$ 是 "nameric"，不含 'm')。
• 语言中的合法字符串包括：
• 不包含 'a' 的字符串 (如 "john")。
• 只包含一个 'a' 的字符串 (如 "abc")。
• 包含多个 'a'，但每对 'a' 之间都有 'm' 的字符串 (如 "mama", "american" 中的 "a...m...a")。

DFA 设计思路:

我们可以设计一个 DFA，其状态代表我们当前所处的“危险等级”。

• 状态 0 ($q_0$): “安全”状态。这是起始状态。在这个状态下，我们要么还没见过 'a'，要么上一个 'a' 之后已经见过一个 'm' 了，警报已解除。
• 状态 1 ($q_1$): “危险”状态。我们刚刚看到了一个 'a'，但还没有看到 'm' 来“解除”这个 'a' 的危险。如果在这个状态下再看到一个 'a'，就意味着出现了 "a...a" 且中间没有 'm' 的情况，字符串非法。
• 状态 2 ($q_{trap}$): “死”状态或“陷阱”状态。一旦进入这个状态，就说明我们已经检测到了一个非法的模式，此后的任何输入都无法挽救这个字符串。

状态转移图设计:

• 字母表: $\Sigma = \{a, b, \dots, z\}$。为了简化，我们将 $\Sigma$ 分为三类：$\{a\}$, $\{m\}$, 和 $\Sigma \setminus \{a, m\}$ (我们称之为 "other")。

• States:
• $q_0$: 起始状态，也是接受状态。
• $q_1$: “刚见过 a”状态，也是接受状态（因为字符串可能就在这里结束，例如 "abc a" 是合法的）。
• $q_{trap}$: 死状态，非接受状态。

• Transitions $\delta$:
• 从 $q_0$ (安全状态):
• 读到 'm': 留在 $q_0$。mama 中的第一个 'm'。
• 读到 "other": 留在 $q_0$。john。
• 读到 'a': 进入危险状态 $q_1$。abc 中的 'a'。
• $\delta(q_0, m) = q_0$
• $\delta(q_0, \text{other}) = q_0$
• $\delta(q_0, a) = q_1$

• 从 $q_1$ (危险状态，刚见过 'a'):
• 读到 'm': 危险解除，回到安全状态 $q_0$。mama 中的 'am' 部分。
• 读到 "other": 危险持续，留在 $q_1$。papa 中的 "ap" 部分。
• 读到 'a': 灾难！我们又看到了一个 'a'，但中间没有 'm'。进入死状态 $q_{trap}$。papa 中的 "apa" 部分。
• $\delta(q_1, m) = q_0$
• $\delta(q_1, \text{other}) = q_1$
• $\delta(q_1, a) = q_{trap}$

• 从 $q_{trap}$ (死状态):
• 读到任何字符（'a', 'm', "other"）: 留在 $q_{trap}$。
• $\delta(q_{trap}, \Sigma) = q_{trap}$

• Start State: $q_0$
• Accept States: $F = \{q_0, q_1\}$。为什么 $q_1$ 也是接受状态？因为一个以 'a' 结尾的字符串是合法的，例如 "ma"。在处理完 "ma" 后，自动机停在 $q_1$，它应该被接受。只要没进入死状态，字符串到目前为止就是合法的。

这是一个判断语言正则性的问题。这个语言 $L$ 的定义是“重复自身”的形式，这通常是非正则语言的一个强烈信号。我们需要使用泵引理来证明它。

语言分析:

• $L = \{ww \mid \dots \}$: 语言中的每个字符串都是某个字符串 $w$ 的精确复制。例如，如果 $w = "011"$, 那么 $ww = "011011" \in L$。
• $w \in \{0,1\}^*$: $w$ 是由 0 和 1 组成的任意字符串。
• $w$ 包含至少一个 0 和至少一个 1: 这是对 $w$ 的一个附加条件。这意味着 $w$ 不能是 $0^*$ 或 $1^*$ 形式的。例如，$w="001"$ 是合法的，但 $w="000"$ 或 $w="11"$ 是不合法的。因此，$ww="001001" \in L$，但 "000000" 和 "1111" 不在 $L$ 中（即使它们是 $w'w'$ 的形式，但 $w'$ 不满足条件）。

直觉判断:

要识别这个语言，机器需要读完前半部分 $w$，将其完整地“记住”，然后与后半部分进行逐一比较。有限自动机 (DFA/NFA) 只有有限的状态，无法记住任意长度的 $w$。这暗示 $L$ 不是正则的。我们将使用泵引理来形式化这个直觉。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。那么泵引理成立，存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w_{str} \in L$，使得 $|w_{str}| \ge p$。这是最关键的一步。我们需要选择一个结构化的、与 $p$ 相关的字符串，使得泵送操作会破坏其结构。
   • 一个好的选择是让 $w$ 的形式为 $0^k1^m$。为了满足 $|ww| \ge p$ 并且结构清晰，我们选择一个简单的 $w$。
   • 令 $w = 0^p1$。这个 $w$ 满足条件“包含至少一个0和至少一个1”。
   • 那么，我们用于泵引理的字符串是 $w_{str} = ww = 0^p10^p1$。
   • 这个字符串 $w_{str} \in L$，并且其长度 $|w_{str}| = 2p+2 \ge p$。
3. 应用泵引理的分割: 根据泵引理，$w_{str}$ 可以被分割为 $xyz$，满足以下条件：
   • $w_{str} = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w_{str} = \underbrace{00\dots0}_{p \text{ times}}10^p1$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 '0' 里面。
   • 所以，$x$ 必然是 $0^a$ 的形式，其中 $a \ge 0$。
   • $y$ 必然是 $0^b$ 的形式，其中 $b \ge 1$ (因为 $|y|>0$)。
   • $z$ 则是剩下的部分，即 $0^{p-a-b}10^p1$。
   • $a+b \le p$。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 泵引理声称，对于所有 $i \ge 0$，$xy^iz$ 都必须在 $L$ 中。
   • 我们选择 $i=2$ 进行泵送（增加'y'）。
   • $xy^2z = xyyz = (0^a)(0^b)(0^b)(0^{p-a-b}10^p1) = 0^{p+b}10^p1$。
   • 现在我们需要判断这个新字符串 $0^{p+b}10^p1$ 是否还在 $L$ 中。
   • 一个在 $L$ 中的字符串必须是 $u u$ 的形式。如果 $0^{p+b}10^p1$ 是 $u u$ 的形式，它的总长度必须是偶数。总长度是 $(p+b)+1+p+1 = 2p+b+2$。
   • 它的中点在哪里？在第 $(2p+b+2)/2 = p + b/2 + 1$ 个字符之后。因为 $b \ge 1$ 并且是整数，所以 $b/2$ 不一定是整数，这个分割点很难处理。

让我们换一种更清晰的泵送方式。选择 $i=0$ (删除'y')。

• 选择 $i=0$。
• $xy^0z = xz = (0^a)(0^{p-a-b}10^p1) = 0^{p-b}10^p1$。
• 这个新字符串是 $w' = 0^{p-b}10^p1$。
• 我们来判断 $w'$ 是否在 $L$ 中。如果它在 $L$ 中，它必须能被写成 $u u$ 的形式，其中 $u$ 包含至少一个0和一个1。
• $w'$ 的总长度是 $(p-b)+1+p+1 = 2p-b+2$。
• 要成为 $uu$ 的形式，它必须能被从中间完美地分成两个相同的部分。
• 它的前半部分应该是 $u$，长度为 $(2p-b+2)/2 = p - b/2 + 1$。
• 它的后半部分也应该是 $u$，长度也为 $p - b/2 + 1$。
• 由于 $b \ge 1$，所以 $b$ 是一个正整数。
• 如果 b 是奇数，那么 $b/2$ 不是整数，总长度是奇数，一个奇数长度的字符串永远不可能写成 $uu$ 的形式。所以 $w' \notin L$。
• 如果 b 是偶数，那么总长度是偶数。前半部分 $u$ 的长度是 $p-b/2+1$。
• 前半部分 $u = 0^{p-b}1$。它的长度是 $(p-b)+1$。
• 后半部分是 $0^p1$。它的长度是 $p+1$。
• 为了让 $w'$ 成为 $uu$ 的形式，前半部分必须等于后半部分。
• 但我们有 $b \ge 1$ (实际上，因为 $b$ 是偶数，所以 $b \ge 2$)。
• $p-b+1 < p+1$。
• $0^{p-b}1$ 不可能等于 $0^p1$。
• 因此，即使 $b$ 是偶数，前后两半也不相等。所以 $w' \notin L$。

• 综上所述，无论 $b$ 是奇数还是偶数，只要 $b \ge 1$，泵送后的字符串 $xy^0z$ 都不在 $L$ 中。

1. 结论: 我们找到了一个 $i=0$，使得 $xy^iz \notin L$。这与泵引理矛盾。因此，我们最初的假设“$L$是正则的”是错误的。

最终结论: $L$ 是非正则的。

这是一个判断语言正则性的问题。语言的规则是 $c$ 的数量必须等于 $a$ 的数量加上 $b$ 的数量。这需要进行加法计数，而有限自动机无法存储任意大的计数值。这强烈暗示该语言是非正则的。我们将使用泵引理来证明。

语言分析:

• $L = \{a^i b^j c^k \mid i+j=k\}$: 字符串由三部分组成，先是任意数量的 $a$，然后是任意数量的 $b$，最后是任意数量的 $c$。
• $i,j,k \ge 0$ 是整数。
• 核心约束是：$k = i+j$。$c$ 的数量等于 $a$ 和 $b$ 的数量之和。

直觉判断:

要识别这个语言，机器需要：

1. 读取并计数 $a$ 的数量 (得到 $i$)。
2. 读取并计数 $b$ 的数量 (得到 $j$)。
3. 将这两个计数值相加。
4. 读取并计数 $c$ 的数量，并与前两步的和进行比较。

有限自动机的状态数量是有限的，它无法存储可能无限大的 $i$ 和 $j$ 的值来进行精确的加法和比较。因此，这个语言应该是非正则的。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。根据泵引理，存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w \in L$，使得 $|w| \ge p$。我们需要一个结构化的字符串来破坏 $i+j=k$ 这个平衡。
   • 一个好的选择是固定其中一个变量，让另一个与 $p$ 相关。
   • 令 $i=p$ 并且 $j=0$。那么根据规则， $k = p+0 = p$。
   • 我们选择的字符串是 $w = a^p c^p$。(注意 $b^0 = \varepsilon$ 是合法的)。
   • 这个字符串 $w \in L$ (因为 $i=p, j=0, k=p$，满足 $i+j=k$)。
   • 其长度 $|w| = 2p \ge p$。
3. 应用泵引理的分割: $w$ 可以被分割为 $xyz$，满足：
   • $w = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w = \underbrace{aa\dots a}_{p \text{ times}}\underbrace{cc\dots c}_{p \text{ times}}$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 'a' 里面。
   • 所以，$x$ 必然是 $a^m$ 的形式，其中 $m \ge 0$。
   • $y$ 必然是 $a^n$ 的形式，其中 $n \ge 1$ (因为 $|y|>0$)。
   • $z$ 则是剩下的部分，即 $a^{p-m-n}c^p$。
   • $m+n \le p$。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 泵引理声称，对于所有 $i' \ge 0$，$xy^{i'}z$ 都必须在 $L$ 中。(这里用 $i'$ 以区别于语言定义中的 $i$)
   • 我们选择 $i'=2$ 进行泵送。
   • $xy^2z = xyyz = (a^m)(a^n)(a^n)(a^{p-m-n}c^p) = a^{p+n}c^p$。
   • 现在我们来判断这个新字符串 $w' = a^{p+n}c^p$ 是否还在 $L$ 中。
   • 这个新字符串的形式是 $a^{i_{new}}b^{j_{new}}c^{k_{new}}$。
   • $i_{new} = p+n$
   • $j_{new} = 0$
   • $k_{new} = p$
   • 为了让 $w'$ 在 $L$ 中，必须满足 $i_{new} + j_{new} = k_{new}$。
   • 即 $(p+n) + 0 = p$。
   • 化简得到 $p+n = p$，这意味着 $n=0$。
   • 但是，根据泵引理的条件，$|y|>0$，所以 $n$ (即 $y$ 的长度) 必须大于等于 1。
   • 这就产生了一个矛盾：$n$ 必须为 0，但 $n$ 又必须大于等于 1。
6. 结论: 我们选择 $i'=2$ 泵送后得到的字符串 $xy^2z$ 不满足 $L$ 的条件，因此 $xy^2z \notin L$。这与泵引理矛盾。所以我们最初的假设“$L$是正则的”是错误的。

另一种选择: 我们也可以选择 $w = a^p b^p c^{2p}$，或者 $w = b^p c^p$。使用 $w = a^p c^p$ 的好处是它结构更简单，分割 $y$ 的可能性只有一种。

最终结论: $L$ 是非正则的。

这是一个判断语言正则性的问题。语言的形式是：以 $k$ 个0开头，以 $k$ 个1结尾，中间夹着任意的字符串 $u$。

语言分析:

• $L = \{0^k u 1^k \mid k \ge 1, u \in \Sigma^*\}$
• $k \ge 1$: 开头的0和结尾的1的数量至少是1。
• $u \in \Sigma^*$: 中间的 $u$ 可以是任意由0和1组成的字符串，包括空字符串。
• 核心约束是：开头的0的数量必须和结尾的1的数量完全相等。

直觉判断:

要识别这个语言，机器需要：

1. 读取并计数开头的 $k$ 个0。
2. 将这个计数值 $k$ “记住”。
3. 读过中间任意的字符串 $u$。
4. 读取结尾的1，并与之前记住的 $k$ 进行比较，确保数量恰好为 $k$。

中间的 $u$ 是一个关键的迷惑项。因为 $u$ 可以包含任意的0和1，机器在读 $u$ 的时候，很容易“忘记”之前计数的 $k$ 值。例如，对于字符串 "0010111"，机器如何知道开头的 "00" 应该和结尾的哪两个 "1" 匹配？它无法分辨结尾的 "11" 是属于 $u$ 的一部分还是属于结尾的 $1^k$ 部分。

更重要的是，为了验证结尾 $1^k$ 的数量，机器必须记住开头 $0^k$ 的数量。由于 $k$ 可以是任意大的正整数，有限自动机的有限状态无法记住任意大的 $k$ 值。这强烈暗示语言是非正则的。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w \in L$，使得 $|w| \ge p$。
   • 我们需要一个结构化的字符串，其中 $k$ 的值与 $p$ 相关，并且中间的 $u$ 尽量简单，以避免混淆。最简单的 $u$ 就是空字符串 $\varepsilon$。
   • 令 $k=p$ 并且 $u=\varepsilon$。
   • 我们选择的字符串是 $w = 0^p 1^p$。
   • 这个字符串 $w \in L$ (因为 $k=p \ge 1$, $u=\varepsilon$)。
   • 其长度 $|w| = 2p \ge p$。
3. 应用泵引理的分割: $w$ 可以被分割为 $xyz$，满足：
   • $w = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w = \underbrace{00\dots 0}_{p \text{ times}}\underbrace{11\dots 1}_{p \text{ times}}$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 '0' 里面。
   • 所以，$y$ 必然是 $0^m$ 的形式，其中 $m \ge 1$ (因为 $|y|>0$)。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 泵引理声称，对于所有 $i' \ge 0$，$xy^{i'}z$ 都必须在 $L$ 中。
   • 我们选择 $i'=2$ 进行泵送。
   • $xy^2z = 0^{p+m}1^p$。
   • 现在我们来判断这个新字符串 $w' = 0^{p+m}1^p$ 是否还在 $L$ 中。
   • 为了让 $w'$ 在 $L$ 中，它必须能被写成 $0^j u' 1^j$ 的形式。
   • 在 $w'$ 中，所有0都在所有1的前面，所以 $u'$ 必须是空字符串。
   • 那么 $w'$ 的形式就是 $0^{p+m}1^p$。
   • 为了匹配 $0^j 1^j$ 的形式，开头的0的数量必须等于结尾的1的数量。
   • 即 $p+m$ 必须等于 $p$。
   • 这要求 $m=0$。
   • 但是，根据泵引理的条件，$|y|>0$，所以 $m$ 必须大于等于 1。
   • 这就产生了一个矛盾：$m$ 必须为 0，但 $m$ 又必须大于等于 1。
6. 结论: 泵送后的字符串 $xy^2z$ 不在 $L$ 中。这与泵引理矛盾。因此，我们最初的假设“$L$是正则的”是错误的。

最终结论: $L$ 是非正则的。

这个问题与上一个问题非常相似，但有一个微小而关键的区别。这里的语言是 $\{0^k 1 u 1^k\}$。

语言分析:

• $L = \{0^k 1 u 1^k \mid k \ge 1, u \in \Sigma^*\}$
• $k \ge 1$: 开头的0和结尾的1的数量至少是1。
• $u \in \Sigma^*$: 中间的 $u$ 可以是任意字符串。
• 核心结构是：一段 $0^k$，后面紧跟着一个单个的 '1'，然后是任意字符串 $u$，最后是一段 $1^k$。

直觉判断:

与上一个问题一样，这个问题似乎也需要匹配开头 $0^k$ 和结尾 $1^k$ 的数量。这看起来仍然需要无限的记忆。但是，中间的那个孤立的 '1' 是一个非常重要的“分隔符”或“标记”。

让我们重新思考一下自动机能否识别它。一个非确定性有限自动机 (NFA) 可以做“猜测”。

NFA 能否识别这个语言?

1. NFA 可以先读开头的 $k$ 个0。但它不知道 $k$ 是多少。
2. 然后它读到一个 '1'。这是一个关键点。NFA 可以“猜测”：这个 '1' 是不是那个重要的分隔符 '1'？
3. 猜测1: 假设这个 '1' 就是分隔符。NFA 进入一个新模式。在这个模式里，它需要验证接下来是否有 $k$ 个 '1'。但它已经忘了 $k$ 是多少了。所以这个猜测行不通。

让我们反过来想，从后往前看。

一个 NFA 无法从后往前读。但是，证明一个语言 $L$ 是正则的，等价于证明它的反转语言 $L^R = \{w^R \mid w \in L\}$ 是正则的（因为正则语言在反转操作下是封闭的）。

• $L^R = \{ (0^k 1 u 1^k)^R \mid k \ge 1, u \in \Sigma^* \}$
• $= \{ (1^k)^R u^R (0^k 1)^R \mid k \ge 1, u \in \Sigma^* \}$
• $= \{ 1^k (u^R) 1 0^k \mid k \ge 1, u \in \Sigma^* \}$

令 $v = u^R$。因为 $u$ 可以是 $\Sigma^*$ 中的任意字符串，所以 $u^R$ 也可以是 $\Sigma^*$ 中的任意字符串。所以 $v$ 也是任意字符串。

• $L^R = \{ 1^k v 1 0^k \mid k \ge 1, v \in \Sigma^* \}$

这个反转语言 $L^R$ 是什么样子的？它以 $k$ 个 '1' 开头，然后是任意字符串 $v$，然后是一个 '1'，最后是 $k$ 个 '0'。

这个语言和原始语言 $L$ 几乎一模一样，也需要匹配开头和结尾的数量。所以反转这条路似乎也没能简化问题。

回到最初的判断：它很可能是非正则的。 我们再次尝试使用泵引理。

证明 $L$ 是非正则的 (使用泵引理):

1. 假设 $L$ 是正则的。存在一个泵长度 $p > 0$。
2. 选择一个字符串 $w \in L$，使得 $|w| \ge p$。
   • 为了突出 $0^k$ 和 $1^k$ 的对应关系，并简化问题，我们选择 $u$ 为空字符串。
   • 令 $k=p$。
   • 我们选择的字符串是 $w = 0^p 1 1^p$。
   • 这个字符串 $w \in L$ (因为 $k=p \ge 1, u=\varepsilon$)。
   • 其长度 $|w| = p+1+p = 2p+1 \ge p$。
3. 应用泵引理的分割: $w$ 可以被分割为 $xyz$，满足：
   • $w = xyz$
   • $|xy| \le p$
   • $|y| > 0$
4. 分析分割:
   • 我们的字符串是 $w = \underbrace{00\dots 0}_{p \text{ times}}11^p$。
   • 因为 $|xy| \le p$，所以 $x$ 和 $y$ 两部分都必须完全落在开头的 $p$ 个 '0' 里面。
   • 所以，$y$ 必然是 $0^m$ 的形式，其中 $m \ge 1$ (因为 $|y|>0$)。
5. 选择 $i$ 进行泵送并导出矛盾:
   • 我们选择 $i=2$ 进行泵送。
   • $xy^2z = 0^{p+m} 1 1^p$。
   • 现在我们来判断这个新字符串 $w' = 0^{p+m} 1 1^p$ 是否还在 $L$ 中。
   • 为了让 $w'$ 在 $L$ 中，它必须能被写成 $0^j 1 u' 1^j$ 的形式，其中 $j \ge 1$。
   • $w'$ 的结构是：一串0，跟着一串1。
   • 要匹配 $0^j 1 u' 1^j$ 的形式，它必须有一个孤立的 '1' 作为分隔符。
   • $w' = 0^{p+m} 1^ {p+1}$。这里面根本没有孤立的 '1'，它就是一堆0跟着一堆1。
   • 如果我们要强行匹配，比如我们把 $0^{p+m}$ 当作 $0^j$，把结尾的 $1^p$ 当作 $1^j$，那么 $j$ 就必须同时等于 $p+m$ 和 $p$，这不可能。
   • 更严谨地说，要匹配 $0^j 1 u' 1^j$ 的形式，$w'$ 必须能被分割成 (一串0) + '1' + (任意串) + (一串1)。
   • $w' = 0^{p+m} 1 1^p$。
   • 这里的第一个 '1' 就是那个分隔符 '1'。
   • 那么，开头的0串是 $0^{p+m}$，所以 $j$ 应该是 $p+m$。
   • 结尾的1串是 $1^p$，所以 $j$ 应该是 $p$。
   • 所以，我们需要 $p+m = p$，这意味着 $m=0$。
   • 但是，根据泵引理，$|y|>0$，所以 $m \ge 1$。
   • 这又是一个矛盾。
6. 结论: 泵送后的字符串 $xy^2z$ 不在 $L$ 中。这与泵引理矛盾。因此，假设“$L$是正则的”是错误的。

等一下，这个结论对吗？让我们重新审视一下。

难道这个问题是正则的吗？我刚才的直觉判断和证明似乎都指向非正则。但是这个问题紧跟在问题5后面，形式非常相似，这可能是一个陷阱，暗示答案可能不同。

让我们尝试构造一个正则表达式或自动机。

如果它是正则的，那么一定存在一个正则表达式。

$L = \{0^k 1 u 1^k \mid k \ge 1, u \in \Sigma^*\}$

• $k=1$: $01u1$。 正则表达式: $01(0|1)^*1$。
• $k=2$: $001u11$。 正则表达式: $001(0|1)^*11$。
• $k=3$: $0001u111$。 正则表达式: $0001(0|1)^*111$。
• ...

$L$ 是所有这些的并集: $01(0|1)^*1 \cup 001(0|1)^*11 \cup 0001(0|1)^*111 \cup \dots$

这是一个无限的并集。正则语言只在有限并集下封闭。所以这个思路不能证明它是正则的。

回到泵引理的证明，检查是否有漏洞。

证明过程是：

1. 选 $w = 0^p 1 1^p$。
2. $y$ 在开头的 $0^p$ 里， $y=0^m, m \ge 1$。
3. 泵送得到 $0^{p+m} 1 1^p$。
4. 要求 $p+m = p$，得出 $m=0$ 的矛盾。

这个证明看起来是无懈可击的。它与证明 $\{0^n1^n\}$ 非正则的逻辑是完全一样的。那个孤立的 '1' 并没有改变需要两端计数的本质。

那会不会问题5才是正则的，而问题6是非正则的？

让我们重新检查问题5: $L_5 = \{0^k u 1^k \mid k \ge 1, u \in \Sigma^*\}$

这个语言的证明也是完全一样的逻辑。选 $w = 0^p 1^p$ (即 $u=\varepsilon$)。泵送开头的0，破坏了与结尾1的数量平衡。

结论: 两个语言都是非正则的，并且证明方法基本相同。

也许这组题目的目的就是让学生辨析这种微小差异是否会影响正则性。在这种情况下，这个分隔符 '1' 并没有提供足够的信息来消除对无限内存的需求。

最终确认: 我的泵引理证明逻辑没有问题。问题6的语言是非正则的。

这是一个具有挑战性的问题，需要更深入的分析。我们需要计算两种不同子串 ab 和 ba 的出现次数，并比较它们是否相等。

语言分析:

• $L = \{w \in \{a,b\}^* \mid \text{count}(w, "ab") = \text{count}(w, "ba") \}$
• count(w, "sub") 表示子串 "sub" 在 $w$ 中出现的次数。
• 例如:
• $w = \text{"aabbbaa"}$
• ab 在索引1处出现一次。
• ba 在索引4处出现一次。
• 次数相等 (1=1)，所以 "aabbbaa" $\in L$。
• $w = \text{"ab"}$
• ab 出现1次，ba 出现0次。不等，所以 "ab" $\notin L$。
• $w = \text{"aba"}$
• ab 出现1次，ba 出现1次。相等，所以 "aba" $\in L$。
• $w = \text{"baba"}$
• ba 出现2次，ab 出现1次。不等，所以 "baba" $\notin L$。
• 空字符串 $\varepsilon$: ab 出现0次，ba 出现0次。相等，所以 $\varepsilon \in L$。
• 单个字符: 'a' 或 'b'。ab 和 ba 都出现0次。相等，所以 'a', 'b' $\in L$。
• 单一字符重复: $a^k$ 或 $b^k$。ab 和 ba 都出现0次。相等，所以 $a^k, b^k \in L$。

寻找规律:

让我们观察 ab 和 ba 的出现如何改变计数的差异。令 diff = count("ab") - count("ba")。我们的目标是 diff = 0。

• 在一个字符串的末尾追加一个字符，看 diff 如何变化。
• 假设我们有一个字符串 $w$。
• 如果 $w$ 以 'a' 结尾，我们追加一个 'b'，得到 $wb$。
• ab 的计数增加1。diff 增加1。
• 如果 $w$ 以 'a' 结尾，我们追加一个 'a'，得到 $wa$。
• ab 和 ba 的计数都不变。diff 不变。
• 如果 $w$ 以 'b' 结尾，我们追加一个 'a'，得到 $wa$。
• ba 的计数增加1。diff 减少1。
• 如果 $w$ 以 'b' 结尾，我们追加一个 'b'，得到 $wb$。
• ab 和 ba 的计数都不变。diff 不变。

这个观察非常重要！计数的差异 diff 只在字符串末尾发生 a 和 b 交替时才改变。

• ...a $\to$ ...ab (diff++)
• ...b $\to$ ...ba (diff--)

进一步分析:

• 一个字符串从头开始。
• 扫描字符串，忽略连续相同的字符，只看字符变化的点。
• 'ab' 对应一次从 'a' 到 'b' 的变化。
• 'ba' 对应一次从 'b' 到 'a' 的变化。
• count("ab") 就是字符串中从 'a' 变为 'b' 的次数。
• count("ba") 就是字符串中从 'b' 变为 'a' 的次数。

考虑一个字符串 $w$。

• 如果 $w$ 为空，或 $w$ 只由 'a' 或 'b' 组成，那么 count("ab") = count("ba") = 0。这些字符串在 $L$ 中。
• 如果 $w$ 既有 'a' 也有 'b'，它必然以某个字符开始，以某个字符结束。
• Case 1: $w$ 以 'a' 开头，以 'a' 结尾。
• 例如: a...b...a...b...a。
• 每一次从 'a' 到 'b' 的转换，后续必然会有一次从 'b' 回到 'a' 的转换，才能最终以 'a' 结尾。
• a -> b 的次数必然等于 b -> a 的次数。
• 因此，count("ab") = count("ba")。
• Case 2: $w$ 以 'b' 开头，以 'b' 结尾。
• 同理，b -> a 的次数必然等于 a -> b 的次数。
• count("ab") = count("ba")。
• Case 3: $w$ 以 'a' 开头，以 'b' 结尾。
• 例如: a...b...a...b。
• 第一次转换是 a -> b。为了以 'b' 结尾，最后一次转换必然是 a -> b。
• a -> b 的次数会比 b -> a 的次数多 1。
• count("ab") = count("ba") + 1。
• Case 4: $w$ 以 'b' 开头，以 'a' 结尾。
• 例如: b...a...b...a。
• b -> a 的次数会比 a -> b 的次数多 1。
• count("ba") = count("ab") + 1。

结论:

一个字符串 $w$ 属于语言 $L$ (即 count("ab") == count("ba")) 当且仅当:

1. $w$ 不包含 'a' 或不包含 'b' (例如 $\varepsilon, a, b, aaa, bbb$)。
2. 或者，$w$ 的第一个字符和最后一个字符相同。

这个结论非常简洁和强大。现在我们可以基于这个新的、等价的定义来判断正则性。

证明 $L$ 是正则的:

我们可以把 $L$ 分解成几个简单的正则语言的并集。

• $L_1$: 不包含 'a' 的字符串。正则表达式为: $b^*$。
• $L_2$: 不包含 'b' 的字符串。正则表达式为: $a^*$。
• $L_3$: 以 'a' 开头，并以 'a' 结尾的字符串。正则表达式为: $a(a|b)^*a$。
• $L_4$: 以 'b' 开头，并以 'b' 结尾的字符串。正则表达式为: $b(a|b)^*b$。

但是这个分解不完全正确，它没有包含长度为1的字符串 'a' 和 'b'。

修正后的分解:

• $L_a = \{w \mid w \text{ 以 'a' 开头和结尾} \}$。正则表达式: $a | a(a|b)^*a$。
• $L_b = \{w \mid w \text{ 以 'b' 开头和结尾} \}$。正则表达式: $b | b(a|b)^*b$。
• $L_{no\_ab} = \{w \mid w \text{ 中没有'a'或没有'b'} \}$。正则表达式: $a^* | b^*$。
• $L = L_a \cup L_b \cup L_{no\_ab}$。
• 更准确地， $L$ 就是所有满足“首尾字符相同”或“只含一种字符”的字符串。
• 这个集合可以被描述为：

1. 空字符串: $\varepsilon$
2. 只有一个字符: $a, b$
3. 由单一字符组成: $a^+$ (一个或多个a), $b^+$ (一个或多个b)
4. 以 'a' 开头和结尾，且长度大于1: $a(a|b)^*a$
5. 以 'b' 开头和结尾，且长度大于1: $b(a|b)^*b$

• 一个更简洁的正则表达式可以覆盖所有这些情况：
• $\varepsilon$
• $a(a|b)^*a$
• $b(a|b)^*b$
• $a^+$
• $b^+$
• $a$
• $b$
• 正则表达式 $a(a|b)^*a$ 已经包含了 $a^+$ (当中间都是a时) 和 $a$ (当中间的 $(a|b)^*$ 是 $\varepsilon$ 时，长度为2的 $aa$)，但不包含单个 'a'。
• 所以，一个完整的描述是: $L = \{w \mid w \text{ 的首尾字符相同}\} \cup \{\varepsilon\}$
• 语言 $\{w \mid w \text{ 的首尾字符相同}\}$:
• $a$
• $b$
• $a(a|b)^*a$
• $b(a|b)^*b$
• 所以这个语言的正则表达式是: $\varepsilon | a | b | a(a|b)^*a | b(a|b)^*b$。
• $a^* | b^*$ 这个也可以。$a^*$ 包含 $\varepsilon, a, aa, \dots$。$b^*$ 包含 $\varepsilon, b, bb, \dots$。他们的并集包含了所有单一字符组成的串。
• 那么 $L$ 到底是什么？是 $\{w \mid \text{首尾字符相同}\}$。
• 如果 $w$ 首尾字符相同，count("ab") = count("ba")。
• 如果 $w$ 首尾字符不同，count("ab") 和 count("ba") 相差1。
• 如果 $w$ 是空串或单字符或单字符重复，首尾字符也相同（或未定义但满足条件）。
• 所以， $L = \{ w \in \{a,b\}^* \mid w \text{ 的第一个字符等于最后一个字符} \} \cup \{\varepsilon\}$。
• 这个描述覆盖了所有情况。

构造一个识别 $L$ 的 NFA:

• 状态 $q_{start}$: 起始状态，也是接受状态 (为了接受 $\varepsilon$)。
• 轨道 a:
• $q_{start} \xrightarrow{a} q_a$ ( $q_a$ 是接受状态，接受单个 'a' )
• $q_a \xrightarrow{a,b} q_{mid\_a}$
• $q_{mid\_a} \xrightarrow{a,b} q_{mid\_a}$
• $q_{mid\_a} \xrightarrow{a} q_a$ (回到接受状态)
• 轨道 b:
• $q_{start} \xrightarrow{b} q_b$ ( $q_b$ 是接受状态，接受单个 'b' )
• $q_b \xrightarrow{a,b} q_{mid\_b}$
• $q_{mid\_b} \xrightarrow{a,b} q_{mid\_b}$
• $q_{mid\_b} \xrightarrow{b} q_b$

这个 NFA 有点乱。让我们用 DFA 来追踪 “第一个字符” 和 “上一个字符”。

DFA 设计:

• $q_0$: 起始状态，接受 (for $\varepsilon$)
• $q_A$: 第一个字符是 'a'。接受 (for 'a')
• $q_B$: 第一个字符是 'b'。接受 (for 'b')
• $q_{A\_mid\_a}$: 首字符是 'a', 上一个字符是 'a'。接受。
• $q_{A\_mid\_b}$: 首字符是 'a', 上一个字符是 'b'。非接受。
• $q_{B\_mid\_a}$: 首字符是 'b', 上一个字符是 'a'。非接受。
• $q_{B\_mid\_b}$: 首字符是 'b', 上一个字符是 'b'。接受。

转移:

• $\delta(q_0, a) = q_A$
• $\delta(q_0, b) = q_B$
• $\delta(q_A, a) = q_{A\_mid\_a}$
• $\delta(q_A, b) = q_{A\_mid\_b}$
• $\delta(q_B, a) = q_{B\_mid\_a}$
• $\delta(q_B, b) = q_{B\_mid\_b}$
• $\delta(q_{A\_mid\_a}, a) = q_{A\_mid\_a}$
• $\delta(q_{A\_mid\_a}, b) = q_{A\_mid\_b}$
• $\delta(q_{A\_mid\_b}, a) = q_{A\_mid\_a}$
• $\delta(q_{A\_mid\_b}, b) = q_{A\_mid\_b}$
• $\delta(q_{B\_mid\_a}, a) = q_{B\_mid\_a}$
• $\delta(q_{B\_mid\_a}, b) = q_{B\_mid\_b}$
• $\delta(q_{B\_mid\_b}, a) = q_{B\_mid\_a}$
• $\delta(q_{B\_mid\_b}, b) = q_{B\_mid\_b}$

这个 DFA 太复杂了。简单的正则表达式证明已经足够了。

最终结论: 语言 $L$ 是正则的。

它的等价定义是：所有首尾字符相同的字符串（以及空字符串和单字符字符串）。

一个描述该语言的正则表达式是:

$R = a^* | b^* | a(a|b)^*a | b(a|b)^*b$

• $a^*$: 接受 $\varepsilon, a, aa, \dots$ (首尾相同)
• $b^*$: 接受 $\varepsilon, b, bb, \dots$ (首尾相同)
• $a(a|b)^*a$: 接受以a开头和结尾的，长度至少为2的串。
• $b(a|b)^*b$: 接受以b开头和结尾的，长度至少为2的串。

这个并集覆盖了所有情况。既然 $L$ 可以被一个正则表达式描述，那么 $L$ 是正则的。