11. 正则语言
📜 [原文1]
计算理论始于一个问题:什么是计算机?这或许是个愚蠢的问题,因为每个人都知道我正在敲字的这个东西就是计算机。但这些真实的计算机相当复杂——复杂到无法让我们直接建立一套可管理的数学理论。相反,我们使用一种理想化的计算机,称为计算模型。与任何科学模型一样,计算模型在某些方面可能准确,但在其他方面可能不准确。因此,我们将根据我们想要关注的特性,使用几种不同的计算模型。我们从最简单的模型开始,称为有限状态机或有限自动机。
📖 [逐步解释]
这段话是整个章节的引言,旨在说明我们为什么需要学习一个看似抽象的概念——计算模型,特别是最简单的一种,有限自动机。
- 提出核心问题:文章开篇就提出了一个根本性的问题:“什么是计算机?”。这不仅仅是指我们日常使用的笔记本电脑或智能手机,而是从理论层面探究“计算”这一行为的本质。
- 现实计算机的复杂性:作者指出,我们日常接触的真实计算机(如个人电脑)内部结构和工作原理极其复杂。它包含了中央处理器(CPU)、内存(RAM)、硬盘、操作系统、各种应用软件等等。如果想直接基于这种复杂的实体来建立一套严格、普适的数学理论,将会非常困难,甚至是不可能的。理论需要简洁和清晰,而现实计算机充满了工程细节和特例。
- 引入解决方案:计算模型**:为了解决现实世界计算机过于复杂的问题,理论计算机科学采用了一种科学研究中常用的方法——建模。我们不直接研究真实的、具体的计算机,而是创造和研究一个“理想化的计算机”,也就是计算模型**。
- 解释计算模型的本质:计算模型是一种数学上的抽象。它抓住了真实计算机最核心、最本质的特性(比如处理输入、改变状态、产生输出),而忽略了那些非本质的、使问题复杂化的细节(比如电源功耗、散热、具体电路实现等)。这就像在物理学中,我们用“质点”来代表一个物体,忽略其大小和形状,只关注其质量和位置,从而可以方便地应用牛顿定律。
- 模型的准确性与多样性:作者强调,任何模型都是对现实的一种简化,因此它必然有其局限性。一个模型可能在某个方面(比如逻辑判断)能很好地模拟真实计算机,但在另一方面(比如存储能力)可能与现实相去甚远。正因为没有一个模型是万能的,所以计算理论中会存在多种不同的计算模型。我们会根据需要研究的特性(例如,内存大小、计算能力)来选择合适的模型。
- 引出本章主角:有限自动机**:在众多计算模型中,我们从最简单、最基础的一种开始学起。这个模型被称为有限状态机(Finite State Machine, FSM)或有限自动机(Finite Automaton, FA)。“有限”这个词是关键,它暗示了这个模型**的内存或资源是有限的,这正是它“简单”的根源。
💡 [数值示例]
- 示例1:真实计算机的复杂性
- 我的笔记本电脑的CPU是Intel Core i7-12700H,它有14个核心,20个线程,最高频率4.7GHz,集成了数十亿个晶体管。内存是32GB的DDR5 RAM,硬盘是1TB的NVMe固态硬盘。操作系统是Windows 11,上面运行着浏览器、代码编辑器、聊天软件等几十个进程。要用一个数学公式完整描述它下一秒钟的状态几乎是不可能的。
- 示例2:计算模型的简化
- 物理学中的“自由落体”模型就是一个很好的类比。它假设一个物体只受重力影响,忽略了空气阻力、地球自转、风速等一切其他因素。这个模型($h = \frac{1}{2}gt^2$)虽然在真空中非常准确,但在现实世界(比如羽毛飘落)中就会有偏差。类似地,有限自动机这个模型,它可能只有几个“状态”,内存只有几“比特”,这与真实计算机的GB级内存天差地别,但它能帮助我们清晰地分析某些特定的计算问题。
⚠️ [易错点]
- 误解1:认为计算模型是某种真实存在的、简陋的物理机器。
- 纠正:计算模型是一个纯数学的、抽象的概念。它是一组规则和定义,存在于纸上和我们的思维中,而不是一个实体计算机。我们可以用软件模拟它,或者用硬件实现它,但模型本身是抽象的。
- 误解2:认为有限自动机因为“简单”而没有用处。
- 纠正:简单是相对的。正是因为它的“简单”(内存有限),使得我们可以对它进行彻底的数学分析,搞清楚它的能力边界。而且,这种“简单”的模型在现实世界中有着极其广泛的应用,比如编译器词法分析、协议栈的状态管理、各种电器的控制器等。
📝 [总结]
本段的核心思想是,为了能对“计算”这一行为进行严格的数学分析,我们不能直接研究复杂的真实计算机,而是需要借助简化的、理想化的计算模型。本章将从最基础的计算模型——有限自动机——开始探讨。
🎯 [存在目的]
本段的目的是为整个计算理论的学习设定一个基本框架和方法论。它回答了“我们为什么要学习这些抽象的模型?”这个问题,通过建立“现实世界太复杂 → 需要抽象模型 → 从最简单的模型开始”的逻辑链条,为后续引入有限自动机的形式化定义和理论做好了铺垫。
🧠 [直觉心智模型]
- 地图与真实世界:把真实的计算机想象成一个极其复杂的真实城市,有无数的街道、建筑、人流和交通规则。要想理解这个城市,直接一头扎进去会迷路。计算模型就像是这个城市的一张地图。地图简化了真实世界,它可能只画出了主干道(核心功能),忽略了小巷子(工程细节)。不同的地图有不同的用途:地铁图(关注公共交通)、旅游图(关注景点)、行政区划图(关注管理边界)。同样,不同的计算模型关注计算机的不同特性。有限自动机就是一张最简单的“街区示意图”。
💭 [直观想象]
想象你面前有一台最新款的顶级配置电脑,机箱打开,里面是密密麻麻的电路、风扇和各种线路,屏幕上同时运行着几十个软件窗口。这就是我们要研究的“真实对象”。现在,我们把目光移开,拿出一支笔和一张纸,在纸上画了几个圈,用箭头把它们连起来,并给箭头标上数字。纸上这个简单的图画,就是计算模型。我们接下来的所有讨论,都是围绕这张纸上的图画展开的,因为它虽然简单,却蕴含着“计算”的根本原理。
1.1. 节
11.1. 有限自动机
📜 [原文2]
有限自动机是计算机的良好模型,其内存量极其有限。具有如此小内存的计算机能做什么呢?许多有用的事情!事实上,我们一直都在与此类计算机交互,因为它们是各种机电设备的核心。
📖 [逐步解释]
这段话是有限自动机概念的引子,主要强调两点:它的核心特性和它的现实意义。
- 定义核心特性:内存极其有限。这是有限自动机的“灵魂”所在。“有限”不仅是指内存不是无限的,更是指内存的量是固定的、预先确定的,并且通常非常小。它不能像我们的个人电脑那样,在程序运行时动态申请更多内存。一个有限自动机在设计之初,它的“记忆能力”就被锁死了。
- 提出设问,引发思考:作者紧接着问:“具有如此小内存的计算机能做什么呢?”。这是一个非常巧妙的设问。在习惯了拥有巨大内存的现代计算机后,我们很自然地会怀疑一个内存极小的设备能有什么用。
- 给出肯定回答,并联系现实:作者立刻给出了响亮的回答:“许多有用的事情!”。为了证明这一点,他指出我们其实一直在与这类“计算机”打交道。它们并非只存在于理论中,而是广泛嵌入在我们身边的各种机电设备里,构成了这些设备控制逻辑的核心。这一下就拉近了抽象理论与日常生活的距离,告诉我们学习这个模型是有实际价值的。
💡 [数值示例]
- 示例1:电风扇的控制器
- 一个老式三档电风扇的控制器就是一个极简的有限自动机。它的内存只需要记录当前是哪个档位。比如用2个比特(bit)就够了:00代表“关闭”,01代表“1档”,10代表“2档”,11代表“3档”。它的内存就这么大,只有2比特,极其有限。它不需要记住昨天开了几档,也不需要上网,只需要根据你按下的按钮(输入)来切换自己的档位(状态)。
- 示例2:交通信号灯
- 一个十字路口的交通灯控制器也是一个有限自动机。它的内存需要记住当前是哪个方向是绿灯,以及绿灯亮了多久。比如它有几个状态:“东西绿灯”、“东西黄灯”、“南北绿灯”、“南北黄灯”。它的内存可能只需要几个比特来编码当前状态,以及一个简单的计时器。它根据时间流逝(输入)来顺序切换状态。它完全不需要记住10分钟前路口的交通流量。
⚠️ [易错点]
- 误解:“极其有限的内存”意味着完全没有内存。
- 纠正:不是没有内存,而是内存的容量是有限且固定的。这个有限的内存就是通过有限数量的“状态”来体现的。比如一个自动机有8个状态,我们可以认为它拥有3比特的内存($2^3=8$),可以记住8种不同的情况。关键在于,它不能在运行中把内存扩展到4比特。
📝 [总结]
本段明确了有限自动机最根本的特性是“内存极其有限”,并通过联系现实生活中的机电设备(如家电控制器),说明了这种看似简单的计算模型具有广泛的实用性,从而激发读者的学习兴趣。
🎯 [存在目的]
本段的目的是将抽象的有限自动机概念与读者熟悉的日常经验联系起来。通过强调其“有限内存”的特性和“广泛应用”的价值,消除读者可能产生的“这东西太理论、没用”的疑虑,为接下来通过自动门的例子具体展开有限自动机的工作原理做铺垫。
🧠 [直觉心智模型]
- 一个只有一页纸记忆的人:想象一个人,他的全部记忆能力就是在一张小纸条上写几个字。当有新信息来时,他只能根据旧信息和新信息,擦掉纸条上的字,写上新的字。这张纸条的尺寸是固定的,永远不能变大。这个人的“记忆”就是有限自动机的“状态”,纸条上的内容就是“当前状态”。尽管他的记忆力如此之差,但他仍然可以完成一些简单的任务,比如“记住现在轮到谁了”或者“记录开关是开还是关”。
💭 [直观想象]
想象你家里的微波炉。你按下一个按钮,它就开始转动加热。它的内部并不需要一个强大的电脑来思考“嗯,主人按了开始键,我应该启动磁控管……”。它内部只有一个非常简单的控制器,这个控制器只有少数几种“心情”(状态):“待机”、“加热中”、“已完成”。你按按钮(输入)就会改变它的“心情”(状态转换)。这个简单的控制器就是一个有限自动机的实例。
1.1.1.1. 自动门的例子
📜 [原文3]
自动门的控制器就是此类设备的一个例子。自动门通常出现在超市入口和出口处,当控制器感应到有人靠近时,自动门就会自动打开。自动门前方有一个踏板,用于检测即将走过门口的人的存在。门后方还有一个踏板,以便控制器能让门开足够长的时间,让行人完全通过,同时也能防止门在开启时撞到站在后面的人。这种配置如下图所示。

图 1.1
自动门顶视图
📖 [逐步解释]
这一段开始用一个非常具体和生活化的例子——自动门——来详细阐述有限自动机的工作原理。
- 提出实例:明确指出自动门控制器是有限自动机的一个典型应用。
- 描述场景:描述了自动门的常见应用场景(超市入口),及其基本功能(感应到人时自动打开)。
- 介绍输入设备:详细说明了自动门的传感器配置。这不是一个简单的传感器,而是两个踏板(pad):
- 前方踏板(FRONT):位于门的入口侧,用来检测即将进入的人。
- 后方踏板(REAR):位于门的出口侧。
- 解释双踏板设计的目的:作者特意解释了为什么需要两个踏板,这对于理解控制逻辑至关重要。
- 让门保持开启:当一个人从前面走到后面,控制器能感知到他还没有完全走远,从而保持门是打开的,避免夹到人。
- 防止开门伤人:如果门是关着的,而此时有人站在后方踏板上,门不应该打开,否则可能会撞到这个人。这体现了更精细的安全逻辑。
- 提供视觉辅助:通过图1.1的顶视图,直观地展示了门、墙、前方踏板和后方踏板的相对位置。这有助于读者在脑海中建立一个清晰的物理场景。
💡 [数值示例]
- 场景1:正常进入
- 一个顾客走向超市,他首先踩到前方踏板。控制器接收到这个信号。然后他穿过门,踩到后方踏板。最后他完全走过,两个踏板都无人站立。控制器需要正确处理这一系列信号,完成“开门-保持打开-关门”的流程。
- 场景2:安全保护
- 门是关着的。一个小孩在门后(出口侧)的后方踏板上玩耍。这时,另一个顾客从门外(入口侧)走来,踩上了前方踏板。在这种情况下,一个设计良好的控制器不应该立即开门,因为它感应到后方有人,开门可能会撞到小孩。
⚠️ [易错点]
- 边界情况:如果一个人同时踩在两个踏板上(比如脚很大,或者两个人一前一后挤在一起),控制器应该如何反应?这是一种需要明确定义的输入情况。
- 传感器信号:现实中的踏板传感器不是理想的,可能会有信号抖动(快速地“踩上-离开-踩上”),或者感应延迟。理论模型通常会忽略这些物理层面的不完美,假设输入信号是清晰、离散的。
📝 [总结]
本段通过描述超市自动门的物理设置(两个踏板)和功能需求(方便通行与保证安全),为接下来介绍其控制逻辑(即有限自动机的状态和转移)提供了具体的现实背景。
🎯 [存在目的]
本段的目的是将有限自动机这个抽象概念具象化。选择自动门这个例子非常巧妙,因为它足够简单,只涉及两种状态(开/关)和几种输入,但其逻辑又不是完全平凡的,需要一定的“智能”来处理,这恰好能体现有限自动机解决实际问题的能力。这为读者理解状态、输入、转移等核心概念搭建了一个直观的脚手架。
🧠 [直觉心智模型]
- 一个只看脚下,记忆力很差的门卫:想象一个门卫,他看不到人,只能感觉到他脚下两块地毯(前方踏板、后方踏板)是否有人踩着。他的记忆力极差,只能记住一件事:“门现在是开着还是关着”。当他感觉到地毯上的变化时,他会根据一个非常简单的规则手册来决定是继续保持现状,还是去开门/关门。这个门卫和他的规则手册,就是一个自动门控制器。
💭 [直观想象]
想象一下你站在超市门口,低头看着脚下的黑色橡胶踏板。你先踩上门前的那一块,门“哗”地一下打开了。你走进去,脚离开了第一块踏板,踩上了门里的第二块踏板,门依然保持打开。等你完全走进去,脚离开了第二块踏板,门在你身后缓缓关上。这个流畅的过程背后,就是一个简单的有限自动机在按照预设的规则忠实地执行任务。
1.1.1.2. 控制器的状态与输入
📜 [原文4]
控制器处于两种状态之一:“OPEN”或“CLOSED”,分别表示门的相应状况。如下图所示,有四种可能的输入条件:“FRONT”(表示有人站在门前踏板上),“REAR”(表示有人站在门后踏板上),“BOTH”(表示有人站在两个踏板上),以及“NEITHER”(表示两个踏板上都没人)。

图 1.2
自动门控制器的状态图
|
|
NEITHER |
FRONT |
REAR |
BOTH |
| 状态 |
CLOSED |
CLOSED |
OPEN |
CLOSED |
CLOSED |
|
OPEN |
CLOSED |
OPEN |
OPEN |
OPEN |
图 1.3
自动门控制器的状态转移表
📖 [逐步解释]
这一部分正式引入有限自动机的两个核心元素:状态和输入,并用两种标准形式——状态图和状态转移表——来描述它们之间的关系。
- 定义状态(States):
- 状态是有限自动机“记忆”的体现。对于自动门控制器,它的“记忆”只需要知道门是开着还是关着。
- 因此,它有两个状态:
- OPEN:门处于打开状态。
- CLOSED:门处于关闭状态。
- 有限自动机在任何时刻都必须处于且仅处于这些预定义状态中的一个。
- 定义输入(Inputs):
- 输入是驱动自动机改变状态的外部信号。对于自动门,输入来自于两个踏板的组合情况。
- 两个踏板,每个都有“被踩上”和“未被踩上”两种可能,所以组合起来共有 $2 \times 2 = 4$ 种可能的输入条件:
- FRONT:只有前方踏板被踩。
- REAR:只有后方踏板被踩。
- BOTH:前后两个踏板都被踩。
- NEITHER:两个踏板都未被踩。
- 介绍两种表示法:
- 状态图(State Diagram, 图1.2):这是一种图形化的表示方法,非常直观。
- 圆圈/节点:代表状态。图中有两个圆圈,分别标为 CLOSED 和 OPEN。
- 箭头/有向边:代表状态转移(Transition)。箭头从一个状态指向另一个(或指向自身),表示在某个输入下,状态发生了怎样的变化。
- 箭头上的标签:代表触发该转移的输入。例如,从 CLOSED 指向 OPEN 的箭头上标有 FRONT,意味着当控制器处于 CLOSED 状态时,如果接收到 FRONT 输入,它将转移到 OPEN 状态。
- 状态转移表(State Transition Table, 图1.3):这是一种表格化的表示方法,更加严谨和精确,便于计算机程序实现。
- 行:代表当前状态(CLOSED, OPEN)。
- 列:代表输入信号(NEITHER, FRONT, REAR, BOTH)。
- 单元格内容:代表在“行”所表示的当前状态下,接收到“列”所表示的输入后,将要转移到的“下一个状态”。例如,在 OPEN 行和 NEITHER 列交叉的单元格中,内容是 CLOSED,这意味着当门是开着 (OPEN) 且前后都无人 (NEITHER) 时,门将转换到 CLOSED 状态。
💡 [数值示例]
- 示例1:查表法
- 当前状态:OPEN (门是开着的)
- 输入信号:REAR (有人站在门后)
- 在状态转移表(图1.3)中,找到 OPEN 这一行,再找到 REAR 这一列。两者交叉处的单元格内容是 OPEN。
- 结论:下一个状态仍然是 OPEN,门保持打开。
- 示例2:看图法
- 当前状态:CLOSED (门是关着的)
- 输入信号:FRONT (有人站在门前)
- 在状态图(图1.2)中,找到 CLOSED 这个圆圈。找到从 CLOSED 出发,并且标签是 FRONT 的箭头。
- 结论:这个箭头指向 OPEN 圆圈,所以下一个状态是 OPEN,门将打开。
⚠️ [易错点]
- 混淆状态和输入:初学者容易将状态(内部记忆)和输入(外部刺激)搞混。要牢记:状态是“我是谁/我在哪”(OPEN/CLOSED),输入是“发生了什么”(FRONT/REAR/BOTH/NEITHER)。自动机根据“我是谁”和“发生了什么”来决定“我将成为谁”。
- 认为状态图/转移表是唯一的:对于同一个问题,可能有多种功能等价的设计。例如,可以设计一个更复杂的有 OPENING(正在开门), CLOSING(正在关门)等中间状态的自动机。这里的模型是一个简化的版本。
📝 [总结]
本段落清晰地定义了自动门例子的状态(OPEN, CLOSED)和输入(FRONT, REAR, BOTH, NEITHER),并引入了两种描述有限自动机行为的标准工具:直观的状态图和严谨的状态转移表。
🎯 [存在目的]
本段的目的是将有限自动机的核心概念——状态、输入和转移——与自动门这个具体例子紧密结合起来,并教会读者如何使用状态图和状态转移表这两种形式化语言来精确描述一个有限自动机的逻辑。这是从非形式化描述到形式化描述的关键一步。
🧠 [直觉心智模型]
- 棋盘游戏:把状态想象成棋盘上的格子(比如“安全区”、“危险区”)。把输入想象成投掷的骰子(点数1到6)。状态转移表或状态图就像是游戏规则手册,它告诉你:“如果你现在在‘安全区’(当前状态),并且你掷出了3点(输入),那么你的棋子下一步应该移动到‘危险区’(下一个状态)”。
💭 [直观想象]
想象你是一个机器人,你的程序就是那张状态转移表(图1.3)。你的大脑里只有一个变量,current_state,它的值要么是 OPEN,要么是 CLOSED。你的眼睛连接着两个传感器,它们会告诉你一个输入值:FRONT, REAR, BOTH, 或 NEITHER。你的任务就是一个无限循环:1. 读取眼睛传来的输入值。2. 查阅你大脑里的那张表格,根据 current_state 和输入值找到新的状态。3. 更新你的 current_state。你不需要任何思考,只需要机械地、精确地查表和更新。
1.1.1.3. 控制器的行为分析
📜 [原文5]
控制器根据其接收到的输入从一个状态转移到另一个状态。当处于 CLOSED 状态并接收到 NEITHER 或 REAR 输入时,它保持在 CLOSED 状态。此外,如果接收到 BOTH 输入,它仍然保持 CLOSED 状态,因为开门有撞倒后方踏板上的人的风险。但如果 FRONT 输入到达,它会转移到 OPEN 状态。在 OPEN 状态下,如果接收到 FRONT、REAR 或 BOTH 输入,它会保持在 OPEN 状态。如果 NEITHER 输入到达,它会返回到 CLOSED 状态。
📖 [逐步解释]
这段话是对上一节给出的状态图和状态转移表所蕴含的逻辑规则的详细文字解读。它逐条分析了控制器在不同状态下,针对不同输入的行为,并解释了其背后的原因。
- 分析 CLOSED 状态下的行为:
- 输入 NEITHER 或 REAR → 状态 CLOSED:门是关的,外面没人或者只有人站在后面。这两种情况都符合“保持关闭”的逻辑。门没理由自己打开,也不能因为后面有人就打开。
- 输入 BOTH → 状态 CLOSED:门是关的,但前后都有人。这时,控制器选择保持关闭。作者特意解释了原因:“因为开门有撞倒后方踏板上的人的风险”。这是一个重要的安全考量,体现了设计的周密性。
- 输入 FRONT → 状态 OPEN:门是关的,有人从前面走来。这是最核心的开门逻辑。控制器接收到开门请求,转移到 OPEN 状态。
- 分析 OPEN 状态下的行为:
- 输入 FRONT、REAR 或 BOTH → 状态 OPEN:门是开的,只要前后两个踏板中至少有一个上面有人,门就应该保持打开状态,以确保行人能安全、从容地通过。
- 输入 NEITHER → 状态 CLOSED:门是开的,且前后都已无人。这意味着行人已经完全通过,门可以安全地关闭了。控制器转移回 CLOSED 状态。
通过这样分情况的详细讨论,原文将图和表中的抽象规则,转化为了符合直觉的、有因果关系的逻辑描述。
💡 [数值示例]
- 初始状态:CLOSED。输入:NEITHER。
- 顾客走到门前,踩上前方踏板。输入变为 FRONT。根据规则,控制器状态从 CLOSED 变为 OPEN。门打开了。
- 顾客接了个电话,后退了一步,脚离开了踏板。输入变为 NEITHER。根据规则,控制器状态从 OPEN 变为 CLOSED。门开始关闭。
- 顾客发现门在关,又立刻上前一步踩上前方踏板。输入变为 FRONT。根据规则,控制器状态再次从 CLOSED 变为 OPEN。门又打开了。
- 初始状态:CLOSED。输入:NEITHER。
- A从门外走来,踩上前方踏板。输入:FRONT。状态变为 OPEN。
- A走到门中间,同时踩上前后踏板。输入:BOTH。状态保持 OPEN。
- 此时,B从门内准备出去,也踩上了后方踏板。A走过,离开了前方踏板,但B还在后方踏板上。输入:REAR。状态保持 OPEN。
- B也完全走过,离开了后方踏板。输入变为 NEITHER。状态从 OPEN 变为 CLOSED。门关闭。这个过程保证了门在整个两人交汇通过期间都保持打开。
⚠️ [易错点]
- 忽略“自环”转移:在状态图中,指向自己的箭头(如 CLOSED 状态下的 REAR 输入)非常重要。它表示“保持当前状态不变”。初学者有时会只关注那些引起状态变化的转移,而忽略这些维持现状的规则,但它们同样是自动机完整逻辑的一部分。
- 理想化的时间模型:这里的分析是基于离散事件的。我们假设输入的变化和状态的转移是瞬时完成的。在现实世界中,门打开和关闭需要时间,这需要更复杂的模型(比如引入“OPENING”和“CLOSING”状态和计时器)来描述。但当前这个简化的模型已经足以展示有限自动机的核心思想。
📝 [总结]
本段用自然语言详细阐述了自动门控制器的完整工作逻辑,将状态转移表中的每一条规则都赋予了现实意义和设计考量(特别是安全性),使得读者能够深入理解为什么自动机要这么设计。
🎯 [存在目的]
本段的目的是“翻译”和“解读”前面给出的形式化表示(图和表)。它在抽象的状态和转移与具体的应用场景逻辑之间架起了一座桥梁,确保读者不仅知道自动机“做什么”(CLOSED -> OPEN),还知道“为什么这么做”(因为有人在前面,需要开门)。这种对设计意图的解释是培养工程思维和问题建模能力的重要一环。
🧠 [直觉心智模型]
- 红绿灯逻辑:这段分析就像在解释为什么“红灯停,绿灯行”。CLOSED 状态就像“红灯”,OPEN 状态就像“绿灯”。FRONT 输入就像是行人按下了过街按钮,触发了从“红灯”到“绿灯”的变化。NEITHER 输入就像是传感器检测到人已走过,可以切换回“红灯”了。而 REAR 或 BOTH 输入在门开着时就像是“只要还有人没走完,绿灯就得一直亮着”。
💭 [直观想象]
想象你正在玩一个简单的电脑游戏。屏幕上有一个门,旁边有两个按钮:“FRONT”和“REAR”。你是一个小人,你可以用鼠标点击这两个按钮。游戏规则(程序的if-else语句)就是这段文字描述的逻辑。
- 如果门是关的,你只点“FRONT”,门就打开。
- 如果门是关的,你点“REAR”或同时点“FRONT”和“REAR”,门没反应。
- 如果门是开的,你只要点着至少一个按钮,门就一直开着。
- 如果门是开的,你把所有按钮都松开,门就关上了。
这段文字就是这个简单游戏的“游戏说明书”。
1.1.1.4. 控制器执行序列示例
📜 [原文6]
例如,一个控制器可能从 CLOSED 状态开始,接收到一系列输入信号:FRONT、REAR、NEITHER、FRONT、BOTH、NEITHER、REAR 和 NEITHER。然后它将经历一系列状态:CLOSED(起始)、OPEN、OPEN、CLOSED、OPEN、OPEN、CLOSED、CLOSED 和 CLOSED。
📖 [逐步解释]
这一段通过一个具体的、连续的输入序列,完整地演示了有限自动机的运行过程。这是一个“将理论付诸实践”的步骤,让读者可以亲手(或在脑海中)模拟自动机的计算。
让我们一步一步地追踪这个过程,对照着图1.3的状态转移表:
- 起始:
- 初始状态:CLOSED。
- 状态序列:[CLOSED]
- 第1个输入:FRONT
- 当前状态:CLOSED。
- 输入:FRONT。
- 查表/看图:从 CLOSED 接收 FRONT,转移到 OPEN。
- 新状态:OPEN。
- 状态序列:[CLOSED, OPEN]
- 第2个输入:REAR
- 当前状态:OPEN。
- 输入:REAR。
- 查表/看图:从 OPEN 接收 REAR,保持在 OPEN。
- 新状态:OPEN。
- 状态序列:[CLOSED, OPEN, OPEN]
- 第3个输入:NEITHER
- 当前状态:OPEN。
- 输入:NEITHER。
- 查表/看图:从 OPEN 接收 NEITHER,转移到 CLOSED。
- 新状态:CLOSED。
- 状态序列:[CLOSED, OPEN, OPEN, CLOSED]
- 第4个输入:FRONT
- 当前状态:CLOSED。
- 输入:FRONT。
- 查表/看图:从 CLOSED 接收 FRONT,转移到 OPEN。
- 新状态:OPEN。
- 状态序列:[CLOSED, OPEN, OPEN, CLOSED, OPEN]
- 第5个输入:BOTH
- 当前状态:OPEN。
- 输入:BOTH。
- 查表/看图:从 OPEN 接收 BOTH,保持在 OPEN。
- 新状态:OPEN。
- 状态序列:[CLOSED, OPEN, OPEN, CLOSED, OPEN, OPEN]
- 第6个输入:NEITHER
- 当前状态:OPEN。
- 输入:NEITHER。
- 查表/看图:从 OPEN 接收 NEITHER,转移到 CLOSED。
- 新状态:CLOSED。
- 状态序列:[CLOSED, OPEN, OPEN, CLOSED, OPEN, OPEN, CLOSED]
- 第7个输入:REAR
- 当前状态:CLOSED。
- 输入:REAR。
- 查表/看图:从 CLOSED 接收 REAR,保持在 CLOSED。
- 新状态:CLOSED。
- 状态序列:[CLOSED, OPEN, OPEN, CLOSED, OPEN, OPEN, CLOSED, CLOSED]
- 第8个输入:NEITHER
- 当前状态:CLOSED。
- 输入:NEITHER。
- 查表/看图:从 CLOSED 接收 NEITHER,保持在 CLOSED。
- 新状态:CLOSED。
- 状态序列:[CLOSED, OPEN, OPEN, CLOSED, OPEN, OPEN, CLOSED, CLOSED, CLOSED]
最终,这个过程完整地复现了原文给出的状态序列。
💡 [数值示例]
- 示例1(原文示例):如上文逐步解释所示。
- 示例2:一个更简单的序列
- 输入序列:FRONT, NEITHER
- 状态序列的推演:
- 起始:CLOSED
- 输入 FRONT:CLOSED -> OPEN
- 输入 NEITHER:OPEN -> CLOSED
- 最终状态序列:[CLOSED, OPEN, CLOSED]。这个过程模拟了一个人正常进门后,门自动关闭的场景。
⚠️ [易错点]
- 状态序列的长度:注意,一个长度为 N 的输入序列,会产生一个长度为 N+1 的状态序列。因为状态序列还包含一个初始状态。在原文例子中,8个输入产生了9个状态。这是一个常见的计数细节错误。
- 起始状态的重要性:所有的计算都必须从一个确定的起始状态开始。如果起始状态不确定,那么对于同一个输入序列,最终的结果可能就不同了。
📝 [总结]
本段提供了一个具体、可操作的例子,展示了有限自动机如何处理一个输入序列并相应地生成一个状态序列。这使得自动机的“计算”过程变得清晰可见。
🎯 [存在目的]
本段的目的是将静态的规则(状态图和转移表)动态化。通过模拟一个运行实例,它让读者从“知道规则”提升到“会用规则”,巩固了对状态转移过程的理解。这就像学了象棋规则后,看一个完整的棋局演示,能更好地理解规则如何应用。
🧠 [直觉心智模型]
- 跟随乐谱的演奏者:输入序列就像一段乐谱,上面按顺序写着一个个音符。状态就像你手指在钢琴上的位置(比如“中央C位置”或“高音区位置”)。状态转移表就是你的训练记忆,告诉你“在中央C位置,如果下一个音符是Do,手就保持不动;如果是Sol,手就移动到高音区”。你从一个指定的起始位置开始,然后严格按照乐谱一个一个音符地弹下去,你的手就会在钢琴上划出一道轨迹,这就是状态序列。
💭 [直观想象]
想象一条长长的纸带,上面依次写着 FRONT, REAR, NEITHER, ...。你有一个小机器人,它站在标有 CLOSED 的地砖上。机器人有一个读头,指向纸带的第一个符号 FRONT。
- 机器人读取 FRONT,查询自己的规则手册,手册说“在CLOSED地砖上读到FRONT,请移动到OPEN地砖”。机器人移动到OPEN地砖。
- 读头自动移到纸带的下一个符号 REAR。
- 机器人读取 REAR,查询手册,“在OPEN地砖上读到REAR,请停在原地”。机器人不动。
- 读头移动到下一个符号...
这个过程一直持续到纸带末尾。机器人走过的地砖序列,就是状态序列。
1.1.1.5. 有限自动机作为通用模型
📜 [原文7]
将自动门控制器视为有限自动机是有用的,因为它提示了如图 1.2 和 1.3 所示的标准表示方法。这个控制器是一个只有一位内存的计算机,能够记录控制器处于哪两种状态。其他常见设备拥有内存稍大的控制器。在电梯控制器中,一个状态可能代表电梯所在的楼层,输入可能是从按钮接收到的信号。这个计算机可能需要几位来跟踪这些信息。各种家用电器(如洗碗机和电子恒温器)以及数字手表和计算器的某些部件的控制器,是具有有限内存的计算机的其他例子。这些设备的设计需要牢记有限自动机的方法论和术语。
📖 [逐步解释]
这段话将自动门的例子进行拔高和推广,阐述了将这些简单的控制器看作有限自动机的普遍意义和好处。
- 抽象的好处:将自动门控制器的逻辑抽象成有限自动机,最大的好处是我们可以使用标准化的工具(状态图和状态转移表)来清晰地、无歧义地描述和分析它。这使得不同背景的工程师或设计师有了一套共同语言。
- 状态与内存的等价关系:作者明确指出了状态和内存之间的关系。自动门控制器有两个状态(OPEN, CLOSED),这等价于它拥有1比特(bit)的内存。一个比特可以表示两种情况(0或1),正好对应CLOSED和OPEN。这是对“有限自动机内存极其有限”这一核心概念的量化解释。
- 扩展到更复杂的例子:
- 电梯控制器:这是一个内存稍大的例子。
- 状态:可以是电梯当前所在的楼层(如1楼, 2楼, ..., 30楼)。如果一栋楼有32层,那么至少需要5比特的内存来表示当前在哪一层($2^5=32$)。此外,状态还需要记录电梯是上行、下行还是静止。
- 输入:可以是电梯内部的楼层按钮、外部的上下按钮、门传感器信号等。
- 其他例子:作者列举了一系列家用电器和电子产品,如洗碗机、恒温器、数字手表、计算器,指出它们的核心控制逻辑都可以被建模为有限自动机。例如:
- 洗碗机的状态可能是:待机、进水、加热、主洗、漂洗、烘干、完成。
- 恒温器的状态可能是:制冷、制热、送风、待机。
- 方法论的价值:最后,作者强调,在设计这类设备时,脑子里有有限自动机的这套方法论(状态、输入、转移、图、表)是非常有帮助的。它提供了一种结构化的思维方式来处理离散的、基于事件的控制逻辑问题。
💡 [数值示例]
- 示例1:内存与状态数量
- 一个设备有3比特的内存。它最多可以表示 $2^3 = 8$ 个不同的状态。它可以被建模为一个最多有8个状态的有限自动机。
- 反之,一个有限自动机有10个状态。为了用二进制来编码这些状态,我们至少需要4比特的内存,因为 $2^3 = 8 < 10$,而 $2^4 = 16 \geq 10$。
- 示例2:数字手表的模式切换
- 一个简单的数字手表有3种模式:显示时间、秒表、闹钟设置。
- 状态:TIME_DISPLAY, STOPWATCH, ALARM_SET. 共3个状态,需要2比特内存。
- 输入:有一个“模式”按钮。
- 转移:
- 在TIME_DISPLAY状态,按“模式”按钮 -> 转移到STOPWATCH状态。
- 在STOPWATCH状态,按“模式”按钮 -> 转移到ALARM_SET状态。
- 在ALARM_SET状态,按“模式”按钮 -> 转移到TIME_DISPLAY状态。
- 这是一个非常清晰的3状态有限自动机。
⚠️ [易错点]
- 高估有限自动机的能力:虽然有限自动机很有用,但它不能解决所有问题。比如,它无法实现一个通用的计算器(可以计算任意长度的数字加法),因为这需要无限的内存来存储数字。它只能处理那些“记忆”需求是有限且固定的任务。计算器中可以用有限自动机实现的部分是像按键的逻辑处理,而不是数值计算本身。
📝 [总结]
本段的核心观点是,有限自动机是一个强大且普适的抽象模型,适用于描述和设计任何具有有限、离散状态和输入的控制系统。通过将具体问题“翻译”成有限自动机,我们可以利用一套标准化的理论和工具来进行分析和设计,并且明确了状态数量与所需内存大小之间的数学关系。
🎯 [存在目的]
本段的目的是将有限自动机从自动门这一个例子的“特殊解”提升为一类问题的“通解”。通过展示其在电梯、家电等多种设备中的适用性,作者建立了有限自动机作为一种基础“方法论”的地位,强调了学习它的普遍价值,而不仅仅是为了理解自动门。
🧠 [直觉心智模型]
- 流程图:有限自动机的状态图本质上就是一种非常严格、形式化的流程图。状态是流程中的某个环节(比如“等待用户输入”),输入是触发流程走向的条件(比如“用户点击了‘确定’按钮”),转移就是流程的走向。任何可以用有限个步骤和判断来描述的流程,都有可能被建模为有限自动机。
💭 [直观想象]
想象一下你在设计一个智能家居系统。你想让灯光在不同时间、根据是否有人在家,呈现不同模式。你可以随性地写一堆if-else代码,但很快就会乱掉。或者,你可以先拿出一张纸,画出这个系统的所有可能“状态”:清晨模式、离家模式、回家模式、影院模式、睡眠模式。然后画出触发这些状态改变的“输入”:时间到达7点、检测到主人离家、主人按下“电影”按钮。再用箭头把它们连接起来。你画出的这张图,就是一个有限自动机,它成为了你编写代码的清晰蓝图。
1.1.1.6. 有限自动机的其他应用
📜 [原文8]
有限自动机及其概率对应物马尔可夫链是我们在尝试识别数据模式时的有用工具。这些设备用于语音处理和光学字符识别。马尔可夫链甚至被用于建模和预测金融市场中的价格变化。
📖 [逐步解释]
这段话进一步拓宽了有限自动机的应用领域,从前面提到的硬件控制器,延伸到了软件和数据科学领域,并引入了一个与之密切相关的概念——马尔可夫链。
- 新的应用领域:识别数据模式:
- 前面讨论的应用(门、电梯)主要是“控制”类任务。这里提出了一个全新的应用方向:“识别”(Recognition)。
- “数据模式识别”是指从一连串的数据(如文本、语音、图像)中找出符合特定规律的部分。例如,从一段英文文本中找出所有的合法邮箱地址。
- 具体应用举例:
- 语音处理(Speech Processing):在语音识别中,一个单词的发音可以被看作是一个音素(phoneme)的序列。一个有限自动机可以被设计用来识别一个特定的单词。例如,单词"cat"的发音由音素 /k/, /æ/, /t/ 组成。我们可以构建一个自动机,它依次接收这些音素,最终达到一个“识别成功”的状态。
- 光学字符识别(Optical Character Recognition, OCR):类似地,识别一个手写或印刷的字母,也可以看作是匹配一个像素模式的过程。
- 引入相关概念:马尔可夫链(Markov Chain):
- 作者提到了有限自动机的“概率对应物”——马尔可夫链。这是一个非常重要的引申。
- 与有限自动机的关系:
- 相同点:两者都有“状态”和“转移”。
- 不同点:在经典的有限自动机中,给定当前状态和输入,下一个状态是唯一确定的(这种叫确定性有限自动机)。而在马尔可夫链中,从一个状态到另一个状态的转移是概率性的。它不会说“一定”到哪个状态,而是说“有 70% 的概率”到状态A,“有 30% 的概率”到状态B。
- 马尔可夫链的应用:因为引入了概率,马尔可夫链非常适合对不确定的、随机的现实世界现象进行建模。
- 金融市场:股票价格的涨跌具有随机性,但可能也存在一些统计规律。马尔可夫链可以用来建模:如果今天股票是“上涨”状态,那么明天有多大概率继续“上涨”,多大概率变为“下跌”或“盘整”状态。通过这种方式来做预测。
- 其他应用还包括:天气预测、搜索引擎的PageRank算法、自然语言处理中的N-gram模型等。
💡 [数值示例]
- 示例1:有限自动机用于模式匹配
- 任务:在一个由a, b, c组成的字符串中,识别是否出现子串 "ab"。
- 自动机设计:
- 状态0 (初始状态): 还没看到"a"。
- 状态1: 刚看到了一个"a"。
- 状态2 (成功状态): 已经看到了"ab"。
- 转移:
- 在状态0,输入a -> 状态1;输入b或c -> 状态0。
- 在状态1,输入b -> 状态2;输入a -> 状态1 (新的"a"开始了);输入c -> 状态0。
- 在状态2,输入任何字符 -> 状态2 (一旦成功,就永远成功)。
- 输入串 "acab" 的处理:状态0 ->(a) -> 状态1 ->(c) -> 状态0 ->(a) -> 状态1 ->(b) -> 状态2。成功识别!
- 示例2:马尔可夫链建模天气
- 状态:晴天 (Sunny), 雨天 (Rainy)。
- 转移概率(以表格表示):
| 当前 \ 下一天 |
晴天 |
雨天 |
| 晴天 |
0.9 |
0.1 |
| 雨天 |
0.5 |
0.5 |
- 解读:如果今天是晴天,那么明天有90%的概率还是晴天,10%的概率会下雨。如果今天是雨天,那么明天有50%的概率转晴,50%的概率继续下雨。
- 这就是一个简单的马尔可夫链,它用概率描述了状态转移。
⚠️ [易错点]
- 混淆有限自动机和马尔可夫链:要记住核心区别:有限自动机是确定性的(对于一个输入,转移是固定的),而马尔可夫链是概率性的(转移是按概率分布的)。可以把确定性有限自动机看作是一种特殊的马尔可夫链,其所有转移概率要么是1(100%),要么是0。
📝 [总结]
本段将有限自动机的应用从硬件控制领域拓展到更广泛的数据模式识别领域(如语音处理),并顺势引入了其在概率世界中的“近亲”——马尔可夫链,展示了状态转移模型这一思想在建模和预测随机现象(如金融市场)中的强大威力。
🎯 [存在目的]
本段的目的是展示“状态机”这一核心思想的普适性和强大生命力。通过连接到数据科学、人工智能和金融等更“时髦”的领域,进一步提升了学习这一基础理论的重要性。它暗示了我们正在学习的不仅仅是一个孤立的计算模型,而是一个可以演化、适配到不同问题领域的强大思维框架。
🧠 [直觉心智模型]
- 食谱 vs 营养师建议:
- 有限自动机就像一本精确的食谱:第一步放3克盐,第二步加热到80度,第三步搅拌5分钟... 步骤和结果都是确定的。
- 马尔可夫链就像一位营养师的建议:“如果你今天吃了蔬菜,明天继续吃蔬菜的可能性会增加。如果你今天吃了垃圾食品,明天你可能会有一半的几率想吃点健康的,但也有一半的几率会继续放纵。” 它描述的是一种趋势和概率,而不是一个确定的指令。
💭 [直观想象]
想象你在玩一个桌面游戏。
- 有限自动机版:游戏地图上画着单向的轨道。每个岔路口都有一个牌子写着“如果你掷出的是偶数,走左边;奇数,走右边”。你的每一步都是由规则定死的。
- 马尔可夫链版:游戏地图的岔路口没有明确的指示。只有一个向导告诉你:“从这里出发,大约有70%的冒险者会选择去森林,30%的会选择去沼泽。” 你下一步去哪里,需要掷一个概率骰子来决定,充满了不确定性。
1.1.1.7. 理论探讨的开始
📜 [原文9]
我们现在将从数学角度更仔细地审视有限自动机。我们将发展有限自动机的精确定义、描述和操作有限自动机的术语,以及描述其能力和局限性的理论结果。除了让您更清楚地理解有限自动机是什么以及它们能做什么和不能做什么之外,这种理论发展还将使您能够在一个相对简单的环境中练习并更适应数学定义、定理和证明。
在开始描述有限自动机的数学理论时,我们抽象地进行,不涉及任何特定的应用。下图描绘了一个称为 $M_{1}$ 的有限自动机。

图 1.4
一个名为 $M_{1}$ 的有限自动机,它有三个状态
📖 [逐步解释]
这段话是一个重要的转折点,标志着我们从非正式、直观的例子(如自动门)转向严格、抽象的数学探讨。
- 宣告研究方法的转变:明确提出要“从数学角度更仔细地审视有限自动机”。这意味着接下来的内容会更加形式化、更加抽象。
- 设定学习目标:作者列出了接下来要做的几件事,为读者设定了清晰的学习路线图:
- 精确定义 (Formal Definition):给出有限自动机的数学定义,不再是模糊的描述。
- 术语 (Terminology):学习一套标准的词汇来描述和操作自动机。
- 理论结果 (Theoretical Results):推导出关于有限自动机的定理,用以描述它的能力(能做什么)和局限性(不能做什么)。
- 阐述双重学习目的:学习这套理论有两个好处:
- 具体层面:深入理解有限自动机这个模型本身。
- 通用层面:这是一个“新手村”。因为有限自动机相对简单,所以它提供了一个绝佳的练习平台,让读者适应和习惯数学家和理论计算机学家使用的语言:定义、定理和证明。这对后续学习更复杂的理论至关重要。
- 开始抽象分析:宣告从这里开始,我们将暂时抛开具体的应用场景(如自动门),转而研究一个纯粹抽象的自动机例子,名为 $M_{1}$。
- 引入第一个抽象例子 $M_1$:通过图1.4,展示了一个具体的、但没有特定应用背景的有限自动机的状态图。这是接下来进行形式化分析的“标本”。
💡 [数值示例]
- 类比学习编程语言:
- 非正式学习:就像你通过看别人写的代码例子来模仿学习编程,比如看一个“打印九九乘法表”的例子。这很直观,但你可能不理解为什么代码要那么写。
- 形式化学习:就像你开始系统学习这门语言的官方文档。你会学习它的“语法规范”(精确定义)、“关键字列表”(术语)、“标准库函数”(能力)以及“编译器限制”(局限性)。虽然枯燥,但这让你能真正掌握这门语言,而不仅仅是模仿。
- 练习平台:用这门语言先去写一些“Hello World”或者“计算1+1”的简单程序(相对简单的环境),来练习你学到的语法和规则(练习定义、定理、证明)。
⚠️ [易错点]
- 畏惧抽象:从具体例子到抽象定义的转换,对很多初学者来说是一个挑战。可能会觉得“没有实际背景,不知道它在干嘛”。
- 应对策略:要认识到这种抽象是必要的,它是从“会用”到“会创造”和“会分析”的必经之路。在学习抽象定义时,要频繁地与前面具体的自动门例子或图1.4这个新的例子联系起来,看看抽象定义中的每一个部分对应到具体例子中是什么。
📝 [总结]
本段作为承上启下的枢纽,宣告了学习重点的转移:从对有限自动机的直观、案例式理解,转向对其进行严格的数学形式化和理论分析。作者阐明了这样做的必要性和双重好处,并通过引入一个纯抽象的自动机 $M_1$ 作为范例,开启了理论探讨的序幕。
🎯 [存在目的]
本段的目的是管理读者的学习预期,并论证接下来内容虽然会变得抽象,但这种抽象是有价值的。它像一位老师在切换教学模式前对学生说:“好了,我们已经通过玩游戏感受了基本规则,现在我们要坐下来,把规则手册上的每一条都读懂、掰碎了分析,这能让你成为真正的高手,还能让你以后自己设计游戏。”
🧠 [直觉心智模型]
- 从学开车到学汽车原理:
- 前面的内容就像在驾校学开车。教练告诉你方向盘怎么打,刹车怎么踩(自动门例子)。你学会了如何操作一辆车。
- 接下来的内容就像进入了汽车工程课堂。老师会给你讲发动机的定义(四冲程、排量)、术语(扭矩、功率)、定理(热力学定律)、能力(最高时速)和局限性(油耗、排放)。学完后,你不仅会开车,还懂车,甚至知道如何去设计和评估一辆车。
💭 [直观想象]
想象你一直是通过看图片和实物来认识各种动物的。现在,一位生物学家把你带进实验室,对你说:“从现在开始,我们不看动物本身了,我们来看它们的基因序列和分类学定义。” 他在白板上画出了一个叫 $M_1$ 的生物的骨架图(图1.4),说:“我们将从分析这个‘模式生物’的结构开始,来学习整个动物界的普遍规律。”
11.2. 有限自动机 $M_1$ 的结构与运行
📜 [原文10]
图 1.4 称为 $M_{1}$ 的状态图。它有三个状态,标记为 $q_{1}, q_{2}$ 和 $q_{3}$。起始状态 $q_{1}$ 由指向它的无源箭头表示。接受状态 $q_{2}$ 是双圆圈的那个。从一个状态到另一个状态的箭头称为转移。
📖 [逐步解释]
这段话是对图1.4所示的状态图 $M_1$ 的构成元素进行详细拆解和说明,引入了有限自动机状态图的几个标准术语和图形约定。
- 状态 (States):
- 图中的圆圈代表状态。
- 这个自动机 $M_1$ 有三个状态,它们的名字分别是 $q_1, q_2, q_3$。使用带下标的字母(如 $q_i$)是数学中表示一系列相关对象的通用惯例。
- 起始状态 (Start State):
- 自动机的计算必须从一个地方开始,这个地方就是起始状态。
- 图形约定:在状态图中,起始状态由一个“无源箭头”指向,即一个没有起点的箭头。在图1.4中,指向 $q_1$ 的那个箭头就是这个标志。
- 因此,$q_1$ 是 $M_1$ 的起始状态。一个有限自动机有且仅有一个起始状态。
- 接受状态 (Accept State):
- 接受状态也叫终止状态(Final State)。它用来判断自动机在处理完一个输入串后是否“同意”或“接受”这个输入串。
- 图形约定:在状态图中,接受状态被画成双圆圈。
- 在图1.4中,$q_2$ 被画成了双圆圈,所以它是接受状态。
- 一个有限自动机可以有零个、一个或多个接受状态。
- 转移 (Transitions):
- 连接状态的箭头被称为转移。
- 每个转移箭头上都标有输入符号(这里是0或1)。
- 它的含义是:如果自动机当前处于箭头的起始状态,并且接收到箭头上标记的输入符号,那么它将沿着该箭头移动到箭头的目标状态。例如,从 $q_2$ 到 $q_3$ 的箭头上标着0,意味着在状态 $q_2$ 时读到输入 0,会转移到状态 $q_3$。
💡 [数值示例]
- 示例1:解读图1.4的一个转移
- 找到从状态 $q_1$ 出发,标有1的箭头。
- 这个箭头指向状态 $q_2$。
- 解读:当自动机 $M_1$ 处于起始状态 $q_1$ 时,如果它读取的第一个输入符号是1,它的状态就会变成 $q_2$。
- 示例2:解读图1.4的一个自环
- 找到从状态 $q_2$ 出发,又指回 $q_2$ 自己的箭头。
- 这个箭头上标有1。
- 解读:当自动机 $M_1$ 处于接受状态 $q_2$ 时,如果它再读取一个输入符号1,它的状态将保持不变,仍然是 $q_2$。
⚠️ [易错点]
- 忘记起始状态:任何自动机的计算过程都必须从起始状态开始。如果随便从一个状态开始,得到的结果就是错误的。
- 忽略接受状态:接受状态是判断最终结果的唯一标准。即使计算过程中经过了接受状态,但如果结束时不在接受状态,该输入串仍然不被接受。
- 混淆0和1:对于同一个起始状态,输入0和输入1可能会导致完全不同的转移。必须严格按照箭头上的标签来确定路径。
📝 [总结]
本段介绍了阅读有限自动机状态图的基本方法,明确了状态(单圈)、起始状态(无源箭头)、接受状态(双圈)和转移(带标签的箭头)这四个核心元素的图形表示法和含义。
🎯 [存在目的]
本段的目的是为读者提供一套“识图”的工具。在引入形式化定义之前,先通过图形化语言,让读者能够准确地解读状态图这种信息丰富的可视化表示,为后续理解自动机的计算过程打下基础。
🧠 [直觉心智模型]
- 地铁线路图:
- 状态 → 地铁站(中关村站、西直门站...)
- 起始状态 → 你家的位置所在的站。
- 接受状态 → 你的目的地站(比如公司所在的国贸站)。
- 输入 → 你要乘坐的线路(4号线、10号线...)。
- 转移 → 乘坐某条线路从一个站到下一个站。
- 状态图就是整张地铁图。你要从你家出发,根据线路选择(输入),一站一站地坐下去(转移),最后看停下来的时候是不是在国贸站(接受状态)。
💭 [直观想象]
想象你在玩一个桌面游戏,棋盘就是图1.4。你有-一个小棋子。
- 游戏开始时,规则说:“必须将棋子放在标有‘START’箭头的 $q_1$ 格子上”(起始状态)。
- 棋盘上有几个特殊的格子画了两个圈,比如 $q_2$。这些是“宝藏格”(接受状态)。
- 现在你抽一张卡片,上面写着一串数字,比如 "1101"。
- 你读第一个数字1。棋盘的格子上画着路线:从 $q_1$ 出发,沿着标1的箭头走,你把棋子移动到了 $q_2$。
- 你读第二个数字1。从 $q_2$ 出发,沿着标1的箭头走,棋子回到了 $q_2$。
- ...以此类推,直到你读完所有数字。
- 最后,你看你的棋子停在哪个格子上。如果停在“宝藏格” $q_2$ 上,你就赢了(接受)。如果停在其他格子上(比如 $q_1$ 或 $q_3$),你就输了(拒绝)。
1.1.2.1. 有限自动机 $M_1$ 的计算过程
📜 [原文11]
当这个自动机接收到诸如 1101 的输入串时,它会处理该串并产生输出。输出要么是接受,要么是拒绝。为简单起见,我们现在只考虑这种是/否类型的输出。处理从 $M_{1}$ 的起始状态开始。自动机逐个从左到右读取输入串中的符号。读取每个符号后,$M_{1}$ 沿以该符号为标签的转移从一个状态转移到另一个状态。当它读取最后一个符号时,$M_{1}$ 产生其输出。如果 $M_{1}$ 现在处于接受状态,则输出为接受;如果不是,则为拒绝。
📖 [逐步解释]
这段话详细描述了有限自动机的“计算”或“处理”一个输入串的完整流程和规则。
- 输入与输出:
- 输入:一个由符号组成的串(string),例如 1101。
- 输出:一个简单的二元判断结果——接受 (accept) 或 拒绝 (reject)。这是一个“是/否”类型的回答。有限自动机的核心功能就是对给定的输入串做出这样的分类。
- 计算流程:这是一个严格的、按部就班的过程。
- 第一步:初始化。计算总是从起始状态开始。对于 $M_1$,就是从 $q_1$ 开始。
- 第二步:顺序读取。自动机像一个读头一样,从左到右,一个接一个地读取输入串中的符号。不能跳过,也不能后退。
- 第三步:状态转移。每读取一个符号,自动机就根据其当前所在的状态和读取到的符号,查找状态图中对应的转移箭头,并移动到箭头指向的下一个状态。这个过程不断重复。
- 第四步:产生最终输出。当输入串的所有符号都被读取完毕后,自动机会停留在某个状态上。此时,进行最终判决:
- 如果自动机所在的最终状态是接受状态(双圈),那么整个输入串被接受。
- 如果最终状态不是接受状态(只是单圈),那么整个输入串被拒绝。
💡 [数值示例]
- 初始状态: $q_1$。
- 读第一个符号 1: 从 $q_1$ 沿标1的箭头,转移到 $q_2$。当前状态: $q_2$。
- 读第二个符号 0: 从 $q_2$ 沿标0的箭头,转移到 $q_3$。当前状态: $q_3$。
- 输入结束: 最终状态是 $q_3$。
- 判决: $q_3$ 不是接受状态(不是双圈)。
- 输出: 拒绝字符串 10。
- 初始状态: $q_1$。
- 读第一个符号 0: 从 $q_1$ 沿标0的箭头,转移到 $q_1$。当前状态: $q_1$。
- 读第二个符号 1: 从 $q_1$ 沿标1的箭头,转移到 $q_2$。当前状态: $q_2$。
- 输入结束: 最终状态是 $q_2$。
- 判决: $q_2$ 是接受状态(是双圈)。
- 输出: 接受字符串 01。
⚠️ [易错点]
- 处理空串 $\varepsilon$:如果输入串是空串(没有任何符号),自动机如何处理?它不读取任何符号,所以它根本不会离开起始状态。因此,判决结果完全取决于起始状态本身。
- 如果起始状态是接受状态,则空串被接受。
- 如果起始状态不是接受状态,则空串被拒绝。
- 对于 $M_1$ 来说,起始状态 $q_1$ 不是接受状态,所以它拒绝空串 $\varepsilon$。
- 过程与结果:输入串被接受还是拒绝,只取决于它跑完后最后停在哪里,跟它中途是否经过接受状态无关。例如,对于输入 10,它中途经过了接受状态 $q_2$,但因为它最后停在了 $q_3$,所以仍然被拒绝。
📝 [总结]
本段将有限自动机的运行机制定义为一个确定性的算法:从起始状态出发,根据输入串的符号序列,一步步地进行状态转移,最终根据自动机停止时的状态是否为接受状态,给出“接受”或“拒绝”的判决。
🎯 [存在目的]
本段的目的是清晰地、无歧义地定义有限自动机的“计算”是什么。这个定义是后续所有理论的基础。只有明确了自动机如何工作,我们才能讨论它能接受哪些串,它能识别什么语言,以及它的能力边界在哪里。这是从静态描述(它是什么)到动态描述(它如何工作)的过渡。
🧠 [直觉心智模型]
- 自动售货机:
- 状态:你投入的金额(0元, 0.5元, 1元, 1.5元...)。起始状态是0元。接受状态是所有大于等于商品价格的金额。
- 输入:你投入的硬币(0.5元硬币,1元硬币)。
- 计算过程:
- 初始状态:0元。
- 你投入一个1元硬币(输入),状态从0元转移到1元。
- 你再投入一个0.5元硬币(输入),状态从1元转移到1.5元。
- 此时,如果一瓶水卖1.5元,那么1.5元就是一个接受状态。你选择商品,它就被“接受”了,然后掉出来。如果水卖2元,1.5元就不是接受状态,你需要继续投币。
- 接受/拒绝:你投入的硬币序列(比如“1元, 0.5元”)是否被接受,取决于最终金额是否达到商品价格。
💭 [直观想象]
想象一条单行道的公路,路边有一些城镇(状态)。你从“起点镇” ($q_1$) 出发。你手里有一张指令卡,写着 1101。
- 第一个指令是 1:你查找地图,发现从“起点镇”出发,沿着标1的路,会开到“幸运镇”($q_2$)。你开车过去。
- 第二个指令是 1:你查找地图,发现从“幸运镇”出发,沿着标1的路,会绕一圈回到“幸运镇”本身。你开车绕了一圈。
- 第三个指令是 0:你从“幸运镇”出发,沿标0的路,开到了“荒芜镇”($q_3$)。
- 第四个指令是 1:你从“荒芜镇”出发,沿标1的路,又开回了“幸运镇”($q_2$)。
指令卡读完了。你最后停在了“幸运镇”($q_2$)。游戏规则说,“幸运镇”是一个“目的地”(接受状态)。所以,你完成了这次旅程,你“赢了”。
1.1.2.2. 有限自动机 $M_1$ 计算示例:输入 1101
📜 [原文12]
例如,当我们将输入串 1101 输入到图 1.4 中的机器 $M_{1}$ 时,处理过程如下:
- 从状态 $q_{1}$ 开始。
- 读取 1,沿转移从 $q_{1}$ 到 $q_{2}$。
- 读取 1,沿转移从 $q_{2}$ 到 $q_{2}$。
- 读取 0,沿转移从 $q_{2}$ 到 $q_{3}$。
- 读取 1,沿转移从 $q_{3}$ 到 $q_{2}$。
- 接受,因为 $M_{1}$ 在输入结束时处于接受状态 $q_{2}$。
📖 [逐步解释]
这段文字是上一段描述的计算流程的一个完整、具体的演练。它将输入 "1101" 应用于自动机 $M_1$,并一步步展示状态的变化。
我们来更详细地分解这个过程,将每一步与一个“时间点”或“处理阶段”对应起来:
- 阶段 0 (处理前):
- 自动机状态: $q_1$ (根据规则,总是从起始状态开始)。
- 待处理输入: 1101
- 阶段 1 (处理第1个符号 '1'):
- 当前状态: $q_1$。
- 读取符号: 1。
- 执行转移: 在状态图上,从 $q_1$ 出发,沿着标有 1 的箭头,到达 $q_2$。
- 新状态: $q_2$。
- 待处理输入: 101
- 阶段 2 (处理第2个符号 '1'):
- 当前状态: $q_2$。
- 读取符号: 1。
- 执行转移: 在状态图上,从 $q_2$ 出发,沿着标有 1 的箭头,这是一个“自环”,所以终点还是 $q_2$。
- 新状态: $q_2$。
- 待处理输入: 01
- 阶段 3 (处理第3个符号 '0'):
- 当前状态: $q_2$。
- 读取符号: 0。
- 执行转移: 在状态图上,从 $q_2$ 出发,沿着标有 0 的箭头,到达 $q_3$。
- 新状态: $q_3$。
- 待处理输入: 1
- 阶段 4 (处理第4个符号 '1'):
- 当前状态: $q_3$。
- 读取符号: 1。
- 执行转移: 在状态图上,从 $q_3$ 出发,沿着标有 1 的箭头,到达 $q_2$。
- 新状态: $q_2$。
- 待处理输入: (空)
- 阶段 5 (处理结束):
- 所有输入符号都已处理完毕。
- 最终状态: $q_2$。
- 进行判决: 检查 $q_2$ 是否为接受状态。在状态图上,$q_2$ 是双圈,所以它是接受状态。
- 最终输出: 接受。
这个过程完全对应原文中的6个步骤。
💡 [数值示例]
- 示例1(原文示例): 输入 1101,最终状态为 $q_2$,被接受。
- 示例2:输入 1010
- 开始: 状态 $q_1$。
- 读 1: $q_1 \rightarrow q_2$。
- 读 0: $q_2 \rightarrow q_3$。
- 读 1: $q_3 \rightarrow q_2$。
- 读 0: $q_2 \rightarrow q_3$。
- 结束: 最终状态是 $q_3$。因为 $q_3$ 不是接受状态,所以字符串 1010 被拒绝。
⚠️ [易错点]
- 状态与符号的精确匹配:在模拟过程中,每一步都必须严格遵守“当前状态”+“当前输入符号”来决定下一步。例如,在状态 $q_3$ 时,输入 0 会去哪里?从图上看,没有从 $q_3$ 出发,标号为 0 的箭头。这是一个图的画法问题,在形式化定义中,每个状态对每个输入符号都必须有且仅有一个转移。我们后面会学到,如果图中没有画出,可能意味着转移到一个“陷阱状态”(一个永远无法离开且非接受的状态),或者在形式化定义中会有明确说明。对于 $M_1$,我们可以从后续的表格定义中看到 $\delta(q_3, 0) = q_2$。所以上一个例子的第5步应该是 $q_2 \rightarrow q_3 \rightarrow q_2$。让我们用这个信息重新跑示例2:
- 示例2 (修正后):输入 1010
- 开始: 状态 $q_1$。
- 读 1: $q_1 \rightarrow q_2$。
- 读 0: $q_2 \rightarrow q_3$。
- 读 1: $q_3 \rightarrow q_2$。
- 读 0: $q_2 \rightarrow q_3$。
- 结束: 最终状态是 $q_3$。1010 被拒绝。(等等,我应该先看形式化定义再做判断,图1.6的表格说明了$\delta(q_3,0)=q_2$和$\delta(q_3,1)=q_2$。图1.4的画法有歧义或错误。我们以更明确的图1.6为准)。
以图1.6的定义重新运行示例2:
- 开始: 状态 $q_1$。
- 读 1: $q_1 \rightarrow q_2$。
- 读 0: $q_2 \rightarrow q_3$。
- 读 1: $q_3 \rightarrow q_2$。
- 读 0: $q_2 \rightarrow q_3$。
(等等,图1.6的表格和图1.4是一致的,$\delta(q_3,0)$应该是$q_2$, $\delta(q_3,1)$也应该是$q_2$。哦,我看错了图1.4,$q_3$到$q_2$的箭头上标的是0, 1。所以之前的分析是错的。)
以正确的图1.4解读再次运行示例2:
- 开始: 状态 $q_1$。
- 读 1: $q_1 \rightarrow q_2$。
- 读 0: $q_2 \rightarrow q_3$。
- 读 1: 从 $q_3$ 读 1,沿着标有0, 1的箭头,转移到 $q_2$。状态 $q_2$。
- 读 0: 从 $q_2$ 读 0,转移到 $q_3$。状态 $q_3$。
- 结束: 最终状态是 $q_3$。 1010被拒绝。
这个过程说明了仔细读图的重要性。一个逗号可能就代表了多条转移。
📝 [总结]
本段通过一个实际的输入串 1101,一步步地、清晰地演示了有限自动机 $M_1$ 的完整计算过程,并根据最终停留的状态得出了“接受”的结论。
🎯 [存在目的]
本段的目的是提供一个“动手练习”。通过这个具体的trace,读者可以亲自验证自己对自动机计算流程的理解是否正确。它将前文抽象的规则描述,转化为一个可观察、可复现的实例,起到了巩固和检验学习成果的作用。
🧠 [直觉心智模型]
- 寻宝游戏指令:你拿到一张藏宝图(状态图)和一个指令序列(输入串1101)。
- 指令1:“向东走”(输入1)。你从起点($q_1$)走到了岔路口A($q_2$)。
- 指令2:“向东走”(输入1)。你在岔路口A打了个转,还在原地($q_2$)。
- 指令3:“向北走”(输入0)。你从岔路口A走到了陷阱B($q_3$)。
- 指令4:“向东走”(输入1)。你从陷阱B找到一条密道,回到了岔路口A($q_2$)。
- 指令结束。你最后的位置在岔路口A($q_2$),而藏宝图上标记着“岔路口A有宝藏”(接受状态)。所以你寻宝成功。
💭 [直观想象]
想象一个弹珠游戏机。弹珠从最顶端的入口($q_1$)落下。机器内部有一系列的开关和通道。
- 你投入第一个硬币“1”,弹珠滚到了一个中间平台($q_2$)。
- 你投入第二个硬币“1”,平台上的一个开关被触发,但弹珠只是在平台上晃了一下,还在原地($q_2$)。
- 你投入第三个硬币“0”,另一个开关被触发,平台倾斜,弹珠掉到了下一层平台($q_3$)。
- 你投入第四个硬币“1”,下一层平台的一个机关被触发,把弹珠弹回了上面的中间平台($q_2$)。
- 游戏结束。你看到弹珠最后停在了中间平台($q_2$),这个平台的出口连着“中奖”灯。于是,“中奖”灯亮起(接受)。
1.1.2.3. 归纳 $M_1$ 接受的语言
📜 [原文13]
对这台机器进行各种输入串的实验表明,它接受串 $1,01,11$ 和 $0101010101$。事实上,$M_{1}$ 接受任何以 1 结尾的串,因为它在读取符号 1 时都会进入其接受状态 $q_{2}$。此外,它接受串 $100,0100,110000$ 和 $0101000000$,以及任何以偶数个 0 跟随最后一个 1 结尾的串。它拒绝其他串,例如 $0,10,101000$。您能描述由 $M_{1}$ 接受的所有串组成的语言吗?我们很快就会这样做。
📖 [逐步解释]
这段话从具体例子上升到归纳总结,尝试去理解自动机 $M_1$ 到底接受一类什么样的串,即它所识别的语言是什么。
- 实验与观察:作者首先列出了一些实验结果:
- 接受的串:1, 01, 11, 0101010101。这些串的共同点是什么?它们都以 1 结尾。
- 这引出了一个初步假设:$M_1$ 是不是接受所有以 1 结尾的串?
- 修正初步假设:作者很快指出了这个假设是不完整的。他提到了一个看似矛盾的地方:“因为它在读取符号 1 时都会进入其接受状态 $q_2$”。这句话其实不完全准确。比如在 $q_2$ 读 0 会到 $q_3$。更准确的说法是,从 $q_1$ 或 $q_3$ 读 1 会到 $q_2$,在 $q_2$ 读 1 会停在 $q_2$。
- 然后作者给出了更多接受的串:100, 0100, 110000, 0101000000。
- 这些串的共同特征是:它们都包含 1,并且在最后一个 1 之后,跟着偶数个 0。(100 -> 最后一个1后有2个0;0100 -> 最后一个1后有2个0;110000 -> 最后一个1后有4个0)。
- 这推翻了“以1结尾”的简单假设,引出了一个更精确的模式。
- 分析状态的含义:要理解这个模式,我们需要搞清楚每个状态代表了什么“记忆”。
- $q_1$:初始状态。可以理解为“到目前为止,还没有读到过1,或者上一个1后面跟了奇数个0”。
- $q_2$:接受状态。可以理解为“刚刚读到了一个1,或者上一个1后面跟了偶数个0”。
- $q_3$:中间状态。可以理解为“上一个1后面跟了奇数个0”。
- 用状态含义来验证逻辑:
- 在$q_1$(没见过1或见过奇数个0在1后),读到0,还在$q_1$(状态不变)。读到1,进入$q_2$(刚见过1,后面0的个数是0,是偶数)。
- 在$q_2$(1后有偶数个0),读到1,还在$q_2$(刷新了最后一个1的位置,后面0的个数还是0,偶数)。读到0,进入$q_3$(1后有奇数个0了)。
- 在$q_3$(1后有奇数个0),读到0或1。这里图1.4的箭头标的是 0, 1 指向 $q_2$。
- 读到0:$q_3 \rightarrow q_2$。这意味着(1后有奇数个0)再读一个0就变成了(1后有偶数个0)。这符合逻辑。
- 读到1:$q_3 \rightarrow q_2$。这意味着(1后有奇数个0)再读一个1,就变成了(刚见过1,后面0的个数是0,偶数)。这也符合逻辑。
- 总结语言的特征:
- 被拒绝的串:0 (没有1), 10 (最后一个1后有1个0,奇数), 101000 (最后一个1后有3个0,奇数)。
- 综上所述,$M_1$ 接受的语言是:所有包含了至少一个1,并且在最后一个1后面跟随了偶数个0的字符串。
- 提出问题,引出下文:作者最后以一个设问“您能描述由 $M_1$ 接受的所有串组成的语言吗?”来总结本段的探索,并用“我们很快就会这样做”来预告后面将给出这个问题的形式化答案。
💡 [数值示例]
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_3$
- $q_3 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_3$
- $q_3 \xrightarrow{0} q_2$
- 最终状态 $q_2$,是接受状态。所以 10100 被接受。
- 验证规律:串中最后一个1是第3个字符,其后跟了2个0(偶数个)。符合规律。
- $q_1 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_3$
- $q_3 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_3$
- 最终状态 $q_3$,不是接受状态。所以 001010 被拒绝。
- 验证规律:串中最后一个1是第5个字符,其后跟了1个0(奇数个)。不符合规律。
⚠️ [易错点]
- 边界情况1:没有1的串
- 输入串 000。过程:$q_1 \xrightarrow{0} q_1 \xrightarrow{0} q_1 \xrightarrow{0} q_1$。最终在 $q_1$,拒绝。符合“必须包含至少一个1”的规律。
- 边界情况2:以1结尾的串
- 输入串 011。过程:$q_1 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_2$。最终在 $q_2$,接受。
- 规律验证:最后一个1后面有0个0。数字0是一个偶数,所以符合“跟随偶数个0”的规律。这一点是初学者容易忽略的。
📝 [总结]
本段通过对自动机 $M_1$ 进行实验性的输入和观察,引导读者通过归纳推理,逐步揭示出其所识别的语言的精确规律:包含至少一个1,且最后一个1后必须跟偶数个0。
🎯 [存在目的]
本段的目的是培养一种重要的能力:从一个给定的自动机(白盒)反向推导出它所定义的语言(功能)。这与后面“设计一个自动机来识别给定语言”(黑盒)的过程正好相反,两者都是计算理论中的核心技能。它展示了如何通过“实验-假设-验证/修正”的科学方法来理解一个未知的计算模型。
🧠 [直觉心智模型]
- 猜灯谜:给你一个灯谜的谜面(自动机 $M_1$ 的结构),你不能直接看谜底(语言的描述)。你只能一次次地猜词语(提供输入串),出谜的人会告诉你“中了”(接受)或“没中”(拒绝)。通过多次尝试和反馈,你逐渐摸索出谜底的规律(比如“谜底是一种水果”),最终猜出谜底(精确描述出语言)。
💭 [直观想象]
想象 $M_1$ 是一个密码锁,它有三个指示灯:$q_1$(红色)、$q_2$(绿色)、$q_3$(黄色)。你有一串按钮 0 和 1。
- 初始时,红灯 $q_1$ 亮。
- 你按下的按钮序列就是输入串。每按一下,灯的状态就根据规则变化。
- 你的目标是,当你按完所有按钮后,最终绿灯 $q_2$ 亮起。
- 通过反复试验,你发现,要想最后绿灯亮,你输入的序列必须满足“最后按的那个1之后,你按了偶数次0”这个奇怪的规律。这个规律就是这个密码锁的“通关密码”的集合,也就是它识别的语言。
11.2. 有限自动机的形式化定义
📜 [原文14]
在上一节中,我们使用状态图介绍了有限自动机。现在我们形式化地定义有限自动机。虽然状态图在直观上更容易理解,但我们也需要形式化定义,原因有两个。
首先,形式化定义是精确的。它解决了关于有限自动机中允许什么操作的任何不确定性。如果您不确定有限自动机是否允许有 0 个接受状态,或者它们是否必须为每个可能的输入符号从每个状态恰好引出一条转移,您可以查阅形式化定义并验证答案在这两种情况下都是肯定的。其次,形式化定义提供了符号。良好的符号有助于您清晰地思考和表达您的想法。
形式化定义的语言有些深奥,与法律文件的语言有些相似。两者都需要精确,并且每个细节都必须详细说明。
📖 [逐步解释]
这段话是引入形式化定义之前的“序言”,旨在向读者解释“为什么我们需要一个看起来更复杂、更不直观的东西?”。
- 回顾与展望:首先回顾了我们已经学习过的方法——状态图,并承认它的优点(直观、易于理解)。然后宣告下一步的任务:给出形式化定义(Formal Definition)。
- 阐述形式化定义的两大必要性:
- 原因一:精确性 (Precision)。
- 状态图这种图形化语言有时可能存在歧义或者省略。例如,像我们之前讨论的,图1.4中从 $q_3$ 出发的箭头只标了 0, 1,如果字母表还有其他符号怎么办?如果一个状态对于某个输入没有画出转移箭头,这意味着什么?
- 形式化定义就像一部“法律”,它用严格的数学语言规定了有限自动机的每一个组成部分和每一条规则,杜绝了任何“可能这样、也可能那样”的模糊空间。
- 作者举了两个例子来证明其精确性:
- 问题A: 是否允许有0个接受状态?形式化定义会明确回答这个问题。
- 问题B: 每个状态是否都必须对每个输入符号有且仅有一条出路(转移)?形式化定义同样会给出确切答案。
- 原因二:符号化 (Notation)。
- 数学的力量很大程度上来源于其强大的符号系统。良好的符号能将复杂的思想浓缩成简洁、易于操作的形式。
- 有了形式化的符号,我们就可以更容易地进行证明、构建算法、比较不同的自动机,就像代数符号让我们能方便地解方程一样。用图形去进行严格的逻辑推导是非常困难的。
- 类比法律文件:
- 作者将形式化定义的语言比作法律文件。这个类比非常贴切。
- 共同点:两者都追求极致的“精确”,力求没有漏洞和歧义。它们可能看起来冗长、晦涩(“深奥”),充满了专门术语和严格的结构,但这都是为了确保在任何情况下,其含义都是唯一和确定的。每一个词、每一个符号都经过了仔细的推敲。
💡 [数值示例]
- 示例1:精确性的体现
- 不精确的口头描述:“一个能识别偶数的机器”。这很模糊。是二进制表示的偶数?十进制?是以偶数结尾?还是所有数字加起来是偶数?
- 状态图:比口头描述好,但可能画得不标准,比如漏掉某个转移。
- 形式化定义:会精确地定义字母表(例如 $\Sigma=\{0, 1, ..., 9\}$),状态(例如 $q_{even}, q_{odd}$),转移函数(例如 $\delta(q_{even}, '3') = q_{odd}$),从而毫无歧义地定义出这个机器到底是什么。
- 示例2:符号化的力量
- 无符号:“把第一个自动机的接受状态和第二个自动机的所有状态组合起来,再把第一个自动机的所有状态和第二个自动机的接受状态组合起来,把这两大组组合并起来,作为新自动机的接受状态。” 这段话非常绕口。
- 有符号:$F = (F_1 \times Q_2) \cup (Q_1 \times F_2)$。 这行符号清晰、简洁地表达了同样的意思,并且便于进行集合运算的推导。
⚠️ [易错点]
- 误解:认为形式化定义是为了把简单问题复杂化。
- 纠正:形式化定义的目的是为了“澄清”而不是“复杂化”。在简单问题上,它的优势不明显,但当问题变得复杂、需要严格证明时,没有形式化定义将寸步难行。它是构建宏伟理论大厦的坚实地基。
📝 [总结]
本段作为引入形式化定义的开场白,论证了从直观的状态图转向严格的数学定义的必要性。形式化定义通过提供无与伦比的“精确性”和便于思考的“符号”,为计算理论的深入研究奠定了基础,其严谨性可与法律文件相媲美。
🎯 [存在目的]
本段的目的是说服读者接受并重视即将到来的抽象内容。它通过解释“为什么”,帮助读者建立正确的学习心态,理解形式化不是目的,而是保证理论体系可靠、严谨的必要手段。这有助于减少读者在面对抽象数学符号时的抵触情绪。
🧠 [直觉心智模型]
- 菜谱 vs 化学式:
- 状态图就像一个家常菜谱,上面写着“少许盐”、“翻炒片刻”。这很直观,容易上手,但不同的人做出来味道可能不一样,而且很难分析为什么好吃或不好吃。
- 形式化定义就像一个化学实验的流程单,上面写着“加入 58.44g NaCl”、“在100kPa下加热至 801°C”。这非常精确,保证了实验的可重复性,并且可以基于化学原理进行分析和预测。虽然对新手不友好,但对科学家来说是必不可少的。
💭 [直观想象]
想象一下,你要和别人签订一份合同。
- 非正式的口头约定:“你帮我干活,我给你报酬”。这很简单,但充满了潜在的纠纷。干什么活?报酬多少?什么时候给?
- 一份草图(状态图):你们画了一个简单的流程图,标明了“开始干活 -> 完成 -> 付钱”。这比口头约定好,但细节仍然缺失。
- 一份正式合同(形式化定义):合同中会用法律术语精确定义“甲方”、“乙方”、“工作范围”、“交付标准”、“支付金额”、“支付方式”、“违约责任”等。这份文件虽然读起来枯燥,但它确保了双方的权利和义务都被无歧义地确定下来。有限自动机的形式化定义就是这样一份“数学合同”。
1.1.2.4. 五元组定义
📜 [原文15]
一个有限自动机有几个部分。它有一组状态,以及根据输入符号从一个状态转移到另一个状态的规则。它有一个输入字母表,指示允许的输入符号。它有一个起始状态和一组接受状态。形式化定义指出,一个有限自动机是由这五个对象组成的列表:状态集、输入字母表、转移规则、起始状态和接受状态。在数学语言中,包含五个元素的列表通常称为五元组。因此,我们将有限自动机定义为由这五个部分组成的五元组。
我们使用一种称为转移函数(通常表示为 $\delta$)来定义转移规则。如果有限自动机有一个从状态 $x$ 到状态 $y$ 的箭头,并用输入符号 1 标记,这意味着如果自动机在状态 $x$ 时读取 1,它就会转移到状态 $y$。我们可以用转移函数表示同样的事情,即 $\delta(x, 1)=y$。这种表示法是一种数学速记。综合起来,我们就得到了有限自动机的形式化定义。
📖 [逐步解释]
这段话在正式给出定义之前,先用自然语言把形式化定义的五个核心组件介绍了一遍,并解释了如何将状态图中的“转移箭头”翻译成数学中的“转移函数”。
- 列举五个核心组件:作者把一个有限自动机拆解成了五个基本组成部分,这五个部分缺一不可。
- 一组状态 (Set of States):自动机所有可能的“记忆”或“位置”的集合。
- 输入字母表 (Input Alphabet):一个集合,规定了哪些符号是合法的输入。
- 转移规则 (Transition Rules):定义了自动机如何根据当前状态和输入符号来改变状态。
- 一个起始状态 (A Start State):规定了计算从哪里开始。
- 一组接受状态 (A Set of Accept States):规定了哪些状态是“成功”的终点。
- 引入“五元组”概念:
- 在数学中,一个有序的元素列表被称为“元组”(Tuple)。包含两个元素的叫二元组(如坐标 (x, y)),三个的叫三元组,五个的就叫五元组(5-tuple)。
- 形式化定义的核心就是:一个有限自动机“是”一个五元组,这个五元组里不多不少,正好包含了上述五个核心组件。这是一种非常数学化的定义方式,用一个结构化的对象来代表一个概念。
- 形式化“转移规则”:
- 在五个组件中,“转移规则”是最复杂的,需要一种精确的数学工具来描述。这个工具就是转移函数 (Transition Function)。
- 转移函数通常用希腊字母 $\delta$ (delta) 来表示。
- 函数思想的引入:作者解释了如何将状态图中的箭头翻译成函数表示。
- 状态图语言:一个从状态 $x$ 到状态 $y$ 的箭头,上面标着 1。
- 函数语言:$\delta(x, 1) = y$。
- 解读函数表示:这个数学式子读作:“转移函数 $\delta$ 在输入为(当前状态 $x$,输入符号 1)时,其输出为(下一个状态 $y$)”。它完美地捕捉了状态转移的三个要素:从哪来、因为啥、到哪去。
- 数学速记:称这种表示法为“数学速记”,因为它用简洁的符号替代了冗长的文字或图形描述。
- 承前启后:最后,作者总结说,把这五个部分用数学符号整合在一起,就得到了完整的形式化定义,为下一段的定义1.5做好了最后的铺垫。
💡 [数值示例]
- 示例1: 翻译 $M_1$ 的一条转移
- 状态图中的箭头: 从 $q_2$ 到 $q_3$ 的箭头,标有 0。
- 用转移函数表示: $\delta(q_2, 0) = q_3$。
- 示例2: 翻译 $M_1$ 的另一条转移
- 状态图中的箭头: 从 $q_1$ 到 $q_1$ 的自环箭头,标有 0。
- 用转移函数表示: $\delta(q_1, 0) = q_1$。
⚠️ [易错点]
- 函数与关系的混淆:在确定性有限自动机(本书目前讨论的类型)中,$\delta$ 是一个函数。这意味着对于任何给定的(状态,符号)输入对,输出(下一个状态)必须是唯一确定的。它不能是“可能到 $y$ 也可能到 $z$”。后面会学到的非确定性有限自动机会放宽这个限制,那时候的“转移关系”就不是一个严格意义上的函数了。
- 元组的有序性:五元组是有序的。第一个元素必须是状态集,第二个必须是字母表,等等。顺序不能搞错。
📝 [总结]
本段通过自然语言拆解了有限自动机的五个核心构成要素,并引入了“五元-组”这一数学概念来封装它们。最关键的是,它解释了如何用一个数学上的“转移函数” $\delta$ 来精确地、无歧义地表示状态图中的转移箭头,为最终的形式化定义扫清了最后的术语障碍。
🎯 [存在目的]
本段的目的是在给出最终的、高度浓缩的形式化定义之前,进行一次“软着陆”。它像一个预览,提前解释了定义中每个符号和组件的含义,特别是将最关键的转移函数 $\delta$ 的概念讲清楚。这样,当读者看到定义1.5时,就不会觉得那是一堆天书般的符号,而是已经理解了其背后含义的数学表达。
[直觉心-智模型]
- 定义一个“人”:如果你要给外星人形式化地定义什么是“人”,你可能会说:一个“人”是一个五元组 (头部, 躯干, 四肢, 起始状态, 功能)。
- 头部: 包含大脑、眼睛等。
- 躯干: 包含心脏、肺等。
- 四肢: 手臂和腿的集合。
- 起始状态: “婴儿”。
- 功能: 一个复杂的函数集合,比如 消化(食物) = 能量,行走(地面) = 位置改变。
用这种方式定义,虽然看起来很奇怪,但非常严谨,外星人可以根据这个定义来“构建”或“识别”一个“人”。有限自动机的五元组定义也是出于同样的严谨性考虑。
💭 [直观想象]
想象你在填写一张表格来注册一个新游戏的角色。这张表格就是五元组。
- 可选职业 (状态集): [战士, 法师, 弓箭手]
- 可用技能 (字母表): [攻击, 防御, 施法]
- 行为规则 (转移函数 $\delta$): 你需要填写一个巨大的表格,说明“如果我是战士,并且我选择‘施法’,会发生什么?” (可能会提示“无效操作,状态不变”)。即 $\delta(\text{战士}, \text{施法}) = \text{战士}$。
- 初始职业 (起始状态): 战士
- 胜利条件 (接受状态集): [击败最终Boss] (这是一个特殊状态)
填完这张完整的表格,你就形式化地定义了你的游戏角色。这个角色就是一个有限自动机。
1.1.2.5. 定义 1.5:有限自动机
📜 [原文16]
定义 1.5
有限自动机是一个五元组 $\left(Q, \Sigma, \delta, q_{0}, F\right)$,其中
- $Q$ 是一个有限集合,称为状态,
- $\Sigma$ 是一个有限集合,称为字母表,
- $\delta: Q \times \Sigma \longrightarrow Q$ 是转移函数, ${ }^{1}$
- $q_{0} \in Q$ 是起始状态,
- $F \subseteq Q$ 是接受状态集。 ${ }^{2}$
[^0]形式化定义精确地描述了我们所说的有限自动机的含义。例如,回到之前关于是否允许 0 个接受状态的问题,您可以看到将 $F$ 设置为空集 $\emptyset$ 会产生 0 个接受状态,这是允许的。此外,转移函数 $\delta$ 为状态和输入符号的每种可能组合精确地指定了一个下一个状态。这肯定地回答了我们的另一个问题,表明对于每个可能的输入符号,恰好有一个转移箭头从每个状态引出。
📖 [逐步解释]
这是本章第一个核心的形式化定义,用纯数学语言定义了什么是有限自动机。让我们逐项拆解这个五元组的含义。
一个有限自动机是一个五元组 $(Q, \Sigma, \delta, q_0, F)$
这句话是定义的核心。它声明了一个有限自动机在数学上就是一个包含五个元素的有序列表(元组)。这五个元素分别是 $Q, \Sigma, \delta, q_0, F$。
- $Q$ 是一个有限集合,称为状态 (States)
- $Q$ 代表 States 的首字母。
- 它是一个集合 (Set),意味着里面的元素没有重复。例如,$\{q_1, q_2, q_3\}$。
- 它是有限 (Finite) 的,这是“有限自动机”这个名字的由来。状态的数量不能是无限的。这直接对应了“内存有限”的概念。
- $\Sigma$ 是一个有限集合,称为字母表 (Alphabet)
- $\Sigma$ (大写的 Sigma) 是数学中常用的表示字母表的符号。
- 它也是一个有限集合,包含了所有该自动机能识别的输入符号。例如,$\{0, 1\}$ 或 $\{a, b, c\}$。任何不属于 $\Sigma$ 的符号都是非法输入。
- $\delta: Q \times \Sigma \longrightarrow Q$ 是转移函数 (Transition Function)
- $\delta$ (小写的 delta) 代表转移函数。
- 这部分是定义中最数学化的部分。它描述了 $\delta$ 是一个什么样的函数。
- 定义域 (Domain): $Q \times \Sigma$。这是 $Q$ 和 $\Sigma$ 的笛卡尔积 (Cartesian Product)。它代表了所有可能的 (当前状态, 输入符号) 的组合对。例如,如果 $Q=\{q_1, q_2\}$ 且 $\Sigma=\{0, 1\}$,那么 $Q \times \Sigma = \{(q_1, 0), (q_1, 1), (q_2, 0), (q_2, 1)\}$。
- 值域 (Codomain): $Q$。这表示函数的输出结果必须是状态集 $Q$ 中的一个元素。
- 箭头 $\longrightarrow$: 表示一个映射关系。
- 完整解读: $\delta$ 是一个函数,它的输入是一个“当前状态”和“一个输入符号”组成的对,它的输出是“下一个状态”。这个定义非常严谨,它隐含了:对于任何一个状态和任何一个字母表中的符号,都必须有唯一一个确定的下一状态与之对应。这就回答了之前提出的问题。
- $q_0 \in Q$ 是起始状态 (Start State)
- $q_0$ 是起始状态的名字。下标 0 暗示了“从零开始”。
- 符号 $\in$ 读作“属于”(is an element of)。
- $q_0 \in Q$ 意味着起始状态必须是状态集 $Q$ 中普通的一员,它不是一个凭空冒出来的状态。
- 注意,起始状态只有一个。
- $F \subseteq Q$ 是接受状态集 (Set of Accept States)
- $F$ 代表 Final 或 Accept。
- 它是一个集合,是状态集 $Q$ 的一个子集 (subset),用符号 $\subseteq$ 表示。
- 这意味着所有接受状态都必须首先是合法的状态。
- 因为 $F$ 是一个集合,它可以包含多个元素(多个接受状态),也可以只包含一个元素,甚至可以是空集 $\emptyset$(零个接受状态)。这也回答了之前提出的问题。
脚注部分的解释:
脚注部分是对这个形式化定义的补充说明,强调了它如何解决之前的模糊之处。
- 关于0个接受状态:$F \subseteq Q$ 允许 $F = \emptyset$ (空集是任何集合的子集),所以0个接受状态是被允许的。这样的自动机将不接受任何输入串。
- 关于转移的唯一性:$\delta: Q \times \Sigma \longrightarrow Q$ 的函数定义,保证了对 $Q \times \Sigma$ 中的每一个元素,都有一个且仅一个 $Q$ 中的元素与之对应。这说明状态图中,从每个状态出发,对于字母表中的每一个符号,都必须画出一条(不多不少)转移箭头。
💡 [数值示例]
- 示例1: 自动门控制器
- $Q = \{\text{CLOSED}, \text{OPEN}\}$
- $\Sigma = \{\text{NEITHER}, \text{FRONT}, \text{REAR}, \text{BOTH}\}$
- $\delta$ 由图1.3的表格定义。例如 $\delta(\text{CLOSED}, \text{FRONT}) = \text{OPEN}$。
- $q_0 = \text{CLOSED}$
- $F = \{\text{OPEN}\}$
- 这五个部分完整地定义了自动门控制器。
- 示例2: 识别奇数个1的自动机 (图1.20)
- $Q = \{q_{\text{even}}, q_{\text{odd}}\}$
- $\Sigma = \{0, 1\}$
- $\delta$:
- $\delta(q_{\text{even}}, 0) = q_{\text{even}}$
- $\delta(q_{\text{even}}, 1) = q_{\text{odd}}$
- $\delta(q_{\text{odd}}, 0) = q_{\text{odd}}$
- $\delta(q_{\text{odd}}, 1) = q_{\text{even}}$
- $q_0 = q_{\text{even}}$
- $F = \{q_{\text{odd}}\}$
⚠️ [易错点]
- $\Sigma$ 和 $Q$ 都是集合:所以 $\{0, 1\}$ 和 $\{1, 0\}$ 是同一个字母表。$\{q_1, q_2\}$ 和 $\{q_2, q_1\}$ 是同一个状态集。
- $q_0$ 和 $F$ 的区别: $q_0$ 是一个元素,而 $F$ 是一个集合。即使只有一个接受状态,比如 $q_2$,我们也写成 $F=\{q_2\}$,而不是 $F=q_2$。
- $\delta$ 的完备性: 这个定义是针对确定性有限自动机 (DFA) 的。它的转移函数 $\delta$ 是一个全函数,即对定义域中的每个输入都必须有定义。
📝 [总结]
定义 1.5 用数学的语言,将有限自动机精确地定义为一个五元组 $(Q, \Sigma, \delta, q_0, F)$。这个定义明确了自动机的五个构成要素(状态集、字母表、转移函数、起始状态、接受状态集)及其数学属性(如有限性、函数性、集合关系),从而消除了所有歧义。
🎯 [存在目的]
本段是全书理论体系的基石之一。这个形式化定义是将有限自动机作为一个数学对象来研究的出发点。没有它,就无法进行严格的证明和推导。所有后续关于正则语言的定理(如闭包性质)都将严格依赖于这个五元组定义来进行构造和证明。
🧠 [直觉心智模型]
- DNA蓝图:五元组就像一个生物体的DNA。它不是生物体本身,而是编码了构建和运行这个生物体所需全部信息的蓝图。
- $Q$:规定了细胞可以分化成哪些类型(神经细胞、肌肉细胞...)。
- $\Sigma$:规定了细胞能响应哪些外界化学信号。
- $\delta$:编码了细胞的发育和响应规则(什么信号会让什么细胞分裂或改变功能)。
- $q_0$:受精卵。
- $F$:成年、具备某种功能(如繁殖能力)的状态。
💭 [直观想象]
想象你正在配置一台全新的服务器。你需要填写一个包含五个字段的配置表:
- HOST_STATES: [RUNNING, STOPPED, REBOOTING] (这就是 $Q$)
- ALLOWED_COMMANDS: [start, stop, reboot] (这就是 $\Sigma$)
- TRANSITION_RULES: (一个复杂的脚本,定义了 on_state(RUNNING) receive_cmd(stop) -> goto_state(STOPPED) 等所有规则,这就是 $\delta$)
- INITIAL_STATE: STOPPED (这就是 $q_0$)
- SUCCESS_STATES: [RUNNING] (这就是 $F$,表示服务器正常运行就是我们想要的目标状态)
当你完整、无误地填写完这张表格,你就形式化地定义了一台服务器的生命周期管理器,它就是一个有限自动机。
1.1.2.6. $M_1$ 的形式化描述
📜 [原文17]
我们可以使用形式化定义的符号来描述单个有限自动机,通过指定定义 1.5中列出的五个部分。例如,让我们回到我们之前讨论的有限自动机 $M_{1}$,为方便起见在此重新绘制。

图 1.6
有限自动机 $M_{1}$
我们可以通过写 $M_{1}=\left(Q, \Sigma, \delta, q_{1}, F\right)$ 来形式化地描述 $M_{1}$,其中
- $Q=\left\{q_{1}, q_{2}, q_{3}\right\}$,
- $\Sigma=\{0,1\}$,
- $\delta$ 描述如下:
|
0 |
1 |
| $q_{1}$ |
$q_{1}$ |
$q_{2}$ |
| $q_{2}$ |
$q_{3}$ |
$q_{2}$ |
| $q_{3}$ |
$q_{2}$ |
$q_{2}$, |
- $q_{1}$ 是起始状态,
- $F=\left\{q_{2}\right\}$。
📖 [逐步解释]
这一段是定义 1.5 的第一次实际应用。它演示了如何将一个以状态图形式给出的自动机 ($M_1$),“翻译”成严格的五元组形式化描述。
这个过程就像是在为一个具体事物(图1.6)填写上一节定义的“五元组”表格。
- $Q$ (状态集):
- 方法: 观察状态图中所有的圆圈。
- 结果: 图中有三个圆圈,分别标记为 $q_1, q_2, q_3$。
- 形式化写作: $Q = \{q_1, q_2, q_3\}$。我们用集合的表示法(花括号 {...})将它们括起来。
- $\Sigma$ (字母表):
- 方法: 观察状态图中所有转移箭头上出现的符号。
- 结果: 箭头上的标签只有 0 和 1。
- 形式化写作: $\Sigma = \{0, 1\}$。
- $\delta$ (转移函数):
- 方法: 这是最繁琐的一步。需要系统地遍历所有“(当前状态,输入符号)”组合,并找出其对应的“下一个状态”。状态转移表是描述 $\delta$ 的最清晰的方式。
- 结果:
- 从 $q_1$ 出发:读0回到 $q_1$;读1去 $q_2$。=> 表格第一行:$q_1, q_2$。
- 从 $q_2$ 出发:读0去 $q_3$;读1回到 $q_2$。=> 表格第二行:$q_3, q_2$。
- 从 $q_3$ 出发:读0去 $q_2$;读1也去 $q_2$。(注意图1.6的箭头从$q_3$到$q_2$上标了0,1,这里表格更清晰地分开列出)。=> 表格第三行:$q_2, q_2$。
- 形式化写作: 用一个完整的表格来定义函数 $\delta$。
- $q_0$ (起始状态):
- 方法: 观察状态图中哪个状态被“无源箭头”所指。
- 结果: 指向 $q_1$ 的箭头没有起点。
- 形式化写作: $q_1$ 是起始状态。(或者更严谨地写 $q_0 = q_1$)
- $F$ (接受状态集):
- 方法: 观察状态图中哪个(或哪些)状态是双圈。
- 结果: 只有 $q_2$ 是双圈。
- 形式化写作: $F = \{q_2\}$。注意,即使只有一个元素,也要写成集合的形式。
通过这五步,我们就将直观的状态图 $M_1$ 完整地、无歧义地转换为了形式化的五元组描述。这两种表示方式(状态图和五元组)信息上是等价的,只是表达形式不同。
💡 [数值示例]
- 示例1(原文示例): 对 $M_1$ 的形式化描述如上。
- 示例2:对自动门控制器的形式化描述
- $Q = \{\text{CLOSED}, \text{OPEN}\}$
- $\Sigma = \{\text{NEITHER}, \text{FRONT}, \text{REAR}, \text{BOTH}\}$
- $\delta$ 定义为:
|
NEITHER |
FRONT |
REAR |
BOTH |
| CLOSED |
CLOSED |
OPEN |
CLOSED |
CLOSED |
| OPEN |
CLOSED |
OPEN |
OPEN |
OPEN |
- $q_0 = \text{CLOSED}$
- $F = \{\text{OPEN}\}$
- 这就是自动门控制器的完整形式化描述。
⚠️ [易错点]
- 图的歧义 vs. 表格的清晰: 状态图为了简洁,有时会将多个输入标记在同一条箭头上(如 0,1)。而状态转移表则必须为每个输入单独列出一列,这使得它在结构上更加严谨和清晰。在进行形式化描述时,使用表格来定义 $\delta$ 是一个好习惯。
- 符号的规范: 在书写形式化描述时,要严格使用数学符号,比如用花括号表示集合,用 $q_0$ 表示起始状态,用 $F$ 表示接受状态集。
📝 [总结]
本段以自动机 $M_1$ 为例,亲身示范了如何应用定义 1.5,将一个图形化的状态图转换为一个严谨的、由五元组构成的形式化描述。这个过程是连接直观理解和数学分析的桥梁。
🎯 [存在目的]
本段的目的是巩固读者对定义 1.5 的理解。通过一个“动手”的例子,展示了形式化定义并不是空中楼阁,而是可以用来精确描述具体自动机的实用工具。它教会了读者一种重要的“翻译”技能:从图到符号。
🧠 [直觉心智模型]
- 个人信息登记表:
- 状态图就像一个人的照片和简介。你可以大致了解他的长相和事迹。
- 形式化五元组就像他的标准个人信息登记表,上面有几项必填字段:
- 曾用名列表 (Q): [小明, 大明, 老明]
- 掌握的语言 (Σ): [中文, 英文]
- 反应模式 (δ): (一个巨大的表格,说明了“听到中文的‘你好’会回答‘你好’”, “听到英文的‘Hello’会回答‘Hello’”)
- 出生时姓名 (q₀): 小明
- 感到开心的状态 (F): [收到工资时, 吃饱饭时]
这个登记表就是对这个人的形式化描述。
💭 [直观想象]
想象你是一名侦探,拿到了一张犯罪团伙的成员关系图(状态图)。现在你需要向总部提交一份标准化的报告(形式化描述)。
- 成员列表 (Q): 你列出所有嫌疑人的代号:{alpha, beta, gamma}。
- 联络暗号 (Σ): 你破译了他们使用的所有暗号:{storm, sunshine}。
- 行动指令 (δ): 你整理出一张表格,说明每个成员在收到不同暗号后会去联系谁。
- 初始接头人 (q₀): alpha。
- 核心头目 (F): {gamma}。
这份报告就是对这个犯罪团伙网络的形式化描述。
1.1.2.7. 语言的识别与接受
📜 [原文18]
如果 $A$ 是机器 $M$ 接受的所有串的集合,我们说 $A$ 是机器 $M$ 的语言,并写为 $L(M)=A$。我们说 $M$ 识别 $A$ 或 $M$ 接受 $A$。因为“接受”一词在指机器接受串和机器接受语言时有不同的含义,为了避免混淆,我们更倾向于对语言使用“识别”一词。
一台机器可以接受几个串,但它总是只识别一种语言。如果机器不接受任何串,它仍然识别一种语言——即空语言 $\emptyset$。
在我们的例子中,设
$$
\begin{aligned}
A=\{w \mid & w \text { 包含至少一个 } 1 \text { 并且 } \\
& \quad \text { 最后一个 } 1 \text { 后跟随偶数个 } 0 \text {s }\}。
\end{aligned}
$$
那么 $L\left(M_{1}\right)=A$,或者等价地说,$M_{1}$ 识别 $A$。
📖 [逐步解释]
这段话定义了有限自动机和语言之间最核心的关系,并对两个容易混淆的词——“接受”和“识别”——做了区分。
- 定义“机器的语言”:
- 一个自动机 $M$ 可以对无数个输入串进行测试,其中一些会被接受,另一些会被拒绝。
- 把所有被 $M$ 接受的串收集起来,放在一个集合里,这个集合就被称为“机器 $M$ 的语言”。
- 形式化记号: 我们用 $L(M)$ 来表示机器 $M$ 的语言。所以,$L(M) = \{w \mid M \text{ 接受 } w\}$。其中 $w$ 代表一个输入串。
- 区分“接受 (accept)”和“识别 (recognize)”:
- 这是一个非常重要的术语辨析,旨在提高表达的精确性。
- 接受 (Accept): 这个动词的主语是机器,宾语是单个的字符串。
- 例句:“机器 $M_1$ 接受字符串 1101。”
- 识别 (Recognize): 这个动词的主语是机器,宾语是一个语言(即一个字符串的集合)。
- 例句:“机器 $M_1$ 识别语言 $A$。”
- 作者的建议: 尽管也有人说“机器接受语言”,但为了避免混淆(“接受”既可以对串也可以对语言),最好是养成习惯:对串用“接受”,对语言用“识别”。
- 一一对应关系:
- 一台机器 $M$ 识别且只识别唯一一个语言 $L(M)$。这个语言是由它所能接受的所有串构成的。
- 一台机器可以接受很多个(甚至无限个)串。
- 极端情况: 如果一台机器一个串都不接受(比如它没有接受状态,或者接受状态不可达),那么它的语言是什么?是空语言,记为 $\emptyset$ (空集)。它仍然识别了一个语言,只不过这个语言里没有任何串。
- $M_1$ 的语言:
- 作者在这里正式给出了之前我们通过归纳分析得出的 $M_1$ 所识别的语言 $A$ 的描述。
- 语言 $A$ 的描述: $A$ 是一个集合,集合中的元素 $w$ (字符串) 满足两个条件:1. $w$ 中必须有 1。2. $w$ 中最后一个 1 的后面,跟着偶数个 0。
- 建立等式: $L(M_1) = A$。这句话是本节分析的最终结论,它精确地指明了机器 $M_1$ 和语言 $A$ 之间的等价关系。
💡 [数值示例]
- 示例1: 串 100
- 我们在之前的例子中看到,机器 $M_1$ 接受串 100。
- 我们来检查 100 是否属于语言 $A$。
- 条件1: 100 包含 1。满足。
- 条件2: 最后一个1是第一个字符,后面跟了两个0。2是偶数。满足。
- 因为 100 满足语言 $A$ 的定义,所以 100 $\in A$。这与 $M_1$ 接受 100 的事实相符。
- 示例2: 串 10
- 我们在之前的例子中看到,机器 $M_1$ 拒绝串 10。
- 我们来检查 10 是否属于语言 $A$。
- 条件1: 10 包含 1。满足。
- 条件2: 最后一个1是第一个字符,后面跟了一个0。1是奇数,不是偶数。不满足。
- 因为 10 没有满足语言 $A$ 的所有条件,所以 10 $\notin A$。这与 $M_1$ 拒绝 10 的事实相符。
⚠️ [易错点]
- 语言是集合: 一定要牢记语言是一个集合。自动机处理的是串(元素),识别的是语言(集合)。
- 空语言 vs. 包含空串的语言:
- 空语言 $\emptyset$:这个语言(集合)里什么都没有。一个识别它的机器会拒绝所有输入串,包括空串 $\varepsilon$。
- 包含空串的语言 $\{\varepsilon\}$:这个语言(集合)里只有一个元素,就是空串 $\varepsilon$。一个识别它的机器只会接受 $\varepsilon$,并拒绝所有其他非空串。这两者是完全不同的。
📝 [总结]
本段定义了机器与其所识别的语言之间的关系,即 $L(M)$ 是 $M$ 所接受的所有串的集合。同时,为了精确性,推荐使用“接受”来描述机器与串的关系,用“识别”来描述机器与语言的关系。最后,明确了 $M_1$ 所识别的语言 $A$ 的数学描述。
🎯 [存在目的]
本段的目的是建立计算理论中一个最核心的等价关系:一个计算装置(有限自动机)等价于一个它所能解决的问题的集合(它所识别的语言)。这是连接“机器”和“问题”的桥梁。从这里开始,我们可以互换地讨论自动机和它们所识别的语言,例如,研究一类语言的性质,就等同于研究能够识别这些语言的机器的能力。
🧠 [直觉心智模型]
- 俱乐部的会员资格:
- 俱乐部 (Club): 就是自动机 $M$。
- 会员名单 (Membership List): 就是语言 $L(M)$。
- 申请人 (Applicant): 就是输入串 $w$。
- 俱乐部的审核过程:
- 俱乐部审核一个申请人,如果符合标准,就接受 (accept) 他成为会员。
- 俱乐部的存在,是为了识别 (recognize) 所有符合其标准的潜在会员组成的那个群体(即语言)。
- 所以,俱乐部接受的是个体,识别的是群体。
💭 [直观想象]
想象一个质检机器 $M$ 在传送带上检验产品 $w$。
- 机器每检验一个产品,就会在产品上盖一个戳:“合格”(接受)或“不合格”(拒绝)。
- 我们将所有被盖上“合格”戳的产品收集起来,装在一个大箱子里。这个大箱子里的所有产品集合,就是这台质检机器定义的“合格品”语言 $L(M)$。
- 所以,我们可以说:
- 这台机器 $M$ 接受了(盖了合格戳)这一个具体的产品 $w$。
- 这台机器 $M$ 的功能是识别 所有合格品这个品类(语言 $A$)。
11.3. 有限自动机的例子
1.1.3.1. 例子 1.7
📜 [原文19]
例子 1.7
这是有限自动机 $M_{2}$ 的状态图。

图 1.8
两状态有限自动机 $M_{2}$ 的状态图
在形式化描述中,$M_{2}$ 是 $\left(\left\{q_{1}, q_{2}\right\},\{0,1\}, \delta, q_{1},\left\{q_{2}\right\}\right)$。转移函数 $\delta$ 是
| | 0 | 1 |
| :---: | :---: | :---: |
| $q_{1}$ | $q_{1}$ | $q_{2}$ |
| $q_{2}$ | $q_{1}$ | $q_{2}$。 |
请记住,$M_{2}$ 的状态图和 $M_{2}$ 的形式化描述包含相同的信息,只是形式不同。您总能在必要时从一种形式转换到另一种形式。
理解任何机器的一个好方法是尝试一些示例输入串。当您进行这些“实验”以查看机器如何工作时,其工作方式通常会变得明显。在示例串 1101 上,机器 $M_{2}$ 从其起始状态 $q_{1}$ 开始,读取第一个 1 后首先进入状态 $q_{2}$,然后读取 1、0 和 1 后进入状态 $q_{2}、q_{1}$ 和 $q_{2}$。该串被接受,因为 $q_{2}$ 是一个接受状态。但串 110 使 $M_{2}$ 停留在状态 $q_{1}$,因此被拒绝。在尝试更多例子后,您会发现 $M_{2}$ 接受所有以 1 结尾的串。因此 $L\left(M_{2}\right)=\{w \mid w \text { 以 1 结尾}\}$。
📖 [逐步解释]
这个例子展示了一个非常简单和基础的有限自动机 $M_2$,并引导读者通过实验来发现它所识别的语言。
- 展示自动机 $M_2$:
- 状态图 (图 1.8): 包含两个状态 $q_1, q_2$。$q_1$ 是起始状态,$q_2$ 是接受状态。
- 形式化描述: 紧接着给出了 $M_2$ 完整的五元组定义,包括其转移函数 $\delta$ 的表格形式。
- 强调等价性: 作者再次提醒读者,状态图和形式化描述是同一事物两种不同的“外貌”,信息是完全等价的。
- 提出分析方法:
- 作者给出了一个非常实用的建议:“理解任何机器的一个好方法是尝试一些示例输入串。” 这是一种“黑盒测试”或“实验归纳”的思维方式。
- 进行实验:
- 实验1: 输入串 1101
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{1} q_2$
- 最终状态: $q_2$。是接受状态。
- 结论: 接受 1101。
- 实验2: 输入串 110
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_1$
- 最终状态: $q_1$。不是接受状态。
- 结论: 拒绝 110。
- 归纳总结:
- 通过更多的实验(读者可以自行尝试,如 001, 101, 000 等),可以发现一个规律。
- 让我们分析状态的含义:
- $q_1$: 观察到,只要输入是 0,或者从 $q_2$ 输入 0,都会回到 $q_1$。这似乎是“上一个输入是0”或“从未见过1”的状态。
- $q_2$: 只要输入是 1,就会进入或停留在 $q_2$。这似乎是“上一个输入是1”的状态。
- 因为 $q_2$ 是接受状态,所以当且仅当最后一个输入符号是 1 时,自动机才会停留在 $q_2$。
- 最终规律: $M_2$ 接受所有以 1 结尾的字符串。
- 给出语言的形式化描述:
- $L(M_2) = \{w \mid w \text{ 以 1 结尾}\}$。
💡 [数值示例]
- 示例1: 串 00101
- $q_1 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{1} q_2$
- 最终在 $q_2$,接受。符合“以1结尾”的规律。
- 示例2: 串 11100
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{0} q_1$
- 最终在 $q_1$,拒绝。符合“不以1结尾”(以0结尾)的规律。
⚠️ [易错点]
- 空串 $\varepsilon$: 输入是空串,停留在起始状态 $q_1$。$q_1$ 不是接受状态,所以拒绝 $\varepsilon$。这符合“以1结尾”的规律(空串没有结尾,自然不以1结尾)。
- 只看最后一个符号: 这个自动机的“记忆”非常短。它只记得上一个符号是什么。从 $q_1$ 状态的自环 0 和 $q_2$ 状态的自环 1 可以看出,之前的历史只要不影响最后一个符号,就都被“忘记”了。
📝 [总结]
例子1.7展示了一个简单的双状态自动机 $M_2$。通过实验和归纳,我们发现它识别的语言是所有以符号 1 结尾的字符串。这个例子强化了通过运行示例串来理解自动机功能的方法。
🎯 [存在目的]
本例子的目的是提供一个比 $M_1$ 更简单的“入门级”自动机,让读者可以轻松地分析其行为并准确地描述其语言。它作为一个模板,展示了从自动机定义到语言描述的标准分析流程。
🧠 [直觉心智模型]
- 一个只关心“最后一声”的裁判:想象一场比赛,有两个信号灯:绿灯($q_2$, 接受)和红灯($q_1$, 拒绝)。比赛由一系列声音组成(输入0或1)。裁判的规则很简单:
- 比赛开始时,红灯亮。
- 只要听到声音0,红灯就亮。
- 只要听到声音1,绿灯就亮。
- 比赛结束时,看哪个灯亮着,就是最终结果。
这个裁判只关心最后一声是什么,完全不理会之前的声音序列。这个裁判就是自动机 $M_2$。
💭 [直观想象]
想象一个电灯开关。它有两个位置:ON ($q_2$) 和 OFF ($q_1$)。
- OFF 是初始位置。
- 开关旁边有两个按钮:按钮0 和 按钮1。
- 规则是:
- 无论灯是开是关,按 按钮0,灯都会变成 OFF 状态(或者保持 OFF)。
- 无论灯是开是关,按 按钮1,灯都会变成 ON 状态(或者保持 ON)。
- 你在一顿操作(输入一串 0 和 1)之后,如果灯最后是 ON 的,你就赢了。
- 很明显,你只有在最后一下按的是 按钮1 的情况下,灯才会是 ON 的。这个开关就是 $M_2$。
1.1.3.2. 例子 1.9
📜 [原文20]
例子 1.9
考虑有限自动机 $M_{3}$。

图 1.10
两状态有限自动机 $M_{3}$ 的状态图
机器 $M_{3}$ 与 $M_{2}$ 相似,只是接受状态的位置不同。像往常一样,机器接受所有在读完后使其停留在接受状态的串。请注意,由于起始状态也是一个接受状态,$M_{3}$ 接受空串 $\varepsilon$。一旦机器开始读取空串,它就到达了末尾;因此,如果起始状态是接受状态,则 $\varepsilon$ 被接受。除了空串之外,这台机器还接受任何以 0 结尾的串。这里,
$$
L\left(M_{3}\right)=\{w \mid w \text { 是**空串** } \boldsymbol{\varepsilon} \text { 或以 0 结尾}\}$。
$$
📖 [逐步解释]
这个例子通过对 $M_2$ 做一个微小的改动,来展示这种改动对所识别的语言产生的巨大影响,并特别强调了对空串 $\varepsilon$ 的处理。
- 与 $M_2$ 的对比:
- $M_3$ 的状态图结构(状态和转移箭头)与 $M_2$ 完全一样。
- 唯一的区别: 接受状态从 $q_2$ 换成了 $q_1$。$q_1$ 现在是双圈,而 $q_2$ 是单圈。
- 分析改动带来的影响:
- 由于转移逻辑不变,我们可以重用之前对 $M_2$ 状态含义的分析,但结论要反过来。
- $q_1$ 这个状态,是在“从未见过1”或“上一个符号是0”时达到的。
- $q_2$ 这个状态,是在“上一个符号是1”时达到的。
- 现在 $q_1$ 成了接受状态。因此,当且仅当自动机结束在 $q_1$ 状态时,输入串才被接受。
- 这意味着,一个串被接受,当且仅当它“以0结尾”,或者它从未包含过1(比如 000),或者它是一个空串。
- 对空串 $\varepsilon$ 的特别说明:
- 这是一个非常重要的知识点。
- 处理过程: 当输入是空串 $\varepsilon$ 时,自动机不读取任何符号,因此它根本不离开其起始状态。
- 判决: 计算“立即”结束,自动机停留在起始状态 $q_1$。
- 结论: 因为 $q_1$ 在 $M_3$ 中是一个接受状态,所以空串 $\varepsilon$ 被 $M_3$ 接受。
- 一般规律: 一个有限自动机接受空串 $\varepsilon$,当且仅当其起始状态也是一个接受状态。
- 总结语言:
- 结合以上两点,被 $M_3$ 接受的串有两种:
- 空串 $\varepsilon$。
- 任何以 0 结尾的非空字符串。
- 形式化描述: $L(M_3) = \{w \mid w \text{ 是空串 } \varepsilon \text{ 或以 0 结尾}\}$。
💡 [数值示例]
- 示例1: 串 1010
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_1$
- 最终状态是 $q_1$。$q_1$ 是接受状态。所以 1010 被接受。
- 验证规律:1010 以 0 结尾,符合。
- 示例2: 串 101
- $q_1 \xrightarrow{1} q_2$
- $q_2 \xrightarrow{0} q_1$
- $q_1 \xrightarrow{1} q_2$
- 最终状态是 $q_2$。$q_2$ 不是接受状态。所以 101 被拒绝。
- 验证规律:101 以 1 结尾,不符合。
- 示例3: 空串 $\varepsilon$
- 不移动,停留在起始状态 $q_1$。$q_1$ 是接受状态。所以 $\varepsilon$ 被接受。
- 验证规律:符合“是空串 $\varepsilon$”这一条。
⚠️ [易错点]
- 接受状态 vs. 起始状态: 这个例子清楚地表明,起始状态和接受状态是两个独立的概念,但它们可以重合。一个状态可以既是起始状态又是接受状态(如 $M_3$ 中的 $q_1$),也可以只是其中之一(如 $M_2$ 中的 $q_1$ 和 $q_2$),或两者都不是(在一个更复杂的自动机中)。
- 语言描述的完备性: 在描述语言时,要特别注意空串 $\varepsilon$ 这个边界情况。如果起始状态是接受状态,在描述语言时就不能遗漏“是空串 $\varepsilon$”这个条件。
📝 [总结]
例子1.9通过微调自动机 $M_2$ 的接受状态得到 $M_3$,展示了仅仅一个状态的“身份”改变,就能使其所识别的语言从“以1结尾”变为“是空串或以0结尾”。本例最重要的教学点是阐明了有限自动机处理空串 $\varepsilon$ 的规则:当且仅当起始状态是接受状态时,$\varepsilon$ 被接受。
🎯 [存在目的]
本例子的目的是深化读者对五元组中每个组件作用的理解。它通过一个“控制变量”的实验(只改变 $F$),清晰地展示了接受状态集 $F$ 如何直接决定语言的归属。同时,它也是引入和讲解空串 $\varepsilon$ 这个重要边界情况的最佳时机。
🧠 [直觉心智模型]
- “出门” vs “回家”:
- 把 $q_1$ 想象成“在家”,$q_2$ 想象成“出门”。输入0代表“处理家务”,输入1代表“外出办事”。
- 在 $M_2$ 中,接受状态是 $q_2$(出门)。它的目标是“只要你最后一步是外出办事,就算完成任务”。
- 在 $M_3$ 中,接受状态是 $q_1$(在家)。它的目标是“只要你最后一步是处理家务(或者压根没出门),就算完成任务”。
- 对于 $M_3$,“没出门”(空串 $\varepsilon$)本身就是一种“完成任务”的状态,因为它最终人“在家”。
💭 [直观想象]
想象一个简单的投票系统,有两个灯:赞成 ($q_1$) 和 反对 ($q_2$)。
- 初始时,赞成灯亮。
- 输入0代表投“赞成”票,输入1代表投“反对”票。
- 规则是:最后一个投票者的意愿决定最终结果。
- 自动机 $M_3$ 就代表了这个系统。赞成灯($q_1$)是接受状态。
- 如果投票序列是 1010,最后是0(赞成),赞成灯亮,结果被接受。
- 如果根本没人投票(空串 $\varepsilon$),系统默认的初始状态就是赞成,结果也被接受。
1.1.3.3. 例子 1.11
📜 [原文21]
例子 1.11
下图显示了一个五状态机器 $M_{4}$。

图 1.12
有限自动机 $M_{4}$
机器 $M_{4}$ 有两个接受状态 $q_{1}$ 和 $r_{1}$,并在字母表 $\Sigma=\{\mathrm{a}, \mathrm{b}\}$ 上操作。一些实验表明它接受串 a, b, aa, bb 和 bab,但不接受串 ab, ba 或 bbba。这台机器从状态 $s$ 开始,读取输入中的第一个符号后,它要么向左进入 $q$ 状态,要么向右进入 $r$ 状态。在这两种情况下,它都无法返回到起始状态(与前面的例子相反),因为它没有办法从任何其他状态回到 $s$。如果输入串中的第一个符号是 a,那么它向左移动并在串以 a 结尾时接受。类似地,如果第一个符号是 b,机器向右移动并在串以 b 结尾时接受。因此 $M_{4}$ 接受所有以相同符号开头和结尾的串。换句话说,$M_{4}$ 接受以相同符号开头和结尾的串。
📖 [逐步解释]
这个例子引入了一个结构更复杂、状态更多的自动机 $M_4$,它的行为不再仅仅取决于最后一个符号,而是与第一个和最后一个符号都有关。
- 自动机 $M_4$ 的结构分析:
- 状态: 共有5个状态:$s, q_1, q_2, r_1, r_2$。
- 字母表: $\Sigma = \{a, b\}$。
- 起始状态: $s$。
- 接受状态: 有两个,$q_1$ 和 $r_1$。这是一个多接受状态的例子。
- 转移结构:
- 从起始状态 $s$ 出发,读a进入“左半边”的 $q_1$,读b进入“右半边”的 $r_1$。
- 一旦离开 $s$,就再也回不来了。整个自动机呈现出一种“决策分支”的结构。
- 左半边 (q-group): $q_1$ 和 $q_2$ 负责处理第一个符号是 a 的情况。
- 右半边 (r-group): $r_1$ 和 $r_2$ 负责处理第一个符号是 b 的情况。
- 实验与行为分析:
- 接受的串: a, b, aa, bb, bab。
- 拒绝的串: ab, ba, bbba。
- 分情况归纳逻辑:
- Case 1: 串以 a 开头
- 第一个输入 a 会使自动机从 $s$ 转移到 $q_1$。
- $q_1$ 是一个接受状态。这意味着,如果串只有一个 a,它停在 $q_1$,被接受。
- 之后,如果读到更多的 a,自动机会从 $q_1$ 转移到 $q_1$(自环),保持在接受状态。
- 如果读到 b,会从 $q_1$ 转移到 $q_2$(非接受状态)。
- 在 $q_2$ 状态(表示上一个符号是b),如果再读到 a,会回到 $q_1$(接受状态);如果读到 b,则停留在 $q_2$。
- 总结左半边的逻辑: 一旦以 a 开头进入左半边,自动机当且仅当最后一个读入的符号是 a 时,才会停留在接受状态 $q_1$。
- 结论: $M_4$ 接受所有以 a 开头且以 a 结尾的串。
- Case 2: 串以 b 开头
- 第一个输入 b 会使自动机从 $s$ 转移到 $r_1$。
- $r_1$ 也是一个接受状态。这意味着单符号串 b 被接受。
- 右半边的逻辑与左半边完全对称:一旦以 b 开头进入右半边,自动机当且仅当最后一个读入的符号是 b 时,才会停留在接受状态 $r_1$。
- 结论: $M_4$ 接受所有以 b 开头且以 b 结尾的串。
- 综合结论:
- 将两种情况合二为一,$M_4$ 接受的语言是“所有以 a 开头且以 a 结尾的串” 并上 “所有以 b 开头且以 b 结尾的串”。
- 这个语言可以更简洁地描述为:所有以相同符号开头和结尾的非空字符串。
💡 [数值示例]
- $s \xrightarrow{b} r_1$
- $r_1 \xrightarrow{a} r_2$
- $r_2 \xrightarrow{b} r_1$
- 最终在 $r_1$,是接受状态。接受 bab。
- 规律验证:以b开头,以b结尾。符合。
- 示例2: 串 ab
- $s \xrightarrow{a} q_1$
- $q_1 \xrightarrow{b} q_2$
- 最终在 $q_2$,不是接受状态。拒绝 ab。
- 规律验证:以a开头,以b结尾。不符合。
- 示例3: 串 a
- $s \xrightarrow{a} q_1$
- 最终在 $q_1$,是接受状态。接受 a。
- 规律验证:以a开头,以a结尾。符合(开头和结尾是同一个字符)。
⚠️ [易错点]
- 空串 $\varepsilon$: 起始状态 $s$ 不是接受状态,所以 $M_4$ 拒绝 $\varepsilon$。这符合语言的描述,因为空串没有开头也没有结尾,谈不上“以相同符号开头和结尾”。
- 单字符的串: 串 a 和 b 均被接受,因为它们的开头和结尾是同一个字符。
- 状态的记忆功能: 这个例子很好地展示了状态如何“记忆”关键信息。
- 状态 $s$ 的存在本身就是一种记忆:“还未读取任何符号”。
- 一旦进入q-group或r-group,自动机就“记住”了第一个符号是 a 还是 b。
- 在q-group中,状态 $q_1$ 和 $q_2$ 的区别在于“记住了”上一个符号是 a 还是 b,从而决定当前是否处于接受状态。
📝 [总结]
例子1.11通过一个结构更对称、更复杂的五状态自动机 $M_4$,展示了有限自动机如何通过状态来“记忆”输入串的早期信息(如第一个符号),并将其与后续信息(如最后一个符号)结合起来进行判断。最终得出结论,$M_4$ 识别的语言是所有以相同符号开头和结尾的非空字符串。
🎯 [存在目的]
本例子的目的是展示有限自动机比“只看最后一位”的简单模型更强的能力。它需要“记忆”两位信息:第一位是什么,和最后一位是什么。通过将这种记忆分散到不同的状态组和状态中,有限自动机巧妙地解决了这个问题。这为后续设计更复杂的自动机提供了设计模式的启发,即“用状态来编码需要记住的历史信息”。
🧠 [直觉心智模型]
- “讲究对称”的质检员:一个质检员要检查一串彩珠 (a代表红珠, b代表蓝珠)。他的规则很特别:
- 他先看第一个珠子是什么颜色,然后拿出对应颜色的“起始托盘”(a对应q-托盘,b对应r-托盘)。
- 然后他看剩下的珠子,但只关心最后一个珠子的颜色。
- 如果最后一个珠子的颜色和他拿出的“起始托盘”颜色一样,他就判定这串彩珠合格。
- 自动机 $M_4$ 就是这个质检员。状态 $q_1, q_2$ 就是在q-托盘上工作,状态 $r_1, r_2$ 就是在r-托盘上工作。$q_1, r_1$ 代表“目前为止,最后一个珠子颜色是对的”,$q_2, r_2$ 代表“目前为止,最后一个珠子颜色是错的”。
💭 [直观想象]
想象一个迷宫,入口是 $s$。迷宫在入口处就分成了两条岔路:标a的左岔路和标b的右岔路。一旦选了路,就不能回头。
- 左岔路通往一个“红色主题”区域,里面有两个房间 $q_1$ 和 $q_2$。$q_1$ 房间是出口(接受状态)。在这个区域里,如果你当前在的房间门口标着a,你就能进入或停留在出口房间 $q_1$。如果标着b,你就会被困在普通房间 $q_2$。
- 右岔路通往一个“蓝色主题”区域,逻辑和左边一样,只是颜色反过来。出口房间是 $r_1$。
- 你手里拿着一串指令 aba。
- 第一步是a,你走了左岔路,进入 $q_1$(出口)。
- 第二步是b,你从 $q_1$ 移动到了 $q_2$(普通房间)。
- 第三步是a,你从 $q_2$ 移回了 $q_1$(出口)。
- 指令结束,你停在 $q_1$,是一个出口。所以你成功走出迷宫。
1.1.3.4. 例子 1.13
📜 [原文22]
例子 1.13
图 1.14 显示了三状态机器 $M_{5}$,它有一个四符号输入字母表,$\Sigma=\{\langle$ RESET $\rangle, 0,1,2\}$。我们将 $\langle$ RESET $\rangle$ 视为一个单一符号。

图 1.14
有限自动机 $M_{5}$
机器 $M_{5}$ 保持其读取的数值输入符号之和模 3 的运行计数。每当它接收到 $\langle$ RESET $\rangle$ 符号时,它将计数重置为 0。如果和是模 3 为 0,换句话说,如果和是 3 的倍数,它就接受。
📖 [逐步解释]
这个例子展示了一个用于算术计算的有限自动机,特别是模运算,并引入了“重置”功能。
- 自动机 $M_5$ 的结构分析:
- 状态: 三个状态,$q_0, q_1, q_2$。
- 字母表: $\Sigma = \{\langle\text{RESET}\rangle, 0, 1, 2\}$。这是一个包含非标准字符的字母表。被当作一个整体的符号,就像0或1一样。
- 起始状态: $q_0$。
- 接受状态: $q_0$。这是一个起始状态同时也是接受状态的例子,因此它会接受空串 $\varepsilon$。
- 自动机功能的描述:
- 核心功能: 计算到目前为止读过的所有数值符号(0, 1, 2)的总和,但只关心这个总和除以3的余数是多少。这就是“模3的运行计数”。
- 状态的含义:
- $q_0$: 表示当前的“运行和”模3等于0。
- $q_1$: 表示当前的“运行和”模3等于1。
- $q_2$: 表示当前的“运行和”模3等于2。
- 转移的逻辑:
- 输入0: 无论在哪一个状态,读入0,和不变,所以余数不变。因此,所有标0的箭头都是自环。例如,在 $q_1$(余数是1),读0,和+0,余数还是1,所以停在 $q_1$。
- 输入1: 读入1,和加1,余数也加1(模3)。因此,所有标1的箭头都指向“下一个”状态:$q_0 \xrightarrow{1} q_1$, $q_1 \xrightarrow{1} q_2$, $q_2 \xrightarrow{1} q_0$ (因为 (2+1) mod 3 = 0)。
- 输入2: 读入2,和加2,余数也加2(模3)。因此,所有标2的箭头都指向“下下个”状态:$q_0 \xrightarrow{2} q_2$, $q_1 \xrightarrow{2} q_0$, $q_2 \xrightarrow{2} q_1$。
- 重置功能:
- 输入 : 无论当前处于哪个状态(无论之前的和是多少),只要读到 符号,自动机就强制返回到起始状态 $q_0$。
- 这等同于将“运行和”清零。所有状态到 $q_0$ 都有一条标着 的箭头。
- 接受条件:
- 接受状态是 $q_0$。
- 这意味着,当且仅当输入串处理完毕后,数值的总和(在最后一次RESET之后)是3的倍数时,串才被接受。
💡 [数值示例]
- 初始状态 $q_0$ (和=0)。
- $q_0 \xrightarrow{1} q_1$ (和=1, 余1)。
- $q_1 \xrightarrow{2} q_0$ (和=1+2=3, 余0)。
- $q_0 \xrightarrow{1} q_1$ (和=3+1=4, 余1)。
- $q_1 \xrightarrow{0} q_1$ (和=4+0=4, 余1)。
- 最终在 $q_1$,不是接受状态。拒绝 1210。
- 规律验证:总和为4,4不是3的倍数。
- 初始状态 $q_0$ (和=0)。
- $q_0 \xrightarrow{1} q_1$ (和=1, 余1)。
- $q_1 \xrightarrow{1} q_2$ (和=1+1=2, 余2)。
- $q_2 \xrightarrow{\langle\text{RESET}\rangle} q_0$ (和被重置为0)。
- $q_0 \xrightarrow{2} q_2$ (和=2, 余2)。
- $q_2 \xrightarrow{1} q_0$ (和=2+1=3, 余0)。
- 最终在 $q_0$,是接受状态。接受 1121。
- 规律验证:最后一次 后的数值和是 2+1=3,是3的倍数。
⚠️ [易错点]
- <RESET>是一个符号: 要把它看作和0,1,2同等地位的一个输入符号,而不是一个特殊的外部指令。它参与自动机的正常转移流程。
- 空串 $\varepsilon$: 起始状态 $q_0$ 是接受状态,所以 $M_5$ 接受 $\varepsilon$。这符合逻辑,因为空串的数值和为0,0是3的倍数。
- 模运算: 要熟悉模运算的规则,特别是 $(a+b) \pmod n = ((a \pmod n) + (b \pmod n)) \pmod n$。这个性质是这个自动机能工作的数学基础。它不需要存储巨大的和,只需要存储当前的余数(状态)。
📝 [总结]
例子1.13展示了一个利用有限自动机进行模运算的精巧设计。通过将“和模3的余数”映射到三个状态,自动机能够在只有有限内存的情况下,处理任意长度的数值输入流,并判断其总和(可被<RESET>清零)是否为3的倍数。
🎯 [存在目的]
本例子的目的有多个:
- 展示有限自动机可以处理算术性质的语言,只要该性质可以通过有限的“记忆”(即状态)来追踪。模运算是这类性质的完美范例。
- 引入非标准字母表和特殊功能符号(如)的概念,展示了自动机模型的灵活性。
- 通过“状态”=“余数”的映射,深刻地揭示了“用状态编码计算历史的关键信息”这一核心设计思想。
🧠 [直觉心智模型]
- 一个只有3个格子的计数器:想象一个圆形的计数器,上面只有三个格子,分别标着 0, 1, 2。有一个指针,初始指向 0。
- 当输入是数值 n 时,你把指针顺时针拨动 n 格。
- 当输入是 <RESET> 时,你直接把指针拨回到 0。
- 在一系列输入之后,如果指针最后停在 0 号格子上,你就赢了。
- 这个计数器就是 $M_5$。它的指针位置就是自动机的状态。
💭 [直观想象]
想象你在参加一个三人报数的游戏。三个人围成一圈,分别是0号($q_0$)、1号($q_1$)、2号($q_2$)。
- 游戏开始时,球在0号手里。
- 裁判喊出一个数字(输入1或2),比如2,持球者就要把球传给他顺时针方向的第2个人。如果0号有球,他会传给2号。
- 如果裁判喊0,持球者不动。
- 如果裁判喊<RESET>,无论球在谁手里,都必须立刻传回给0号。
- 当裁判喊完一串数字后,如果球最后在0号手里,那么0号所在的队伍就获胜了(接受)。
1.1.3.5. 例子 1.15
📜 [原文23]
例子 1.15
考虑例子 1.13的推广,使用相同的四符号字母表 $\Sigma$。对于每个 $i \geq 1$,设 $A_{i}$ 是所有串的语言,其中数字之和是 $i$ 的倍数,但每当出现符号 $\langle$ RESET $\rangle$ 时,和会重置为 0。对于每个 $A_{i}$,我们给出一个有限自动机 $B_{i}$,识别 $A_{i}$。我们形式化地描述机器 $B_{i}$ 如下:$B_{i}=\left(Q_{i}, \Sigma, \delta_{i}, q_{0},\left\{q_{0}\right\}\right)$,其中 $Q_{i}$ 是 $i$ 个状态的集合 $\left\{q_{0}, q_{1}, q_{2}, \ldots, q_{i-1}\right\}$,我们设计转移函数 $\delta_{i}$,使得对于每个 $j$,如果 $B_{i}$ 处于 $q_{j}$,则运行和是 $j$ 模 $i$。对于每个 $q_{j}$,设
$$
\begin{aligned}
& \delta_{i}\left(q_{j}, 0\right)=q_{j}, \\
& \delta_{i}\left(q_{j}, 1\right)=q_{k}, \text { 其中 } k=j+1 \text { **模** } i, \\
& \delta_{i}\left(q_{j}, 2\right)=q_{k}, \text { 其中 } k=j+2 \text { **模** } i, \text { 以及 } \\
& \delta_{i}\left(q_{j},\langle\text { RESET }\rangle\right)=q_{0} 。
\end{aligned}
$$
📖 [逐步解释]
这个例子不再是描述一个具体的自动机,而是描述一个自动机家族的“制造模板”。它将例子1.13中的“模3”问题推广到了“模i”问题,其中 $i$ 是任意大于等于1的整数。
- 问题的推广:
- 从模3到模i: 不再只关心和是不是3的倍数,而是关心和是不是任意指定整数 $i$ 的倍数。
- 语言家族 $A_i$: 对于每一个整数 $i$ (如 $i=2, 5, 100$),都对应一个语言 $A_i$。
- $A_2$:和是2的倍数(偶数)的串的语言。
- $A_5$:和是5的倍数的串的语言。
- 目标: 为这个语言家族中的每一个语言 $A_i$,都给出一个识别它的有限自动机 $B_i$。
- 自动机模板 $B_i$ 的形式化描述:
- 这里无法画出状态图,因为状态的数量 $i$ 是一个未指定的参数。当参数未知时,形式化描述就显示出了其强大的威力。
- $B_i = (Q_i, \Sigma, \delta_i, q_0, \{q_0\})$
- $Q_i$ (状态集): 为了实现“和模i”的计算,我们需要 $i$ 个状态来分别代表 $i$ 种可能的余数:0, 1, 2, ..., $i-1$。所以,$Q_i = \{q_0, q_1, ..., q_{i-1}\}$。状态的数量是 $i$。
- $\Sigma$ (字母表): 和 $M_5$ 一样,$\Sigma=\{\langle\text{RESET}\rangle, 0,1,2\}$。
- $q_0$ (起始状态) 和 $F$ (接受状态集): 和 $M_5$ 的逻辑一样,起始和接受的都是 $q_0$(代表余数为0)。所以 $F=\{q_0\}$。
- $\delta_i$ (转移函数): 这是设计的核心,它被定义为一个通用的规则。对于任意一个状态 $q_j$ (表示当前余数是 $j$):
- 读0: $\delta_i(q_j, 0) = q_j$。和加0,余数不变。
- 读1: $\delta_i(q_j, 1) = q_k$,其中 $k = (j+1) \pmod i$。和加1,余数变为 $(j+1)$ 模 $i$。
- 读2: $\delta_i(q_j, 2) = q_k$,其中 $k = (j+2) \pmod i$。和加2,余数变为 $(j+2)$ 模 $i$。
- 读: $\delta_i(q_j, \langle\text{RESET}\rangle) = q_0$。和清零,余数变为0。
- 总结: 这段文字提供了一个“自动机生成器”。你给我一个整数 $i$,我就能根据这个模板,生成一个专门识别“和为i的倍数”的语言的自动机 $B_i$。
💡 [数值示例]
- 示例1: 构造 $B_3$
- 让 $i=3$。根据模板,我们得到:
- $Q_3 = \{q_0, q_1, q_2\}$。
- $\Sigma = \{\langle\text{RESET}\rangle, 0, 1, 2\}$。
- $\delta_3$ 的规则是 $k = (j+n) \pmod 3$。
- $q_0 = q_0$。
- $F = \{q_0\}$。
- 我们发现,这样构造出来的 $B_3$ 和例子1.13中的 $M_5$ 是完全一样的。这验证了模板的正确性。
- 示例2: 构造 $B_2$ (识别和为偶数的串)
- 让 $i=2$。
- $Q_2 = \{q_0, q_1\}$ ($q_0$代表偶数和, $q_1$代表奇数和)。
- $\Sigma = \{\langle\text{RESET}\rangle, 0, 1, 2\}$。
- $\delta_2$:
- $\delta_2(q_0, 0)=q_0$, $\delta_2(q_1, 0)=q_1$。
- $\delta_2(q_0, 1)=q_1$, $\delta_2(q_1, 1)=q_0$。
- $\delta_2(q_0, 2)=q_0$, $\delta_2(q_1, 2)=q_1$ (因为2是偶数,不改变奇偶性)。
- $\delta_2(q_j, \langle\text{RESET}\rangle)=q_0$。
- $q_0 = q_0$。
- $F = \{q_0\}$。
- 这个 $B_2$ 自动机可以判断输入的数值和(可重置)是奇数还是偶数。
⚠️ [易错点]
- 参数 $i$ 的角色: $i$ 不是自动机的输入,也不是自动机的状态。它是用来定义这个自动机结构的一个“元参数” (meta-parameter)。对于一个已经构造好的 $B_5$,它的结构是固定的,它只能解决“模5”的问题,不能临时起意去解决“模7”的问题。
- i=1 的情况: 如果 $i=1$,那么 $Q_1=\{q_0\}$,只有一个状态。$k = (0+n) \pmod 1 = 0$。所有转移都回到 $q_0$。因为 $q_0$ 是接受状态,所以这个 $B_1$ 自动机会接受所有输入串。这符合逻辑,因为任何整数都是1的倍数。
📝 [总结]
例子1.15通过形式化描述,将一个具体问题(和模3)推广为一个参数化的问题家族(和模i),并提供了一个可以生成该家族中任何一个有限自动机的“模板”。这极大地展现了形式化定义在处理抽象和广义问题时的优越性。
🎯 [存在目的]
本例子的目的是展示形式化描述的强大威力。当面对一个无法具体画出的、依赖于参数的自动机家族时,状态图就无能为力了,而形式化描述则可以清晰、简洁、无歧-义地定义整个家族的构造规则。这是从描述“一个”对象到描述“一类”对象的飞跃,是数学和理论科学的核心能力之一。
🧠 [直觉心智模型]
- 一个可定制的钟表:这个例子就像是提供了一个钟表的设计图纸。这个钟表的表盘上有 $i$ 个刻度 (0到 $i-1$)。
- 参数 $i$ 就是你定制表盘时决定的刻度总数。你可以做一个12小时的钟,也可以做一个24小时的,或者一个奇特的7小时的。
- 输入n就是把时针拨动n格。
- 输入<RESET>就是把时针拨回到0点。
- 这个设计图纸(形式化描述)可以用来制造出任何小时制的钟表(自动机 $B_i$)。
💭 [直观想象]
想象一个函数 create_modulo_checker(i),它是一个代码生成器。
```python
def create_modulo_checker(i):
2Q = {0, 1, ..., i-1} (状态用数字表示)
3Sigma = {'0', '1', '2', 'RESET'}
5F = {0}
def delta(current_state, symbol):
if symbol == '0':
return current_state
elif symbol == '1':
return (current_state + 1) % i
elif symbol == '2':
return (current_state + 2) % i
elif symbol == 'RESET':
return 0
return (Q, Sigma, delta, q0, F)
```
例子1.15的形式化描述,在精神上就等价于上面这段Python代码。它不是一个自动机,而是制造自动机的程序。
11.4. 计算的形式化定义
📜 [原文24]
到目前为止,我们已经通过状态图和作为一个五元组的形式化定义非形式化地描述了有限自动机。非形式化描述起初更容易理解,但形式化定义对于使概念精确、解决非形式化描述中可能出现的任何歧义很有用。接下来,我们对有限自动机的计算也这样做。我们已经对它的计算方式有了非形式化的概念,现在我们将它数学形式化。
设 $M=\left(Q, \Sigma, \delta, q_{0}, F\right)$ 是一个有限自动机,设 $w=w_{1} w_{2} \cdots w_{n}$ 是一个串,其中每个 $w_{i}$ 是字母表 $\Sigma$ 的一个成员。那么 $M$ 接受 $w$ 如果存在一个状态序列 $r_{0}, r_{1}, \ldots, r_{n}$ 在 $Q$ 中,满足三个条件:
- $r_{0}=q_{0}$,
- $\delta\left(r_{i}, w_{i+1}\right)=r_{i+1}$,对于 $i=0, \ldots, n-1$,并且
- $r_{n} \in F$。
条件 1 表示机器从起始状态开始。条件 2 表示机器根据转移函数从一个状态转移到另一个状态。条件 3 表示如果机器最终停留在接受状态,则接受其输入。我们说 $M$ 识别语言 $A$ 如果 $A=\{w \mid M \text { 接受 } w\}$。
📖 [逐步解释]
这一段是继自动机本身的形式化定义之后,对自动机的“运行过程”或“计算”所做的形式化定义。
- 目的说明:
- 之前,我们形式化定义了自动机这个静态的“机器”是什么。
- 现在,我们要形式化定义这个机器动态的“工作过程”是怎样的。
- 我们之前已经有了非形式化的概念(“从头读到尾,一步步转移”),现在要把它翻译成精确的数学语言。
- 定义的前提:
- 设有一个有限自动机 $M=(Q, \Sigma, \delta, q_0, F)$。
- 设有一个长度为 $n$ 的输入串 $w = w_1w_2...w_n$,其中每个符号 $w_i$ 都属于字母表 $\Sigma$。
- 核心定义:
- “$M$ 接受 $w$”这句话,在数学上等价于:“存在一个长度为 $n+1$ 的状态序列 $r_0, r_1, ..., r_n$”,并且这个序列必须同时满足以下三个条件。
- 状态序列: 这是一个记录了自动机每一步所处状态的列表。注意它的长度是 $n+1$,比输入串的长度 $n$ 多一个,因为它包含了初始状态。
- 三个条件详解:
- 条件1: $r_0 = q_0$
- 含义: 状态序列的第一个状态 $r_0$ 必须是自动机的起始状态 $q_0$。
- 翻译: 计算必须从起始状态开始。
- 条件2: $\delta(r_i, w_{i+1}) = r_{i+1}$,对于 $i=0, ..., n-1$
- 含义: 这是描述状态转移的核心规则。它说,第 $i+1$ 个状态 $r_{i+1}$ 必须是转移函数 $\delta$ 在输入为(第 $i$ 个状态 $r_i$,第 $i+1$ 个输入符号 $w_{i+1}$)时的结果。
- 展开来看:
- 当 $i=0$ 时: $\delta(r_0, w_1) = r_1$ (读完第一个符号 $w_1$ 后,状态从 $r_0$ 变为 $r_1$)。
- 当 $i=1$ 时: $\delta(r_1, w_2) = r_2$ (读完第二个符号 $w_2$ 后,状态从 $r_1$ 变为 $r_2$)。
- ...
- 当 $i=n-1$ 时: $\delta(r_{n-1}, w_n) = r_n$ (读完最后一个符号 $w_n$ 后,状态从 $r_{n-1}$ 变为 $r_n$)。
- 翻译: 机器的每一步状态变化都必须严格遵守其转移函数 $\delta$。
- 条件3: $r_n \in F$
- 含义: 状态序列的最后一个状态 $r_n$(也就是处理完所有输入后的最终状态)必须是接受状态集 $F$ 中的一个成员。
- 翻译: 计算必须结束于一个接受状态。
- 重申“识别”的定义:
- 最后,作者再次用形式化的语言重申了“识别”的定义:$M$ 识别语言 $A$ 的意思是,$A$ 这个集合,正好就等于所有能让 $M$ 接受的串 $w$ 所构成的集合。
💡 [数值示例]
- 示例1: 自动机 $M_2$ (图1.8) 和输入串 $w = 101$
- $M_2 = (\{q_1, q_2\}, \{0,1\}, \delta, q_1, \{q_2\})$。
- $w = w_1w_2w_3 = 101$ ($n=3$)。
- 问题: $M_2$ 是否接受 101?
- 回答: 我们需要判断是否存在一个状态序列 $r_0, r_1, r_2, r_3$ 满足三个条件。
- 寻找序列:
- 根据条件1,$r_0$ 必须是 $q_1$。序列:$[q_1, ?, ?, ?]$
- 根据条件2 ($i=0$): $r_1 = \delta(r_0, w_1) = \delta(q_1, 1) = q_2$。序列:$[q_1, q_2, ?, ?]$
- 根据条件2 ($i=1$): $r_2 = \delta(r_1, w_2) = \delta(q_2, 0) = q_1$。序列:$[q_1, q_2, q_1, ?]$
- 根据条件2 ($i=2$): $r_3 = \delta(r_2, w_3) = \delta(q_1, 1) = q_2$。序列:$[q_1, q_2, q_1, q_2]$
- 我们找到了这样一个唯一的状态序列:$r_0=q_1, r_1=q_2, r_2=q_1, r_3=q_2$。
- 检验条件3: 最后一个状态 $r_3$ 是 $q_2$。$q_2$ 是否属于接受状态集 $F=\{q_2\}$?是的,$q_2 \in \{q_2\}$。
- 结论: 因为存在满足所有三个条件的状态序列,所以 $M_2$ 接受 101。
- 示例2: 自动机 $M_2$ 和输入串 $w = 10$
- $w = w_1w_2 = 10$ ($n=2$)。
- 寻找序列:
- $r_0 = q_1$。
- $r_1 = \delta(r_0, w_1) = \delta(q_1, 1) = q_2$。
- $r_2 = \delta(r_1, w_2) = \delta(q_2, 0) = q_1$。
- 找到的状态序列是 $[q_1, q_2, q_1]$。
- 检验条件3: 最后一个状态 $r_2$ 是 $q_1$。$q_1$ 是否属于接受状态集 $F=\{q_2\}$?不是,$q_1 \notin \{q_2\}$。
- 结论: 状态序列存在,但它不满足条件3。因此 $M_2$ 不接受 (即拒绝) 10。
⚠️ [易错点]
- 存在性: 定义的核心是“如果存在一个...状态序列...”。对于我们目前学的确定性有限自动机(DFA),对于任何输入串,这个状态序列都是唯一的。所以“存在”这个词在这里看起来有点多余。但是,这个词是为了与后续将要学习的“非确定性有限自动机(NFA)”的定义保持一致。在NFA中,对于同一个输入串,可能存在多条不同的计算路径(状态序列),只要其中有任何一条满足这三个条件,串就被接受。所以在这里理解“存在”的深意很重要。
- 下标匹配: 条件2中 $\delta(r_i, w_{i+1}) = r_{i+1}$ 的下标匹配需要特别小心。它表示用第 $i$ 个状态和第 $i+1$ 个输入来决定第 $i+1$ 个状态。
📝 [总结]
本段为有限自动机的“计算过程”提供了严格的数学定义。它将“接受一个字符串”这一行为,精确地定义为“能够找到一个满足起始、转移和接受三个条件的状态序列”。这个定义是连接自动机结构和其语言行为的形式化桥梁。
🎯 [存在目的]
本段的目的是为了能以数学的方式来证明关于语言和自动机的定理。例如,如果要证明某个自动机 $M$ 识别语言 $A$,我们就必须严格地证明以下两点:
- 对于任何属于 $A$ 的串 $w$,我们都能根据此定义构造出一个满足条件的状态序列。
- 对于任何不属于 $A$ 的串 $w$,我们能证明找不到满足条件的状态序列(通常是条件3不被满足)。
没有这个形式化定义,证明将无从谈起。
🧠 [直觉心智模型]
- 提交一份合规的申请表:
- 接受一个串就像是提交一份成功的申请。
- 状态序列 $r_0, ..., r_n$ 就是你填写的申请表的一系列步骤。
- 条件1 ($r_0=q_0$): 你必须从申请流程的第一步(起始状态)开始,不能跳步。
- 条件2 ($\delta(r_i, w_{i+1})=r_{i+1}$): 你填写的每一步信息($w_{i+1}$),都必须导致你进入了系统指定的下一个流程环节($r_{i+1}$)。你的申请路径必须是合法的。
- 条件3 ($r_n \in F$): 你走完所有流程后,最后的状态必须是“申请已批准”(接受状态)。
- 只有当你的申请过程(状态序列)同时满足这三条规定,你的申请(输入串)才会被接受。
💭 [直观想象]
想象一下,你要证明你昨天是按照特定路线开车的。
- 输入串 $w$: 是你开车时遇到的一系列路口指令(比如“左转,直行,右转”)。
- 状态序列 $r$: 是你提供的一系列沿途照片,照片上有时间戳和GPS定位(你所在的位置,即状态)。
- 要让警察相信你的说法(接受你的串),你的照片序列必须满足:
- 条件1:第一张照片必须是在你家车库拍的(起始状态)。
- 条件2:每一张后续照片的地点,都必须是从前一张照片的地点,按照对应的路口指令,能合法开到的地方。你不能伪造一个“瞬移”的路径。
- 条件3:最后一张照片的地点,必须是你的公司停车场(接受状态)。
这个带有证据链的照片序列,就是形式化的“计算”过程。
1.1.4.1. 定义 1.16:正则语言
📜 [原文25]
定义 1.16
如果某个有限自动机识别它,则称该语言为正则语言。
📖 [逐步解释]
这是一个极为重要和核心的定义,它建立了一类语言和一个计算模型之间的直接等价关系。
- 定义的主体: 正则语言 (Regular Language)。这是一个专门的术语,用来称呼某一类特定的语言(字符串的集合)。
- 定义的条件: 一个语言 $A$ 被称为正则语言,其充分必要条件是:存在至少一个有限自动机 $M$,这个自动机 $M$ 识别 $A$(即 $L(M)=A$)。
- 解读:
- 这个定义是在语言和机器之间画上等号。
- “正则语言”这个集合,包含了所有那些“可以用有限自动机来判断其成员资格”的语言。
- 换句话说,有限自动机的能力边界,就定义了正则语言的外延。一个问题(一个语言)如果可以用有限的内存来解决,那它就是“正则”的。如果一个问题所需内存会随着输入规模无限增长,那它就不是“正则”的。
- 存在性: 这里的“某个”(存在一个)很关键。我们不需要所有有限自动机都识别它,只要能找到一个(或者构造出一个)能识别该语言的有限自动机,这个语言就获得了“正则语言”的资格认证。
💡 [数值示例]
- 示例1: 语言 $A = \{w \mid w \text{ 以1结尾}\}$
- 在例子1.7中,我们找到了一个有限自动机 $M_2$ 能够识别这个语言 $A$。
- 根据定义1.16,因为我们找到了这样一个自动机,所以语言 $A$ 是一个正则语言。
- 示例2: 语言 $B = \{w \mid w \text{ 是空串 } \varepsilon \text{ 或以0结尾}\}$
- 在例子1.9中,我们找到了有限自动机 $M_3$ 识别这个语言 $B$。
- 因此,语言 $B$ 也是一个正则语言。
- 示例3: 语言 $C = \{w \mid w \text{ 以相同符号开头和结尾}\}$
- 在例子1.11中,我们找到了有限自动机 $M_4$ 识别这个语言 $C$。
- 因此,语言 $C$ 也是一个正则语言。
- 一个非正则语言的例子(预告): 考虑语言 $D = \{0^n1^n \mid n \ge 0\}$,这个语言包含 $\varepsilon, 01, 0011, 000111, ...$ 等等。即任意数量的0后面跟着相同数量的1。要判断一个串是否属于这个语言,机器必须“数”清楚前面有多少个0,然后再去匹配后面1的数量。如果0的数量可以是任意大,这就需要无限的内存来“计数”。因此,直觉上,有限自动机(内存有限)是无法识别这个语言的。我们将在后续章节严格证明这一点。所以,$D$ 不是一个正则语言。
⚠️ [易错点]
- 混淆概念: “有限自动机”是一种机器,“正则语言”是一个由字符串集合构成的大家族。两者不是一回事,而是通过“识别”这个动作关联起来的。
- 不要说“正则自动机”: 这个说法是错误的。自动机是有限自动机,它识别的语言被称为正则语言。
📝 [总结]
定义1.16 给出了“正则语言”的精确定义:凡是能被某个有限自动机识别的语言,就是正则语言。这个定义将有限自动机这一计算模型和正则语言这一语言类别划上了等号,确立了计算理论的一个基本对应关系。
🎯 [存在目的]
本定义的目的是划定一个疆域。它在所有可能语言(问题的集合)的无限版图上,圈出了一块领地,并命名为“正则语言”。这块领地内的所有问题,都可以被最简单的计算模型——有限自动机——所解决。这个定义是“乔姆斯基谱系”的最低层,是形式语言理论的基石。它使得我们可以开始系统地研究这一类语言的共性、性质和能力边界。
🧠 [直觉心智模型]
- “有驾照”的人:
- 有限自动机就像一个“驾照考官”。
- 语言就像一个“想开车的人”。
- 正则语言就是“所有通过了驾照考试的人”这个群体。
- 定义1.16说的就是:如果你能找到一个“驾照考官”(有限自动机)认可你(识别你所属的语言),那么你就是“有驾照的人”(正则语言)。
💭 [直观想象]
想象一个“正则语言俱乐部”。
- 这个俱乐部的入会标准非常明确:你(一个语言,即一个字符串集合)要想成为会员,必须能找到一个“有限自动机”作为你的“担保人”。
- 这个“担保人”(自动机)必须能完美地履行职责:对于你这个语言中的任何一个成员(字符串),它都亮绿灯(接受);对于任何非你语言成员的字符串,它都亮红灯(拒绝)。
- 只要你能找到这么一个合格的担保人,你就能进入“正则语言俱乐部”。
- 所有以1结尾的字符串组成的语言,找到了 $M_2$ 做担保人,于是它成功入会。
- 所有 $0^n1^n$ 形式的字符串组成的语言,找遍了所有“有限自动机”界的大佬,没有一个能为它担保,所以它被俱乐部拒之门外。
1.1.4.2. 例子 1.17
📜 [原文26]
例子 1.17
以例子 1.13中的机器 $M_{5}$ 为例。设 $w$ 为串
10〈RESET〉22〈RESET〉012。
那么 $M_{5}$ 根据计算的形式化定义接受 $w$,因为它在计算 $w$ 时进入的状态序列是
$$
q_{0}, q_{1}, q_{1}, q_{0}, q_{2}, q_{1}, q_{0}, q_{0}, q_{1}, q_{0}
$$
满足这三个条件。$M_{5}$ 的语言是
$$
\begin{array}{r}
L\left(M_{5}\right)=\{w \mid \text { 在 } w \text { 中的**符号之和**是 0 **模** 3, \\
\text { 除非 } \langle\text { RESET }\rangle \text { 将计数重置为 0 }\}。
\end{array}
$$
由于 $M_{5}$ 识别这种语言,它是一种正则语言。
📖 [逐步解释]
这个例子是将前面几个定义(形式化计算、正则语言)串联起来的一个完整应用。
- 回顾机器和输入:
- 机器: 例子1.13中的 $M_5$,它计算数值和模3。
- 输入串 $w$: 1022012。这是一个长度为9的串。
- 应用计算的形式化定义:
- 作者宣称 $M_5$ 接受 $w$,并给出了证据——一个长度为 $9+1=10$ 的状态序列。
- 验证这个状态序列:
- 串 w: 1, 0, , 2, 2, , 0, 1, 2
- 状态 r: $q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_1 \xrightarrow{\text{<R>}} q_0 \xrightarrow{2} q_2 \xrightarrow{2} q_1 \xrightarrow{\text{<R>}} q_0 \xrightarrow{0} q_0 \xrightarrow{1} q_1 \xrightarrow{2} q_0$
- 这个推导出的状态序列与原文给出的 q_0, q_1, q_1, q_0, q_2, q_1, q_0, q_0, q_1, q_0 完全匹配。
- 检验三个条件:
- 条件1 (起始): 序列的第一个状态 $q_0$ 是 $M_5$ 的起始状态。满足。
- 条件2 (转移): 上述推导过程的每一步都严格遵循了 $M_5$ 的转移函数。满足。
- 条件3 (接受): 序列的最后一个状态是 $q_0$。$M_5$ 的接受状态集 $F=\{q_0\}$。$q_0 \in F$。满足。
- 结论: 因为存在满足所有三个条件的状态序列,所以根据形式化定义,$M_5$ 接受 $w$。
- 描述语言并判定其类别:
- 首先给出 $M_5$ 所识别的语言 $L(M_5)$ 的自然语言描述:在最后一次之后,数值和是3的倍数的那些串的集合。
- 然后应用定义1.16:
- 我们有一个语言 $L(M_5)$。
- 我们有一个有限自动机 $M_5$ 识别它。
- 因此,根据定义,这个语言 $L(M_5)$ 是一个正则语言。
💡 [数值示例]
- 示例1(原文示例): 已详细分析。
- 示例2: 串 $w = 222$
- 状态序列: $q_0 \xrightarrow{2} q_2 \xrightarrow{2} q_1 \xrightarrow{2} q_0$。序列为 $[q_0, q_2, q_1, q_0]$。
- 检验:
- 起始于 $q_0$。√
- 转移合法。√
- 结束于 $q_0 \in F$。√
- 结论: $M_5$ 接受 222。
- 语言类别: 因为 $M_5$ 识别的语言(和是3的倍数)是一个正则语言。
⚠️ [易错点]
- 证明的严谨性: 口头上说“它的和是3的倍数,所以被接受”是非形式化的。严格的证明是,像本例一样,明确地写出那个满足所有三个条件的状态序列。这是将直觉转化为数学证明的关键一步。
📝 [总结]
本例子是一个“总复习”,它将自动机 $M_5$、一个具体的输入串、计算的形式化定义、语言的描述以及正则语言的定义全部串联在一起,完整地走了一遍“自动机 -> 计算过程 -> 接受/拒绝 -> 语言 -> 语言类别判定”的完整逻辑链条。
🎯 [存在目的]
本例子的目的是展示前面所学的所有形式化概念是如何协同工作的。它提供了一个范本,告诉读者如何利用形式化定义来严格地论证一个串被一个自动机接受,并由此得出关于该自动机所识别的语言的性质(即它是正则的)。
🧠 [直觉心智模型]
- 法庭判案:
- 法官: 你 (分析者)
- 被告: 输入串 $w$
- 法律条文: 有限自动机 $M_5$ 的定义。
- 检方指控: “被告 $w$ 属于语言 $L(M_5)$”。
- 你的任务: 判定指控是否成立。
- 你的判决过程: 你不需要自由心证,而是严格依照“计算的形式化定义”这部“程序法”来审理。你找到了一个完整的证据链(状态序列),这个证据链的起点、每一步以及终点都完全符合法律条文(三个条件)。
- 最终判决: “本庭宣布,被告 $w$ 被机器 $M_5$ 接受。”
- 进一步推论: “鉴于机器 $M_5$ 是一个有限自动机,根据‘正则语言定义法’,其所识别的语言 $L(M_5)$ 被归类为正则语言。”
💭 [直观想象]
想象你在填写一份报税单。
- 输入串: 你一年中所有的收入和支出记录。
- 自动机 $M_5$: 税务局的自动计算软件。它的状态是你当前的应税收入等级(比如低、中、高)。
- 计算过程: 软件读取你的一条条记录,不断更新你的应税等级。
- 状态序列: 软件在后台生成的你的等级变化日志。
- 接受状态: “无需补税”或“有退税”的状态。
- 例子1.17就像是审计员在审查你的报税单。他拿到了你的收支记录 $w$,然后用税务局的软件跑了一遍,得到了一个等级变化日志(状态序列)。他检查这个日志的起始、过程和结尾都合法,并且最后停在了“无需补税”的状态。于是他判定你的报税流程是合规的(接受)。然后他得出结论:这套税务软件所定义的“合规报税语言”是一个正则语言。
11.6. 正则运算
📜 [原文32]
在前两节中,我们介绍了有限自动机和正则语言并对其进行了定义。我们现在开始研究它们的性质。这样做将有助于开发一个用于设计自动机以识别特定语言的技术工具箱。该工具箱还将包括证明某些其他语言是非正则的(即,超出有限自动机的能力范围)的方法。
在算术中,基本对象是数字,而工具是用于操作它们的运算,例如 + 和 $\times$。在计算理论中,对象是语言,而工具包括专门用于操作它们的运算。我们定义语言上的三种运算,称为正则运算,并使用它们来研究正则语言的性质。
📖 [逐步解释]
这段话是新一节的引言,标志着学习重点的又一次转移:从设计单个自动机,转向研究正则语言这一集合家族的普适性质。
- 承前启后:
- 回顾: 我们已经定义了有限自动机(机器)和正则语言(由这些机器识别的问题)。
- 展望: 我们要开始研究正则语言的性质 (properties)。
- 阐明学习目的:
- 研究这些性质不是为了理论而理论,而是有非常实用的目的:建立一个“技术工具箱”。
- 工具箱的两个功能:
- 建设性工具: 开发更强大的设计方法。比如,如果我知道如何为语言A和语言B分别设计自动机,那么利用这些性质,我或许能“自动地”为“A或B”设计一个自动机,而无需从头思考。
- 批判性工具: 证明某些语言是非正则的。这是同样重要的能力。知道一个工具能做什么,和知道它不能做什么,同样重要。这些性质将帮助我们找到有限自动机的“阿喀琉斯之踵”,从而严格证明某些问题(如前述的 $0^n1^n$)是它无法解决的。
- 类比算术:
- 作者用了一个非常贴切的类比来解释接下来要做什么。
- 算术:
- 研究对象: 数字 (numbers)。
- 操作工具: 运算 (operations),如加法 +、乘法 ×。
- 计算理论:
- 研究对象: 语言 (languages)。
- 操作工具: 我们也需要定义一些在语言上进行的运算。
- 引出核心概念:正则运算:
- 作者明确指出,我们将要定义三种在语言上施加的运算,并给它们起了一个特殊的名字——正则运算 (Regular Operations)。
- 我们将使用这三种运算来研究正则语言的性质。这里的核心问题将是:“正则语言”这个大家族,对于这些运算是不是“封闭”的?(即,对正则语言进行正则运算,得到的结果还是不是一个正则语言?)
💡 [数值示例]
- 算术中的“封闭”概念:
- 自然数集 $\mathbb{N} = \{1, 2, 3, ...\}$。
- 它对加法是封闭的:任何两个自然数相加,结果还是自然数 (e.g., $3+5=8 \in \mathbb{N}$)。
- 它对减法是不封闭的:两个自然数相减,结果不一定是自然数 (e.g., $3-5=-2 \notin \mathbb{N}$)。
- 计算理论中的“封闭”概念(预告):
- 设 $A$ 和 $B$ 都是正则语言。
- 我们将要研究的问题是:$A \cup B$ (A和B的并集) 是不是一个正则语言?
- 如果答案是“是”,我们就说正则语言这个类 (class) 对并集运算是封闭的。
⚠️ [易错点]
- 运算的对象: 要清晰地认识到,接下来的运算(如并集、连接)的操作对象是语言(字符串的集合),而不是单个字符串或自动机本身。
📝 [总结]
本段作为新章节的开篇,阐明了接下来的研究方向:从设计和分析单个自动机,转向研究正则语言这个集合类的代数性质。通过类比算术中的数字和运算,引出了即将在语言上定义的三种正则运算,并预告了研究的核心问题——闭包性质(closure properties),这套理论将构成一个强大的“工具箱”,既能用于构造复杂的自动机,也能用于证明某些语言的非正则性。
🎯 [存在目的]
本段的目的是提升研究的抽象层次。它将我们的视角从“一个语言”和“一个自动机”的微观层面,提升到“一类语言”和“一类运算”的宏观层面。这是数学和理论科学发展的典型路径:在理解了基本对象之后,转而研究这些对象构成的集合的整体结构和性质。
[直觉心-智模型]
- 从学做菜到研究化学反应:
- 之前的部分是“学做菜”:你学会了做“番茄炒蛋”(识别奇数个1)和“可乐鸡翅”(识别含001)。
- 接下来的部分是研究“烹饪化学”:
- 对象: 食材类别(蔬菜类、肉类...)。
- 运算: “混合”(并集)、“搭配”(连接)。
- 研究性质: “蔬菜类”和“肉类”混合后,还是不是“健康食品类”?(闭包性质)。
- 研究这些性质,能让你成为一个美食家或营养学家,而不仅仅是一个厨子。你能创造新菜式,也能分析为什么有些搭配是“黑暗料理”。
💭 [直观想象]
想象你是一个乐高玩家。
- 之前,你学会了如何用乐高拼一辆“小汽车”(一个自动机)和一栋“小房子”(另一个自动机)。
- 现在,你开始思考一些更根本的问题:
- 运算: 有没有一种通用的方法,可以把任意两件拼好的作品“粘在一起”?(连接运算)
- 运算: 有没有一种方法,可以把任意一件作品“复制”任意多次,然后首尾相连?(星号运算)
- 闭包性质: 如果我只用“汽车类”的零件和“房子类”的零件,通过上述方法组合出的新东西,还是不是一个“交通工具或建筑”?
- 研究这些高层次的组合规则,就是研究正则运算。
1.1.6.1. 定义 1.23:正则运算
📜 [原文33]
定义 1.23
设 $A$ 和 $B$ 是语言。我们定义正则运算并集、连接和星号如下:
- 并集:$A \cup B=\{x \mid x \in A \text { 或 } x \in B\}$。
- 连接:$A \circ B=\{x y \mid x \in A \text { 且 } y \in B\}$。
- 星号:$A^{*}=\left\{x_{1} x_{2} \ldots x_{k} \mid k \geq 0 \text { 且每个 } x_{i} \in A\right\}$。
📖 [逐步解释]
这个定义正式引入了三种在语言上进行操作的基本运算。注意,这里的操作对象是语言(字符串的集合),操作的结果也是一个新的语言。
- 并集 (Union)
- 符号: $A \cup B$。这个符号与集合论中的并集完全相同。
- 定义: 新语言 $A \cup B$ 包含所有满足以下条件的字符串 $x$:$x$ 要么是语言 $A$ 的成员,要么是语言 $B$ 的成员。
- 直观理解: 就是把语言 $A$ 和语言 $B$ 中的所有字符串倒进一个大袋子里,得到的那个新集合就是并集。
- 例子: 如果 $A=\{\text{"apple"}, \text{"banana"}\}$,$B=\{\text{"banana"}, \text{"cherry"}\}$,那么 $A \cup B = \{\text{"apple"}, \text{"banana"}, \text{"cherry"}\}$。(注意集合元素不重复)
- 连接 (Concatenation)
- 符号: $A \circ B$。有时为了简洁,也会直接写成 $AB$。
- 定义: 新语言 $A \circ B$ 包含所有形如 $xy$ 的字符串,其中 $x$ 必须是语言 $A$ 中的一个字符串,而 $y$ 必须是语言 $B$ 中的一个字符串。
- 直观理解: 从语言 $A$ 中任选一个字符串,再从语言 $B$ 中任选一个字符串,然后把它们前后拼接起来。所有可能的拼接结果,构成了连接语言。
- 字符串连接: 这里的 $xy$ 表示字符串的拼接。如果 $x=\text{"ab"}$,$y=\text{"cde"}$,那么 $xy = \text{"abcde"}$。
- 注意: 字符串的连接不满足交换律,即 $xy \neq yx$。因此,语言的连接运算通常也不满足交换律,即 $A \circ B \neq B \circ A$。
- 星号 (Star)
- 符号: $A^*$。也称为克林闭包 (Kleene Star / Kleene Closure),以数学家斯蒂芬·克林命名。
- 定义: 这是三种运算中最复杂的一个。新语言 $A^*$ 包含所有通过“从语言 $A$ 中取出任意 $k$ 个字符串($k$ 可以是0),然后按任意顺序拼接起来”所能得到的所有字符串。
- 拆解定义:
- $x_1, x_2, ..., x_k$: 每一个 $x_i$ 都是语言 $A$ 中的一个成员。允许重复选取,比如 $x_1$ 和 $x_2$ 可以是 $A$ 中的同一个字符串。
- $k \ge 0$: 这是一个至关重要的条件,表示我们可以选取的字符串的数量 $k$ 可以是0,1,2,...,任意非负整数。
- 当 $k=0$ 时: 我们从 $A$ 中选取0个字符串进行拼接。在形式语言理论中,0个字符串的拼接结果被定义为空串 $\varepsilon$。
- 结论: 任何语言 $A$ 的星号运算 $A^*$ 中,都必然包含空串 $\varepsilon$。
- 直观理解: $A^*$ 就是由 $A$ 中的“基本积木块”通过任意次数的拼接(包括零次)所能构成的一切。
- $A^* = \{\varepsilon\} \cup A \cup (A \circ A) \cup (A \circ A \circ A) \cup \dots$
⚠️ [易错点]
- 连接 vs. 笛卡尔积: $A \circ B$ (连接) 和 $A \times B$ (笛卡尔积) 是完全不同的。
- $A \circ B$ 的元素是字符串。
- $A \times B$ 的元素是有序对。
- 例如,设 $A=\{\text{"a"}\}, B=\{\text{"b"}\}$。$A \circ B = \{\text{"ab"}\}$。而 $A \times B = \{(\text{"a"}, \text{"b"})\}$。
- 星号运算与空串: 永远不要忘记 $\varepsilon$ 总是 $A^*$ 的成员。即使 $A$ 本身是空语言 $\emptyset$,$A^* = \emptyset^*$ 仍然是 $\{\varepsilon\}$,而不是 $\emptyset$。因为可以从 $\emptyset$ 中取0个字符串来拼接,得到 $\varepsilon$。
- 星号运算与空串语言: 如果 $A = \{\varepsilon\}$,那么 $A^* = \{\varepsilon\}^* = \{\varepsilon, \varepsilon\varepsilon, \varepsilon\varepsilon\varepsilon, ...\} = \{\varepsilon\}$。
📝 [总结]
定义1.23 形式化地定义了三种在语言上进行操作的正则运算:
- 并集 ($\cup$): 合并两个语言。
- 连接 ($\circ$): 将一个语言的串拼在另一个语言的串前面。
- 星号 ($*$): 将一个语言的串进行任意次数(包括0次)的自我拼接。
🎯 [存在目的]
本定义的目的是为形式语言理论提供一套基本的“代数工具”。就像 + 和 × 是构建所有算术表达式的基础一样,这三种正则运算将成为构建所有正则表达式的基础。后续的理论将证明,由有限自动机识别的正则语言类,对这三种运算是封闭的,这是正则语言理论中最核心的结论之一。
🧠 [直觉心智模型]
- 乐高积木:
- 语言 A, B: 两盒不同主题的乐高积木块。A是“车轮”盒,B是“窗户”盒。
- 并集 ($A \cup B$): 把两盒积木倒在一起。新盒子里的积木要么是车轮,要么是窗户。
- 连接 ($A \circ B$): 从A盒拿一个车轮,从B盒拿一个窗户,把窗户粘在车轮上。所有可能的“轮上窗”组合。
- 星号 ($A^*$): 只给你“车轮”盒。你可以不拿(得到一个空作品 $\varepsilon$),或拿一个车轮,或拿两个车轮粘在一起,或拿三个... 你用“车轮”能拼出来的所有东西(比如一条履带)。
💭 [直观想象]
想象你在用两种颜料进行创作。
- 语言 A: {红色}
- 语言 B: {蓝色}
- 并集: 你的调色板上有 {红色, 蓝色}。
- 连接: 你先画一笔红色,紧接着画一笔蓝色,得到一个“红蓝”色的笔触。{红蓝}。
- 星号: 只用红色。你可以不画(白纸,$\varepsilon$),画一笔红,画两笔红,画三笔红...得到所有由纯红色笔触构成的图案。
1.1.6.2. 例子 1.24
📜 [原文34]
例子 1.24
设字母表 $\Sigma$ 是标准 26 个字母 $\{\mathrm{a}, \mathrm{b}, \ldots, \mathrm{z}\}$。如果 $A=\{\operatorname{good}, \mathrm{bad}\}$ 且 $B=\{$ boy, girl $\}$,那么
$$
\begin{aligned}
A \cup B= & \text { \{good, bad, boy, girl\} } \\
A \circ B= & \text { \{goodboy, goodgirl, badboy, badgirl\}, 以及 } \\
A^{*}= & \{\varepsilon, \text { good, bad, goodgood, goodbad, badgood, badbad, } \\
& \text { goodgoodgood, goodgoodbad, goodbadgood, goodbadbad, } \ldots\} 。
\end{aligned}
$$
📖 [逐步解释]
这个例子为定义1.23中抽象的正则运算提供了具体、易于理解的实例。
- 前提:
- 语言 A: 包含两个字符串 "good" 和 "bad"。 $A = \{\text{good}, \text{bad}\}$。
- 语言 B: 包含两个字符串 "boy" 和 "girl"。 $B = \{\text{boy}, \text{girl}\}$。
- 并集 (Union) $A \cup B$:
- 计算: 将语言 A 和语言 B 的所有成员合并到一个集合中,并去除重复项(本例无重复)。
- 结果: $\{\text{good}, \text{bad}\} \cup \{\text{boy}, \text{girl}\} = \{\text{good}, \text{bad}, \text{boy}, \text{girl}\}$。
- 连接 (Concatenation) $A \circ B$:
- 计算: 从 A 中取一个串,从 B 中取一个串,然后拼接起来。我们需要遍历所有可能的组合。
- 组合:
- 从 A 取 "good", 从 B 取 "boy" $\rightarrow$ "goodboy"
- 从 A 取 "good", 从 B 取 "girl" $\rightarrow$ "goodgirl"
- 从 A 取 "bad", 从 B 取 "boy" $\rightarrow$ "badboy"
- 从 A 取 "bad", 从 B 取 "girl" $\rightarrow$ "badgirl"
- 结果: $A \circ B = \{\text{goodboy}, \text{goodgirl}, \text{badboy}, \text{badgirl}\}$。
- 星号 (Star) $A^*$:
- 计算: 从语言 A 中任意选取0次、1次、2次、... 并拼接。
- k=0: 选取0 个串拼接,得到空串 $\varepsilon$。
- k=1: 选取 1 个串,得到 A 本身:$\{\text{good}, \text{bad}\}$。
- k=2: 选取 2 个串进行拼接 ($A \circ A$)。所有可能的组合:
- "good" + "good" $\rightarrow$ "goodgood"
- "good" + "bad" $\rightarrow$ "goodbad"
- "bad" + "good" $\rightarrow$ "badgood"
- "bad" + "bad" $\rightarrow$ "badbad"
- k=3: 选取 3 个串进行拼接 ($A \circ A \circ A$)。例如 "goodgoodgood", "goodgoodbad", "goodbadgood" 等等。
- ... 以此类推,可以无限进行下去。
- 结果: $A^*$ 是一个无限语言,它包含了所有由 "good" 和 "bad" 这两个“积木块”拼接而成的串,再加上一个空串 $\varepsilon$。原文只列举了k=0, 1, 2 的情况和k=3的一部分。
💡 [数值示例]
- 示例1(原文示例): 已详细解释。
- 示例2: 设 $L_1 = \{ \text{"a"}, \text{"b"} \}$, $L_2 = \{ \text{"1"}, \text{"2"} \}$
- 并集: $L_1 \cup L_2 = \{ \text{"a"}, \text{"b"}, \text{"1"}, \text{"2"} \}$
- 连接: $L_1 \circ L_2 = \{ \text{"a1"}, \text{"a2"}, \text{"b1"}, \text{"b2"} \}$
- 星号: $L_1^* = \{ \varepsilon, \text{"a"}, \text{"b"}, \text{"aa"}, \text{"ab"}, \text{"ba"}, \text{"bb"}, \text{"aaa"}, \dots \}$ (所有由 a, b 组成的串,包括空串)。
⚠️ [易错点]
- 连接的顺序: $A \circ B$ 和 $B \circ A$ 是不同的。
- $A \circ B = \{\text{goodboy}, \text{goodgirl}, \text{badboy}, \text{badgirl}\}$。
- $B \circ A = \{\text{boygood}, \text{girlgood}, \text{boybad}, \text{girlbad}\}$。
- 显然 $A \circ B \neq B \circ A$。
- 星号运算的无限性: 除非 $A = \{\varepsilon\}$ 或 $A = \emptyset$,否则如果 $A$ 包含任何非空字符串,则 $A^*$ 一定是一个无限语言。
📝 [总结]
例子1.24用两个简单的、包含英文单词的语言 A 和 B,具体地演算了并集、连接和星号这三种正则运算的结果,使得这些抽象的定义变得直观和易于理解。
🎯 [存在目的]
本例子的目的是巩固读者对定义1.23的理解。通过具体的单词拼接,读者可以清晰地看到每种运算是如何产生新语言的,特别是连接的组合性和星号的递归、无限的特性。这是在进行理论证明之前必不可少的、建立直觉的一步。
🧠 [直觉心智模型]
- 点菜:
- 语言A (主食): {米饭, 面条}
- 语言B (菜): {宫保鸡丁, 鱼香肉丝}
- 并集 $A \cup B$: 你可以点的所有单品:{米饭, 面条, 宫保鸡丁, 鱼香肉丝}。
- 连接 $A \circ B$: 套餐组合(主食+菜):{米饭宫保鸡丁, 米饭鱼香肉丝, 面条宫保鸡丁, 面条鱼香肉丝}。
- 星号 $A^*$: “主食自助”。你可以不吃($\varepsilon$),或只吃一碗米饭,或吃一碗米饭加一碗面条,或吃两碗米饭...
💭 [直观想象]
想象你有两套字母印章。
- A套: {g,o,o,d} 和 {b,a,d} 两个连体印章。
- B套: {b,o,y} 和 {g,i,r,l} 两个连体印章。
- 并集: 把四块印章都放在桌上。
- 连接: 先从A套里拿一块印章(如 good),再从B套里拿一块(如 boy),紧挨着盖在纸上,得到 goodboy。
- 星号: 只用A套的两块印章。你可以在纸上不盖($\varepsilon$),或者只盖一个 good,或者盖一个 good 后面再盖一个 bad,... 随意组合盖章。
1.1.6.3. 闭包性质
📜 [原文35]
设 $\mathcal{N}=\{1,2,3, \ldots\}$ 为自然数集。当我们说 $\mathcal{N}$ 在乘法下是封闭的,我们的意思是对于 $\mathcal{N}$ 中的任意 $x$ 和 $y$,乘积 $x \times y$ 也在 $\mathcal{N}$ 中。相比之下,$\mathcal{N}$ 在除法下不是封闭的,因为 1 和 2 在 $\mathcal{N}$ 中,但 $1 / 2$ 不在。一般来说,如果对集合的成员应用某种运算后,结果仍然是该集合中的对象,则称该集合在该运算下封闭。我们证明正则语言集合在所有三种正则运算下都是封闭的。在第 1.3 节中,我们展示了这些是操作正则语言和理解有限自动机能力的有用工具。我们从并集运算开始。
📖 [逐步解释]
这段话正式引入了闭包性质 (Closure Property) 这个核心的数学概念,并宣告了本节后续的主要任务:证明正则语言对三种正则运算都是封闭的。
- 通过类比解释“闭包”:
- 作者没有直接给闭包下定义,而是从一个我们熟悉的例子——自然数集 $\mathcal{N}$ ——入手。
- 封闭的例子: 乘法。从 $\mathcal{N}$ 中任取两个数(如 3 和 5),它们的乘积 15 仍然在 $\mathcal{N}$ 中。这个规律对所有自然数都成立。所以我们说“自然数集对乘法是封闭的”。
- 不封闭的例子: 除法。从 $\mathcal{N}$ 中取两个数 1 和 2,它们的商 $1/2$ 不在 $\mathcal{N}$ 中。我们找到了一个“反例”,所以我们说“自然数集对除法是不封闭的”。
- 给出“闭包”的通用定义:
- 集合 S 在运算 op 下是封闭的,意思是:从 S 中取出元素,用运算 op 对它们进行操作,得到的结果仍然是 S 中的元素。
- 直观理解: 在一个“封闭”的集合里做运算,你永远“逃不出去”,总是在这个集合内部打转。
- 宣告核心定理:
- 作者在这里直接给出了本节最重要的结论:“正则语言集合在所有三种正则运算下都是封闭的。”
- 这意味着:
- 一个正则语言 $\cup$ 一个正则语言 $\rightarrow$ 结果还是一个正则语言。
- 一个正则语言 $\circ$ 一个正则语言 $\rightarrow$ 结果还是一个正则语言。
- 一个正则语言的 $*$ $\rightarrow$ 结果还是一个正则语言。
- 这是一个非常强大的结论,我们将在后面逐一证明它。
- 预告应用价值:
- 证明这些闭包性质有什么用?作者指出,它们是操作正则语言和理解有限自动机能力的有用工具。这呼应了本节开头的“技术工具箱”的比喻。
- 开始证明:
- 最后,作者宣布将从最简单的并集运算开始,着手证明第一个闭包性质。
💡 [数值示例]
- 示例1: 整数集 $\mathbb{Z}$
- $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$。
- 对加法封闭吗?是 ($(-2)+5=3 \in \mathbb{Z}$)。
- 对减法封闭吗?是 ($3-5=-2 \in \mathbb{Z}$)。
- 对乘法封闭吗?是 ($(-2) \times 3 = -6 \in \mathbb{Z}$)。
- 对除法封闭吗?否 ($1 \div 2 = 0.5 \notin \mathbb{Z}$)。
- 示例2: 语言的闭包(直观感受)
- 设 $A$ = {所有以a结尾的串} (我们知道这是正则的)。
- 设 $B$ = {所有以b结尾的串} (同理,也是正则的)。
- $A \cup B$ = {所有以a或b结尾的串}。直觉上,这似乎也是一个可以用有限自动机解决的问题,所以它可能是正则的。
- $A \circ B$ = { (某个以a结尾的串) + (某个以b结尾的串) }。这个新语言的结构变复杂了。它是否还是正则的?不那么直观了,需要严格证明。
⚠️ [易错点]
- 证明的必要性: 不能仅凭直觉判断一个集合是否封闭。比如,对于 $A \circ B$ 的例子,我们可能会觉得“拼接”操作很复杂,也许会导致结果不再是正则的。只有通过严格的构造性证明(即,展示一个能识别结果语言的有限自动机),我们才能确信它是封闭的。
- 证明的思路: 证明“正则语言对某运算是封闭的”,其标准套路是:
- 假设参与运算的语言(如 $A_1, A_2$)是正则的。
- 根据正则语言的定义,这意味着存在有限自动机 $M_1, M_2$ 分别识别它们。
- 利用 $M_1, M_2$ 作为“零件”,构造一个新的有限自动机 $M$。
- 证明这个新的 $M$ 识别的语言恰好是 $A_1$ 和 $A_2$ 运算后的结果语言。
- 因为我们成功构造出了这样一个有限自动机,所以结果语言根据定义也是正则的。证明完毕。
📝 [总结]
本段用自然数的例子通俗地解释了数学中“闭包性质”的概念,并明确提出了接下来要证明的核心定理:正则语言这个大家族,对于并集、连接和星号这三种正则运算是封闭的。这为后续的理论证明设定了清晰的目标。
🎯 [存在目的]
本段的目的是引入“闭包”这个在代数结构研究中至关重要的概念。通过建立“正则语言”与“正则运算”之间的这种稳定关系,我们可以将正则语言视为一个具有良好代数结构的集合。这使得我们可以用模块化、组合化的方式来分析和构建语言及自动机,极大地增强了理论的威力。
🧠 [直觉心智模型]
- “纯种狗”的繁育:
- 正则语言: “纯种狗”这个集合。
- 运算: “繁育”操作。
- 闭包性质: 如果“纯种狗A”和“纯种狗B”繁育出的后代,保证仍然是“纯种狗”,那么“纯种狗”这个集合对于“繁育”运算就是封闭的。
- 如果和“非纯种狗”繁育,后代就不是纯种了,这就不封闭。
💭 [直观想象]
想象一个“会员专用”的加工坊。
- 正则语言: 会员(特指某种特定类型的原料)。
- 正则运算: 加工坊里的机器(搅拌机、拼接机、复制机)。
- 闭包性质: 这个加工坊的规定是,机器的输入必须是“会员原料”,并且经过机器加工出来的成品,也必须有资格成为“会员原料”。即,这个体系是自给自足、内部循环的。
- 我们的任务就是去证明,正则语言这个“会员俱乐部”和正则运算这些“机器”,确实构成了这样一个封闭的体系。
1.1.6.4. 定理 1.25:并集闭包性
📜 [原文36]
定理 1.25
正则语言的类在并集运算下是封闭的。
换句话-说,如果 $A_{1}$ 和 $A_{2}$ 是正则语言,那么 $A_{1} \cup A_{2}$ 也是正则语言。
证明思路 我们有正则语言 $A_{1}$ 和 $A_{2}$,并希望证明 $A_{1} \cup A_{2}$ 也是正则语言。因为 $A_{1}$ 和 $A_{2}$ 是正则语言,我们知道某个有限自动机 $M_{1}$ 识别 $A_{1}$,某个有限自动机 $M_{2}$ 识别 $A_{2}$。为了证明 $A_{1} \cup A_{2}$ 是正则语言,我们演示一个有限自动机,称之为 $M$,它识别 $A_{1} \cup A_{2}$。
这是一个构造性证明。我们从 $M_{1}$ 和 $M_{2}$ 构造 $M$。机器 $M$ 必须恰好在 $M_{1}$ 或 $M_{2}$ 接受其输入时接受其输入,以便识别并集语言。它通过模拟 $M_{1}$ 和 $M_{2}$ 并在其中任何一个模拟接受时接受来工作。
我们如何使机器 $M$ 模拟 $M_{1}$ 和 $M_{2}$ 呢?也许它首先在输入上模拟 $M_{1}$,然后模拟 $M_{2}$。但我们在这里必须小心!一旦输入符号被读取并用于模拟 $M_{1}$,我们就无法“回带输入磁带”来尝试在 $M_{2}$ 上进行模拟。我们需要另一种方法。
假装您是 $M$。当输入符号逐个到达时,您同时模拟 $M_{1}$ 和 $M_{2}$。这样,只需要对输入进行一次遍历。但是您能用有限的内存同时跟踪两个模拟吗?您只需要记住每台机器在读取到这一点时所处的状态。因此,您需要记住一个状态对。有多少种可能的状态对?如果 $M_{1}$ 有 $k_{1}$ 个状态,而 $M_{2}$ 有 $k_{2}$ 个状态,则状态对(一个来自 $M_{1}$,另一个来自 $M_{2}$)的数量是乘积 $k_{1} \times k_{2}$。这个乘积将是 $M$ 中的状态数量,每个状态对对应一个状态。$M$ 的转移从状态对到状态对,更新 $M_{1}$ 和 $M_{2}$ 的当前状态。$M$ 的接受状态是那些状态对,其中 $M_{1}$ 或 $M_{2}$ 处于接受状态。
📖 [逐步解释]
这部分首先陈述了关于并集闭包的定理,然后给出了一个非常详细、循循善诱的“证明思路”。这个思路比形式化的证明本身更重要,因为它揭示了构造方法背后的思考过程。
- 定理陈述:
- 定理1.25: 正则语言类对并集运算是封闭的。
- 换句话说: 如果你有两个正则语言 $A_1$ 和 $A_2$,那么它们的并集 $A_1 \cup A_2$ 也必然是一个正则语言。
- 证明的大方向:
- 起点: 假设 $A_1, A_2$ 是正则语言。
- 利用定义: 这意味着,存在有限自动机 $M_1$ 识别 $A_1$,以及有限自动机 $M_2$ 识别 $A_2$。
- 目标: 证明 $A_1 \cup A_2$ 是正则语言。
- 达成目标的方法: 我们必须构造一个新的有限自动机 $M$,并证明 $L(M) = A_1 \cup A_2$。这种通过直接造出一个实例来证明其存在性的方法,称为构造性证明 (Proof by Construction)。
- 构思新自动机 $M$ 的功能:
- $M$ 的任务是识别 $A_1 \cup A_2$。这意味着,对于一个输入串 $w$:
- 如果 $w \in A_1$ 或 $w \in A_2$,那么 $M$ 必须接受 $w$。
- 换句话说,如果 $M_1$ 接受 $w$ 或 $M_2$ 接受 $w$,那么 $M$ 必须接受 $w$。
- 核心思想: $M$ 的工作方式应该是去模拟 $M_1$ 和 $M_2$ 的运行。
- 探索模拟方法 (并排除错误方法):
- 错误想法: 先用 $w$ 跑一遍 $M_1$,然后再用 $w$ 跑一遍 $M_2$。
- 为什么错误: 有限自动机的模型是一次性的、从左到右的读取。它没有能力“回带输入磁带”来重新读取输入。一旦一个符号被读过,它就永远过去了。
- 提出正确方法:并行模拟 (Parallel Simulation):
- 核心技巧: 既然不能先后模拟,那就“同时”模拟。
- 角色扮演: 假装你是新机器 $M$。当一个输入符号进来时,你同时思考:
- “如果我是 $M_1$,我现在会走到哪个状态?”
- “如果我是 $M_2$,我现在会走到哪个状态?”
- 内存需求: 为了进行这种并行模拟,在每一步,你需要记住两个信息:$M_1$ 当前的状态,以及 $M_2$ 当前的状态。
- 用状态编码记忆: 这种“成对的记忆”可以用 $M$ 的一个状态来表示。$M$ 的每一个状态,实际上是一个状态对 (pair of states),形如 $(r_1, r_2)$,其中 $r_1$ 是 $M_1$ 的一个状态,$r_2$ 是 $M_2$ 的一个状态。
- 构造 $M$ 的细节:
- $M$ 的状态集: 是 $M_1$ 状态集和 $M_2$ 状态集的笛卡尔积。如果 $M_1$ 有 $k_1$ 个状态,$M_2$ 有 $k_2$ 个状态,那么 $M$ 将有 $k_1 \times k_2$ 个状态。
- $M$ 的转移: $M$ 的转移就是并行地更新这个状态对。如果 $M$ 当前在状态 $(r_1, r_2)$,读入符号 $a$,那么 $M_1$ 会从 $r_1$ 走到 $\delta_1(r_1, a)$,$M_2$ 会从 $r_2$ 走到 $\delta_2(r_2, a)$。所以,$M$ 的下一个状态就是 $(\delta_1(r_1, a), \delta_2(r_2, a))$。
- $M$ 的起始状态: $M_1$ 从 $q_1$ 开始,$M_2$ 从 $q_2$ 开始。所以 $M$ 的起始状态就是状态对 $(q_1, q_2)$。
- $M$ 的接受状态: $M$ 应该在 $M_1$ 接受 或 $M_2$ 接受时接受。因此,$M$ 的接受状态是所有满足“其第一个分量是 $M_1$ 的接受状态,或其第二个分量是 $M_2$ 的接受状态”的状态对。
💡 [数值示例]
- 示例:
- $M_1$: 识别以a结尾的语言。$Q_1=\{s_1, s_a\}$, $q_1=s_1$, $F_1=\{s_a\}$。
- $M_2$: 识别以b结尾的语言。$Q_2=\{t_1, t_b\}$, $q_2=t_1$, $F_2=\{t_b\}$。
- 构造 $M$:
- $M$ 的状态: $Q = Q_1 \times Q_2 = \{(s_1, t_1), (s_1, t_b), (s_a, t_1), (s_a, t_b)\}$。共 $2 \times 2 = 4$ 个状态。
- $M$ 的起始状态: $(s_1, t_1)$。
- $M$ 的转移: 以状态 $(s_1, t_1)$ 读入 a 为例:
- $M_1$ 中: $\delta_1(s_1, a) = s_a$。
- $M_2$ 中: $\delta_2(t_1, a) = t_1$。
- 所以 $M$ 中: $\delta((s_1, t_1), a) = (s_a, t_1)$。
- $M$ 的接受状态: 所有第一个分量是 $s_a$ 或 第二个分量是 $t_b$ 的状态对。
- $F = \{(s_a, t_1), (s_a, t_b), (s_1, t_b)\}$。注意 $(s_1,t_1)$不是,$(s_a,t_b)$是的。
- 这个新构造的自动机 $M$ 将会识别所有以a或以b结尾的语言。
⚠️ [易错点]
- 忘记笛卡尔积: 构造的关键是想到用状态的笛卡尔积来模拟并行计算。这是有限自动机理论中一个非常经典和重要的技巧。
- 接受状态的逻辑: $M$ 的接受状态是 $F_1 \times Q_2$ 和 $Q_1 \times F_2$ 的并集,而不是 $F_1 \times F_2$。如果是后者,那么机器将识别 $A_1 \cap A_2$(交集),而不是 $A_1 \cup A_2$(并集)。
📝 [总结]
“证明思路”部分通过一个精彩的思维过程,为证明定理1.25提供了蓝图。它排除了“顺序模拟”的错误想法,提出了“并行模拟”的正确思路,并最终将此思路转化为一个具体的自动机构造方案:新自动机的状态是原自动机状态的笛卡尔积,以此来同步追踪两台原自动机的运行轨迹,并通过设置合适的接受状态来识别其语言的并集。
🎯 [存在目的]
“证明思路”比冷冰冰的形式化证明本身更具教学价值。它向读者展示了数学家和理论家是如何思考问题的:如何将一个目标(证明并集闭包)分解,如何提出可能的解决方案,如何评估方案的可行性,以及如何最终敲定一个优雅且正确的构造方法。这是对创造性问题解决过程的精彩解剖。
🧠 [直觉心智模型]
- 两人三足赛跑:
- $M_1$ 和 $M_2$: 两个独立的跑步者。
- 新机器 $M$: 把这两个人绑在一起玩“两人三足”。
- $M$ 的状态: 是一个状态对 (A的位置, B的位置)。
- $M$ 的转移: 裁判喊“预备,跑!”(输入),A和B同时迈出一步, (A的位置, B的位置) 更新为 (A的新位置, B的新位置)。
- $M$ 的接受状态: 只要A或B中任何一个人到达了终点,就算整个“两人三足”组合获胜。
💭 [直观想象]
想象你在同时观看两场不同的足球比赛,$M_1$ 和 $M_2$。
- 你的大脑有限,但你可以做到“同时追踪两场比赛的比分”。
- 你的“状态”: 就是一个比分牌 (M1的比分, M2的比分)。
- 输入: 时间流逝,两场比赛中可能都有进球。
- 你的状态转移: 每隔几分钟,你就更新一下你的比分牌。
- 接受状态: 你的目标是“只要有一场比赛分出胜负就算完”。所以,任何形如 (M1胜, M2进行中) 或 (M1进行中, M2胜) 或 (M1胜, M2胜) 的比分牌,都是你的“接受状态”。
1.1.6.5. 定理 1.25 的形式化证明
📜 [原文37]
证明
设 $M_{1}$ 识别 $A_{1}$,其中 $M_{1}=\left(Q_{1}, \Sigma, \delta_{1}, q_{1}, F_{1}\right)$,设 $M_{2}$ 识别 $A_{2}$,其中 $M_{2}=\left(Q_{2}, \Sigma, \delta_{2}, q_{2}, F_{2}\right)$。
构造 $M$ 以识别 $A_{1} \cup A_{2}$,其中 $M=\left(Q, \Sigma, \delta, q_{0}, F\right)$。
- $Q=\left\{\left(r_{1}, r_{2}\right) \mid r_{1} \in Q_{1} \text { 且 } r_{2} \in Q_{2}\right\}$。
这个集合是集合 $Q_{1}$ 和 $Q_{2}$ 的笛卡尔积,写为 $Q_{1} \times Q_{2}$。它是所有状态对的集合,第一个来自 $Q_{1}$,第二个来自 $Q_{2}$。
- $\Sigma$,字母表,与 $M_{1}$ 和 $M_{2}$ 中的相同。在这个定理和所有后续的类似定理中,为简单起见,我们假设 $M_{1}$ 和 $M_{2}$ 都具有相同的输入字母表 $\Sigma$。如果它们具有不同的字母表 $\Sigma_{1}$ 和 $\Sigma_{2}$,该定理仍然成立。那么我们将修改证明,使 $\Sigma=\Sigma_{1} \cup \Sigma_{2}$。
- $\delta$,转移函数,定义如下。对于每个 $\left(r_{1}, r_{2}\right) \in Q$ 和每个 $a \in \Sigma$,设
$$
\delta\left(\left(r_{1}, r_{2}\right), a\right)=\left(\delta_{1}\left(r_{1}, a\right), \delta_{2}\left(r_{2}, a\right)\right) 。
$$
因此,$\delta$ 获取 $M$ 的一个状态(实际上是来自 $M_{1}$ 和 $M_{2}$ 的状态对),以及一个输入符号,并返回 $M$ 的下一个状态。
- $q_{0}$ 是状态对 $\left(q_{1}, q_{2}\right)$。
- $F$ 是状态对的集合,其中任何一个成员是 $M_{1}$ 或 $M_{2}$ 的接受状态。我们可以将其写为
$$
F=\left\{\left(r_{1}, r_{2}\right) \mid r_{1} \in F_{1} \text { 或 } r_{2} \in F_{2}\right\} 。
$$
这个表达式与 $F=\left(F_{1} \times Q_{2}\right) \cup\left(Q_{1} \times F_{2}\right)$ 相同。(请注意,它与 $F=F_{1} \times F_{2}$ 不同。那会给我们什么呢? ${ }^{3}$)
[^1]这结束了有限自动机 $M$ 的构造,它识别 $A_{1}$ 和 $A_{2}$ 的并集。这种构造相当简单,因此其正确性从证明思路中描述的策略显而易见。更复杂的构造需要额外的讨论来证明正确性。这种类型的构造的形式化正确性证明通常通过归纳法进行。有关证明正确的构造的例子,请参见定理 1.54的证明。您在本课程中遇到的大多数构造都相当简单,因此不需要形式化正确性证明。
📖 [逐步解释]
这部分是将上一节的“证明思路”翻译成严格的形式化数学语言。它遵循标准的构造性证明格式。
1. 准备阶段 (Setup)
- 前提: 设 $A_1, A_2$ 是正则语言。
- 展开定义: 这意味着存在有限自动机 $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ 识别 $A_1$,和 $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ 识别 $A_2$。
2. 构造阶段 (Construction)
- 目标: 构造一个新自动机 $M = (Q, \Sigma, \delta, q_0, F)$,使其能识别 $A_1 \cup A_2$。
- 构造 M 的五元组:
- $Q$ (状态集): 定义为 $Q_1 \times Q_2$,即所有可能的状态对 $(r_1, r_2)$ 的集合,其中 $r_1 \in Q_1, r_2 \in Q_2$。这实现了“并行记忆”。
- $\Sigma$ (字母表): 假设 $M_1, M_2$ 的字母表相同。作者补充说明,即使不同,取其并集 $\Sigma_1 \cup \Sigma_2$ 即可,不影响结论。
- $\delta$ (转移函数): 定义 $M$ 的转移为并行执行 $M_1$ 和 $M_2$ 的转移。对于 $M$ 的任意一个状态 $(r_1, r_2)$ 和任意输入 $a$,下一个状态被定义为 $(\delta_1(r_1, a), \delta_2(r_2, a))$。
- $q_0$ (起始状态): $M_1$ 从 $q_1$ 开始,$M_2$ 从 $q_2$ 开始。因此 $M$ 的起始状态是这对状态对 $(q_1, q_2)$。
- $F$ (接受状态集): 为了识别并集,只要其中一个模拟成功就算成功。所以,$F$ 定义为所有满足“第一个分量在 $F_1$ 中 或 第二个分量在 $F_2$ 中”的状态对 $(r_1, r_2)$ 的集合。
3. 对 F 的进一步解释
- 集合语言: $F = \{(r_1, r_2) \mid r_1 \in F_1 \text{ 或 } r_2 \in F_2\}$。
- 等价的集合运算: 这个集合等于 $(F_1 \times Q_2) \cup (Q_1 \times F_2)$。
- $F_1 \times Q_2$: 所有第一个分量是 $M_1$ 的接受状态的状态对 (不管 $M_2$ 在什么状态)。
- $Q_1 \times F_2$: 所有第二个分量是 $M_2$ 的接受状态的状态对 (不管 $M_1$ 在什么状态)。
- 它们的并集,正好就是“其中一个分量是接受状态”的状态对集合。
- 对比思考题: 作者提出了一个问题:“如果 $F = F_1 \times F_2$ 会怎样?”
- 答案: $F_1 \times F_2$ 要求状态对的第一个分量必须在 $F_1$ 中,并且第二个分量必须在 $F_2$ 中。这意味着 $M$ 只有在 $M_1$ 和 $M_2$ 同时接受输入时才接受。因此,这样的机器将识别的是语言的交集 $A_1 \cap A_2$。
4. 证明的总结
- 作者指出,到此,构造已经完成。由于构造的逻辑与“证明思路”中的直观策略完全对应,其正确性是显而易见的,因此省略了更繁琐的、通过数学归纳法进行的形式化正确性证明。
💡 [数值示例]
- 并集构造: 在上一节“证明思路”中给出的“以a结尾”和“以b结尾”的语言的自动机构造,就是这个形式化证明的一个具体实例。
- 交集构造: 同样使用上一节的 $M_1$ 和 $M_2$。如果要构造一个识别 $A_1 \cap A_2$ (以a结尾且以b结尾,这是不可能的,所以是空语言,除非a=b) 的自动机,我们只需要改变第五步:
- $F_{new} = F_1 \times F_2 = \{s_a\} \times \{t_b\} = \{(s_a, t_b)\}$。
- 这个新的自动机的接受状态只有一个:$(s_a, t_b)$。
- 可以验证,没有任何输入串(除了空串,如果a=b的话)能让自动机同时结束在 $s_a$ 和 $t_b$。例如,一个串以a结尾,那么它在$M_2$中的状态必然是 $t_1$ 而不是 $t_b$。所以这个构造出的自动机的接受状态是不可达的,它识别空语言,这正好是 $A_1 \cap A_2$ 的结果。这说明,通过改变 $F$ 的定义,这个笛卡尔积构造法同样可以用来证明正则语言对交集也是封闭的。
⚠️ [易错点]
- 证明的完备性: 虽然作者说“正确性是显而易见的”,但在非常严格的数学语境下,是需要用数学归纳法对输入串的长度进行归纳,来证明“对于任意长度为n的串w,M运行w后到达状态$(r_1, r_2)$,当且仅当$M_1$运行w后到达$r_1$且$M_2$运行w后到达$r_2$”。本书为了教学目的,省略了这一步。
📝 [总结]
本段给出了定理1.25的一个完整的构造性证明。它严格按照五元组的定义,利用 $M_1$ 和 $M_2$ 的组件,构造出了一个新的有限自动机 $M$。通过定义 $M$ 的状态为状态对的笛卡尔积,并巧妙地定义了其转移函数和接受状态集,使得 $M$ 能够完美地模拟 $M_1$ 和 $M_2$ 的并行运行,并识别它们语言的并集。
🎯 [存在目的]
本段的目的是展示一个标准的、完整的构造性证明是什么样的。它将“证明思路”中的直觉和策略,转化为严谨、无歧义的数学步骤。这是计算理论中最重要的技能之一。通过学习和理解这个证明,读者不仅知道了“正则语言对并集是封闭的”这个结论,更重要的是学会了如何去证明这类结论。
🧠 [直觉心智模型]
- 雇佣一个“复合型”员工:
- $M_1$: 一个只懂前端的程序员。
- $M_2$: 一个只懂后端的程序员。
- $M$: 你把他们俩都招进来,组成一个小组。这个小组的“状态”就是 (前端的进度, 后端的进度)。
- $M$ 的转移: 项目经理(输入)提出一个新需求,前端和后端同时开工,更新各自的进度。
- $M$ 的接受: 老板说,“只要前端或后端任何一边完成了他们的模块,这个阶段就算成功”。
- 这个小组作为一个整体,就是一个新的“自动机”,它的能力是原来两个程序员能力的并集。
💭 [直观想象]
想象有两部独立的电影 $M_1$ 和 $M_2$。你想把它们“合并”成一部新的体验 $M$。
- 你租了一个可以同时放两部电影的特殊影院。
- $M$ 的状态: 就是一个对 (M1的当前画面, M2的当前画面)。
- $M$ 的转移: 时间(输入)流逝,两部电影同时播放,画面对 不断更新。
- $M$ 的接受状态: 你定义了一个规则:“只要任何一部电影出现了‘剧终’画面,就算我看完了”。
- 这个特殊的观影体验 $M$,其“结束”条件就是 $M_1$ 或 $M_2$ 的“结束”。
1.1.6.6. 定理 1.26:连接闭包性
📜 [原文38]
我们刚刚展示了两个正则语言的并集是正则语言,从而证明了正则语言的类在并集运算下是封闭的。我们现在转向连接运算,并尝试证明正则语言的类在该运算下也是封闭的。
定理 1.26
正则语言的类在连接运算下是封闭的。
换句话说,如果 $A_{1}$ 和 $A_{2}$ 是正则语言,那么 $A_{1} \circ A_{2}$ 也是正则语言。
为了证明这个定理,让我们尝试一些类似于并集情况的证明。像以前一样,我们可以从识别正则语言 $A_{1}$ 和 $A_{2}$ 的有限自动机 $M_{1}$ 和 $M_{2}$ 开始。但是现在,构造自动机 $M$ 不再是如果 $M_{1}$ 或 $M_{2}$ 接受其输入就接受,而是如果其输入可以分成两部分,其中 $M_{1}$ 接受第一部分, $M_{2}$ 接受第二部分,它就必须接受。问题是 $M$ 不知道在哪里分割其输入(即,第一部分在哪里结束,第二部分在哪里开始)。为了解决这个问题,我们引入了一种新的技术,称为非确定性。
📖 [逐步解释]
这段话引出了下一个目标——证明正则语言对连接运算的闭包性,并指出了证明这个定理所面临的新挑战,从而引出一个全新的、极其重要的概念:非确定性。
- 承前启后:
- 回顾: 成功证明了并集的闭包性。
- 新目标: 证明连接的闭包性,即定理1.26。
- 定理1.26陈述:
- 正则语言的类对连接运算是封闭的。
- 展开: 如果 $A_1, A_2$ 是正则语言,那么它们的连接 $A_1 \circ A_2$ 也必然是一个正则语言。
- 尝试旧方法:
- 思路: 能不能模仿并集的证明?
- 起点: 同样是假设有有限自动机 $M_1$ 识别 $A_1$ 和 $M_2$ 识别 $A_2$。
- 构造新自动机 $M$ 的功能需求:
- 对于并集,M 在 $M_1$ 或 $M_2$ 接受时接受。
- 对于连接 $A_1 \circ A_2$,一个输入串 $w$ 属于这个语言,意味着 $w$ 可以被分割成两部分 $w = xy$,其中 $x \in A_1$ (即 $M_1$ 接受 $x$) 且 $y \in A_2$ (即 $M_2$ 接受 $y$)。
- 所以,$M$ 的任务是判断输入 $w$ 是否能找到这样一种分割。
- 发现新困难:
- 核心问题: 分割点是未知的!
- 举例: 设 $w = w_1w_2w_3w_4w_5$。
- 分割点可能在 $w_1$ 之后,即 $x=w_1, y=w_2w_3w_4w_5$。
- 也可能在 $w_2$ 之后,即 $x=w_1w_2, y=w_3w_4w_5$。
- ...
- 对于我们目前所学的确定性有限自动机 (DFA),它在读取输入时,无法“猜测”分割点在哪里。当它读到 $w_1$ 时,它不知道应该继续作为 $M_1$ 的一部分运行下去,还是应该在此刻“切换”到 $M_2$ 的模拟。它没有“未卜先知”的能力。
- 引入解决方案:非确定性 (Nondeterminism):
- 根本困难: 确定性 (Determinism) 模型要求每一步的行动都是唯一确定的。
- 新思路: 如果我们的机器被允许“猜测”呢?或者说,如果它在某个点可以“分身”,同时探索多条路径呢?
- 非确定性: 这就是“非确定性”的核心思想。我们即将引入一种新的计算模型,它放宽了确定性的限制,允许在某些情况下有多种下一步的选择。
- 如何解决连接问题: 有了非确定性,自动机 $M_1$ 在每读完一个符号后,除了可以继续在 $M_1$ 内部转移,还可以有一个“猜测”的选项:“也许 $M_1$ 的部分到此结束了,现在开始切换到 $M_2$ 的起始状态运行”。只要有任何一条这样的“猜测”路径最终成功(即 $M_1$ 部分结束在 $F_1$,$M_2$ 部分结束在 $F_2$),整个串就被接受。
💡 [数值示例]
- 语言: $A_1 = \{\text{"a"}\}$, $A_2 = \{\text{"b"}\}$。$A_1 \circ A_2 = \{\text{"ab"}\}$。
- 输入串: "ab"。
- 确定性自动机 $M$ 的困境:
- 读 a: $M$ 跑在模拟 $M_1$ 的部分。$M_1$ 接受 a。此时 $M$ 应该做什么?
- 选择1: 假设 a 就是第一部分 $x$。那么 $M$ 需要开始用剩下的输入 b 来模拟 $M_2$。
- 选择2: 假设 a 还不是 $x$ 的全部。万一语言 $A_1$ 是 {"a", "aa"} 怎么办?$M$ 需要继续用模拟 $M_1$ 的方式读下一个 b。
- $M$ 无法做出确定的选择。
- 非确定性自动机 $M$ 的能力:
- 读 a: $M$ 模拟 $M_1$ 跑完 a 后,$M_1$ 到达接受状态。此时 $M$ “分裂”成两个计算分支:
- 分支1 (猜测分割点在此): 这个分支“交棒”给 $M_2$,开始用输入 b 在 $M_2$ 的起始状态上运行。
- 分支2 (猜测分割点在后面): 这个分支继续在 $M_1$ 上运行,用输入 b 来处理。
- 最后,分支1 会成功($M_2$ 跑完b后接受),而分支2 会失败。因为只要有一个分支成功,整个串就被接受。
⚠️ [易错点]
- 非确定性不是随机性: 非确定性不等于“随机”或“概率”。它更像是“并行宇宙”或“穷举搜索”。机器会同时探索所有可能的路径,只要其中一条是通的,就算成功。它不是按某个概率去选择一条路。
- 非确定性是理论工具: 非确定性有限自动机 (NFA) 是一个强大的数学工具,便于我们进行设计和证明。虽然现实世界的计算机都是确定性的,但我们将在后续证明,任何NFA都可以被转换成一个等价的DFA。所以,引入非确定性并没有增强有限自动机的计算能力,但极大地增强了我们的设计和分析能力。
📝 [总结]
本段在尝试证明正则语言对连接运算封闭时,遇到了现有确定性模型无法解决的“未知分割点”问题。为了克服这个困难,作者顺势引入了一个全新的、更灵活的计算范式——非确定性,预示着我们将学习一种新的自动机模型。
🎯 [存在目的]
本段的目的是展示现有理论(DFA)的局限性,并以此为契机,自然地、有说服力地引入一个更强大的理论工具(NFA)。它不是凭空抛出一个新概念,而是通过解决一个实际问题(连接闭包的证明)的需求,来论证这个新概念的必要性和价值。这是一种非常高明的教学手法。
🧠 [直觉心智模型]
- 侦探破案:
- 确定性侦探 (DFA): 他只有一个选择。在岔路口,他必须根据现有线索,选择一条他认为最正确的路走下去。如果走错了,就破案失败。
- 非确定性侦探 (NFA): 他有超能力。在每个岔路口,他都可以“分身”,让每个分身去探索一条路。只要有任何一个分身最终找到了凶手,就算整个侦探破案成功。
💭 [直观想象]
想象你在玩一个迷宫游戏。
- 确定性玩法 (DFA): 在每个路口,你只能选择一个方向前进。
- 非确定性玩法 (NFA): 在每个路口,你可以放下无数个你的“克隆体”,让每个克隆体去探索一个方向。你自己则坐在入口处喝茶。只要有任何一个克隆体通过无线电报告“我找到出口了!”,你就立刻宣布你通关了。
连接运算的证明,就需要这种“克隆”能力来“猜测”所有可能的分割点。
2行间公式索引
- $M_1$ 识别的语言 A 的集合描述:
$$
\begin{aligned}
A=\{w \mid & w \text { 包含至少一个 } 1 \text { 并且 } \\
& \quad \text { 最后一个 } 1 \text { 后跟随偶数个 } 0 \text {s }\}。
\end{aligned}
$$
- $M_3$ 识别的语言的集合描述:
$$
L\left(M_{3}\right)=\{w \mid w \text { 是**空串** } \boldsymbol{\varepsilon} \text { 或以 0 结尾}\}$。
$$
- 用于构造并集自动机的转移函数定义:
$$
\delta\left(\left(r_{1}, r_{2}\right), a\right)=\left(\delta_{1}\left(r_{1}, a\right), \delta_{2}\left(r_{2}, a\right)\right) 。
$$
- 用于构造并集自动机的接受状态集定义:
$$
F=\left\{\left(r_{1}, r_{2}\right) \mid r_{1} \in F_{1} \text { 或 } r_{2} \in F_{2}\right\} 。
$$
[[END_OF_RESPONSE]]所有解释内容已全部输出完毕。