离散事件系统建模：自动机五元组、生成语言与标记语言详解

第四章把离散事件系统的抽象工具一股脑端了上来：自动机、形式语言、正则运算、阻塞分析。前面几章还在用自然语言和图示讨论“事件驱动”的直觉，到了这一章，直接从“描述系统”跳到了“严格定义系统”。这篇笔记我会尽量按原书的逻辑走，但会把容易绕晕的地方拆开讲，包括我自己第一次读的时候理解错的几个点。

如果只让我用一句话概括这一章，那就是：用一套完全形式化的语言来描述事件序列的合法性。读完你会掌握状态机怎么用五元组表达，什么叫生成语言和标记语言，以及怎么判断一个系统模型会不会“卡死”或者“停不下来”。这套东西是后续学习监督控制、故障诊断和时序分析的地基，适合正在读原书第四章、或者已经读完但希望把细节串一遍的读者。

1. 第四章在整本书里的位置，以及我为什么要单独写笔记

1.1 教材连续性和这一章的定位

《Introduction to discrete event systems》前面章节铺垫了大量动机：离散事件系统的状态由事件驱动而不是由时钟驱动，事件的发生时机不确定、顺序敏感，所以需要一套独立于微分方程的建模方法。前三章帮读者建立直觉，第四章开始动手搭形式化框架。可以说，第四章是把“离散事件系统”从一种观察角度变成一门“能用数学语言讨论的学科”的分水岭。

我单独为这一章写笔记，是因为它在全书中起着承上启下的作用。承上，是承接自动机与语言的基本概念，把事件序列用符号串的形式写下来；启下，是后面的可控制性分析、状态估计、故障诊断都要用到这里的“语言”与“状态”的关系。尤其是标记语言这个概念，如果在这一章没有真正吃透，后面学监督控制理论时会非常痛苦。原书在第四章引入的语言体系和符号约定，几乎贯穿了全部后续内容。

这一章的阅读难点不在于单个定义有多复杂，而在于多个抽象概念同时出现：状态、事件、转移函数、语言、正则运算，它们相互纠缠。很多初学者（包括我）会陷入一个误区，觉得自动机不过是画图，把状态圈和箭头画出来就算懂了。实际上画图只是辅助，形式化的五元组和语言定义才是这一章要训练的思维。

1.2 读完这一章你该带走什么

我给自己的学习目标列了一个能力清单，放在这里作为笔记的“验收标准”：

• 给定一个实际系统，能自然地在头脑里抽出“状态集、事件集、转移函数、初始状态、标记状态”这五个要素。
• 能区分“系统可以生成的序列”和“系统从初始状态到达标记状态过程中产生的序列”，也就是生成语言与标记语言。
• 能用正则运算对语言做并、连接、闭包等操作，简单解释结果语言表示什么。
• 能识别自动机中的死锁、活锁、阻塞，并在小规模状态图上手工判断。
• 能独立把一个带故障、修复、缓冲区的小系统从需求建模成自动机，并用转移表验证行为。

如果这些能力都达到了，那么这一章的基本目标就算完成。如果只是“能看懂定义但不会建模”，大概率是缺少从实际场景到五元组的翻译练习。所以我后续在笔记里会刻意放一个完整建模的例子，而不是只列定义。

2. 核心模型：自动机五元组到底在说什么

2.1 从“事件驱动”到五元组

自动机的五元组是这一章最基础的内容：状态集、事件集、转移函数、初始状态和标记状态集。看似简单，但我发现最容易出问题的是转移函数。书上常说转移函数是部分函数，也就是说并非每个状态都能响应所有事件。这个细节容易被忽略，因为画状态图的时候，我们都习惯只画有效转移，不会把所有“不合法事件”的箭头都画出来。但形式化定义时，部分函数意味着“事件在这个状态下没有定义”，而不是“事件发生后停留在原状态”。

两个说法在实际建模中有本质区别。

假如一个系统在“空闲”状态下收到“故障恢复”事件，常见的建模方式是：这个事件在空闲状态下根本不应该发生，所以转移函数对该组合无定义。如果图省事，把这个组合写成转移到空闲状态本身，相当于默认故障恢复事件随时可以发生且没有效果，这会引入大量实际系统中不存在的语言序列，导致后面分析出的行为比真实系统更“宽松”。

我建议在建模初期就明确：每个状态下，事件集里哪些事件是“合法”的，哪些是“不该出现”的。该不该出现，取决于系统物理约束，而不是取决于我们是否愿意画箭头。把无效事件显式标成“无定义”，比用自环代替要严谨得多。这一步做对了，后续做语言交集或观察器构造时，定义域问题才不会埋雷。

状态集和事件集的选取也要说两句。状态不是越细越好，事件也不是越少越好。状态粒度过细会导致状态爆炸，过粗又丢掉了必要的区分能力。第四章虽然不会直接教你“怎么划分状态”，但通过语言等价的概念，会逼迫你思考“什么样的状态差异是系统行为上真正有差异的”。这一点我会在第四章实操部分展开讲。

2.2 生成语言与标记语言，这两个概念必须分清

原书里这一章最重要的两个定义，我认为是生成语言和标记语言。生成语言是所有从初始状态出发、沿合法转移序列产生的标签序列集合。它描述的是“系统可能经历的一切事件轨迹”，不管系统最后有没有到达某个完成状态。标记语言则是那些到达标记状态下的事件序列，它描述的是“系统成功完成某个任务”的轨迹。

我第一次读的时候把这两个概念混在一起，结果后面看监督控制相关章节时完全不知道监督器要约束的是哪个语言。这里用一个类比：生成语言像是记录一个人从早上出门到晚上回家之间所有行走路径，你可以走到任意地点再折返；标记语言则只关注“到达了目的地”的那些完整路径。很多分析，尤其是“任务完成”相关的问题，关心的是标记语言；而安全性、可达性分析则经常涉及生成语言。

两者的关系也值得想清楚。标记语言是生成语言的子集，因为任何能到标记状态的轨迹，首先是一段合法轨迹。但反向不成立：存在能合法执行却永远无法到达标记状态的轨迹。这种轨迹恰恰是“阻塞”的来源。一个系统如果存在一个状态，从它出发无论怎么走都到不了标记状态，那么这个状态一旦被进入，系统就一直“悬着”，没有完成的可能。

在读这一章时，我建议把这两个集合记成不同的符号，做题时明确写出每个结论用的是哪一类语言，能避免大量混淆。我从第四章后养成的习惯是：描述系统行为时先问“我要的是全部合法轨迹，还是完成轨迹”。

2.3 一个最简单的建模示例

用一个简单工作站例子来串一遍五元组。场景：一台机器初始处于空闲状态，收到“启动”事件进入加工状态，加工完成后触发“完成”事件回到空闲。忽略故障，我们取状态集为{空闲，加工}，事件集为{启动，完成}。初始状态是空闲，标记状态可以设为空闲，表示一次加工周期“完成”回到原状。

转移函数如下：

注意：在“空闲”状态下没有对“完成”事件的定义，在“加工”状态下没有对“启动”事件的定义。生成语言是“启动、完成”不断交替的所有有限序列，标记语言是从初始状态出发、最后回到空闲状态的序列，两者实际上是同一套序列。这个例子小得不起眼，但它能帮你验证自己对五元组的理解：部分转移函数、初始状态、标记状态三者间的关系。

等到后面加入故障和修复事件，事件集变为{启动，完成，故障，修复}，转移关系变复杂，生成语言就未必等于标记语言了。这就是下一部分要深入的内容。

2.4 为什么语言视角比状态图视角更“能打”

状态图适合人眼观察，语言适合做数学运算。第四章最重要的思维转变，是把自动机当成一个“语言的生成器”，而不是单纯的图形。为什么非要这样？因为很多后续操作，比如求两个系统的同步、判断一个系统是否满足某种规格、构造监督器，都需要对语言做集合运算。图形没法直接做交集、补集，但语言可以。

用生活化类比：状态图像电路原理图，你可以直接看出电流流向；语言像代数方程，你可以在不画图的情况下推演出系统行为。电路工程师需要原理图，也需要方程；离散事件系统的研究者同样需要这两种视角。

另外，语言视角还有一个好处：我们可以在不知道具体状态数的情况下，讨论“一个系统是否可能生成某个序列”。很多规范和限制本身也不是用状态图给出的，而是用事件序列的因果约束给出的。语言与自动机的对等关系让我们既可以用图形表达，又可以用代数推理。这一章后续的正则运算，本质上就是在语言层面操作“系统的行为集合”。

3. 语言的基本运算与行为属性

3.1 正则运算的直觉理解

原书第四章会介绍正则语言的常见运算，包括并、连接、Kleene闭包、反转和补。这些运算看起来是形式语言课的内容，但在离散事件系统里，每个运算都能对应到一个直觉上的系统操作。

并运算对应“两个系统中的任意一个行为都可以发生”的系统；连接运算对应“先完成一个系统的任务，再完成另一个系统的任务”；Kleene闭包对应“一个任务可以被反复执行任意多次”。当你在系统里看到“重复加工”“循环检测”这类需求时，背后几乎都是这些运算。

我当初学这些运算最大的障碍是太把它们当形式符号，没有和系统行为挂钩。后来换了个方式：先用中文把语言集合描述出来，再写形式表达式。比如某个系统允许的事件序列是“开始后可以重复任意多次‘处理失败、重新处理’，最后以成功结束”，那么语言表达式可以写成：开始 + (处理失败 + 重新处理)* + 成功。先有语义，后有表达式，再构造自动机，思路就会很清楚。

补运算值得单独提醒一下。自动机定义中的补是针对某个事件集合上的全体有限序列而言的，补集往往包含大量“实际系统不可能发生”的序列。做补运算时，原本缺失的转移都要补上，通常会引入明显的“拒绝”状态。初学者容易忘记这一步，导致补语言的计算结果不对。

3.2 阻塞、死锁、活锁：从行为属性看系统是否“正常”

第四章把很多行为属性搬到了语言和状态图的框架下：可达状态、共达状态、死锁、阻塞、活锁。“可达”指的是从初始状态能去到的状态；“共达”指的是能到达某个标记状态的状态。两个概念合起来，可以描述系统是否有“永远无法完成”的风险。

死锁是指系统到达一个没有任何主动转移的状态，即无路可走。活锁则更隐蔽：系统仍在一路执行事件，但无论怎么执行，都到不了标记状态。用生成语言和标记语言可以精准描述阻塞：如果存在一条从初始状态出发的无限序列，它的每个前缀都属于生成语言，但整个序列永远不可能是某一串标记语言的前缀，那么这个系统就是阻塞的。

这里有一个经常被忽略的细节：第四章讨论的自动机通常是有限状态自动机，且状态转移关系不一定总保证“从任何状态都能到达标记状态”。所以阻塞检查本质上要看两方面：一方面有没有状态“卡死”导致事件序列无法继续延伸；另一方面有没有状态虽然可以继续走，但无法到达标记集合。后者如果存在，系统虽然从外部看还在运转，实际上已经丧失了“完成任务”的可能。

3.3 阻塞检测的手工判断方法

对于小规模自动机，手工检测阻塞有一套固定流程。我从这章学到的做法是：

1. 从标记状态集合出发，反向寻找所有能到达标记状态的状态，得到“反向可达集合”。
2. 把自动机限制在反向可达集合内，检查每个状态是否都存在至少一个合法转移，如果没有，说明系统存在从某些路径上无法继续推进的死锁。
3. 再检查从初始状态出发是否能保证最终进入反向可达集合。如果初始状态本身就在反向可达集合内，且限制后的自动机每个状态都有出路，那基本可以判断系统非阻塞。

这个流程看起来简单，实际操作时最容易出错的地方是反向搜索时把转移方向看反。转移函数是“状态+事件→下一状态”，反向搜索时要从下一状态找回到上一状态的所有可能事件，注意此时可能需要遍历所有状态和事件组合。我建议用一张转移表，先逐行标记每个状态的所有入边，再反向推进，能减少遗漏。

从语言视角看，非阻塞性质等价于：生成语言中任何有限序列，都能被延拓成一个标记语言序列。换句话说，系统无论走到哪一步，都存在一个继续推进到完成状态的方案。这个表述非常直观，做证明题时用语言定义，做直觉判断时用反向可达搜索。

4. 实操笔记：把一个真实场景完整建出来

4.1 建模前的四问

这一章读完之后，我给自己总结了一套建模前的问题清单。拿到一个实际场景时，先问四件事。

第一问：系统边界在哪。哪些事件是系统自己的行为，哪些是外部环境施加的输入。比如一台机床，启动、停机可以由控制器发出，属于系统可控行为；某个随机故障则是环境注入的事件，建模时事件集合必须包含它，但控制上它不可控。

第二问：事件集合怎么定。事件粒度和状态划分要配套。事件定得太粗，比如只定义“完成”而不定义“失败”，状态图很干净，却可能丢掉判断系统是否可靠的关键行为。

第三问：哪些状态是任务完成态。有的人建模时把所有“稳定状态”都标成标记状态，这是不对的。标记状态应该对应“一个有意义的过程结束”，而不是“没有事件发生”。如果所有状态都标记，标记语言就成了生成语言，阻塞概念失去意义。

第四问：状态记忆要保留多少信息。同一状态下，未来行为不同，那就必须拆状态；未来行为完全相同，再像的状态也可以合并。这是一个非常实用原则，也是最小化自动机背后思想的生活版。

把四个问题过一遍，再动手画图，通常比边画边想质量高很多。

4.2 一个带故障与修复的工作站模型

这个例子是我在实际学习时自己动手建的，过程比较有代表性。场景：一台机器负责处理工件，初始空闲；工件到达后启动加工，加工过程中可能发生故障；故障后进入待修状态，修复后回到空闲；加工成功则正常完成，回到空闲。这里标记状态定义为“空闲”，表示一个加工任务完成或一次修复完成后的稳定状态。状态我们拆成：空闲、加工中、故障待修。事件为：启动、完成、故障、修复。

转移关系按自然逻辑写：

在这张表里，“空闲”状态下没有定义“完成”“故障”“修复”事件，“加工中”状态没有定义“启动”“修复”事件，“故障待修”状态只接受“修复”。现在观察生成语言和标记语言的区别：生成语言包括 启动、故障、修复 这类序列，比如一次加工还没成功就因为故障中断了，然后又修复回空闲；标记语言则是能回到“空闲”状态的那些完整序列，包括“启动、完成”和“启动、故障、修复”。这里有个容易被忽略的细节：序列“启动、故障、修复”确实回到了标记状态，但它属于标记语言；而序列“启动、故障”本身不是标记语言，因为系统还停在故障待修状态。

你会发现，在建模中加入故障事件后，生成语言不再等于标记语言。“永远完不成任务”的阻塞风险通过状态转移关系体现了出来。对于这个简单模型，每个状态都有朝向标记状态的路径，所以系统是非阻塞的。一旦加入第二个故障源，状态变多，判断就没这么直观了。

4.3 状态爆炸时的化简思路

状态爆炸是离散事件系统建模永恒的话题。第四章本身没有系统讲解状态压缩算法，但我们在实战中可以用“等价状态合并”的思路做化简。两个状态如果从它们出发，对未来事件序列的接受行为完全相同，那它们就是等价的，可以把它们合并。

举个例子，一台设备有两个传感器，建模时如果把“传感器1正常、传感器2正常”“传感器1正常、传感器2故障”“传感器1故障、传感器2正常”“两者都故障”都作为单独状态，状态数会翻倍。但如果系统后续行为只关心“是否至少有一个传感器可用”，那么很多细分状态可以合并。关键判断标准仍然是：从新状态出发，能生成的语言集合是否一致。

章后习题里的不少题就是“简化给定的自动机”。我自己的做法是：先列出每个状态的出边，逐一比较两个状态的出边事件集合和对应目标状态，如果完全一致就合并，然后迭代。这种手工方法对几个状态的小模型足够用，最大的坑在于合并完一个等价类后，其他状态的行为可能发生变化，要重新检查一轮，直到不再有可合并状态为止。

从这一章开始，我对“状态数”这件事变得很敏感。建模时多问自己一句“这个状态差异真的会导致未来行为差异吗”，能省下后续分析的大量无效工作。

5. 学习过程中踩过的坑和排查方法

5.1 自动机“看着对，实际错”的常见原因

我学第四章时犯过几个低级错误，而且都是“看图完全正确，形式化时不对”的类型。

第一种是转移函数写漏。画图时因为省略无效转移，导致转移表里缺少部分定义项；但如果后面做自动机操作时，默认所有未定义转移都“保持原状态”，就会凭空扩大语言集合。正确做法是区分“无定义”和“自环”，别在表格里用一个横线草率带过。

第二种是标记状态的选择。我一度把“没有出边的状态”都当作标记状态，试图把死锁包装成任务完成。这相当于把系统故障状态当成正常终态，完全偏离了标记状态的含义。标记状态应该由业务语义决定，而不是由图结构决定。

第三种是对“完整自动机”和“非完整自动机”的混淆。完整自动机要求每个状态对每个事件都有定义，这个性质在做补运算时是前提。很多题目里的自动机并非完整自动机，如果没先补全就直接做补，结果就错了。补全的方式一般是加一个拒绝状态，把所有缺失转移引到拒绝状态，并且拒绝状态对所有事件都自环。

我建议每次做完自动机构造，都按“事件遍历法”自检：逐状态检查事件集里每个事件是否有对应的转移定义，并写下它是“合法转移”还是“无定义、拒绝或忽略”。这样能避免形式化表示与直觉图脱节。

5.2 做题和建模时最容易混淆的概念组

第四章的概念密度大，有几组概念我专门做了对比表格，放在笔记里反复看。

这些概念组看起来独立，实际上在分析同一类问题时会同时出现。比如判断阻塞，你需要标记语言定义、共达状态、死锁概念全部配合使用。把它们放在一张表格里反复对照，比单独背每个定义有用。

5.3 一条靠谱的学习与验证路径

如果让我给读第四章的人一条路径，我会建议按下面这个顺序推进，而不是直接抄教材习题：

第一步，用至少两个现实场景（比如一台工作站、一个自助售货机）建立自动机模型。先画状态图，再写五元组和转移表。第二步，手工列举五条左右的事件序列，分类哪些属于生成语言，哪些属于标记语言，哪些既不属于生成语言也不属于标记语言。第三步，对模型做补集和并操作，体会语言运算如何改变状态图结构。第四步，检查模型是否存在死锁或阻塞，用反向可达法手工推一遍。

做完这四步，再去做教材习题，效率会高很多。因为定义已经内化成了操作技能，而不是只能在记忆里复述的文字。我第一遍读第四章就是跳过了前两步，直接啃习题，结果很多题“似懂非懂”，回头补建模练习才把概念串起来。

另外，如果你手头正好有可以验证自动机的工具，建议把建好的模型丢进去跑一跑，看看生成的序列集合和手写的是否一致。自己写代码去枚举状态转移函数，本身也是一种很好的验证方式。但要注意，重点不是工具，而是你能否解释工具输出里每一段语言对应的实际系统行为。

6. 与后面章节的衔接和我个人的一点体会

6.1 这一章给后面监督控制理论打下的基础

第四章的一切铺垫，最终都指向后续的监督控制理论。监督控制的研究对象是一个被控系统自动机和一个规格语言，目标是设计一个监督器，通过禁用一部分可控事件，使得闭环系统的行为满足规格，同时保持非阻塞。

你会发现，监督器设计本质上是语言的交集运算：把被控系统的生成语言与规格语言做交集，然后判断交集是否非阻塞。如果第四章的语言模型没建好，交集的构造会变成纯粹的符号游戏，你不知道自己在删哪些轨迹。而只有把语言和状态图之间的关系吃透，才能理解为什么“禁用某个事件”等价于“从语言中删除一批事件序列”。

此外，可观察事件与可控事件的区分虽然在前几章偶然提起，但在约束和控制问题里，它们是监督器能否实现的关键。第四章没有深入讲可控性，但要求你具备用语言刻画“事件是否被允许”的能力。我后来回看第四章才发现，那些看似“纯数学”的语言性质，其实每一步都在为控制设计铺路。

6.2 我的实操体会与下一步计划

我读完第四章做的最值得的一件事情，是把自己生活中一个简单的排队系统完整建模了一遍。那次练习让我意识到，五元组定义本身不难，难的是状态划分和事件集的取舍。同一个物理系统，换一种状态划分方式，得到的语言集合就不同，阻塞结论甚至可能改变。这种敏感性只能在动手建模时获得，靠读是读不出来的。

下一步我计划进入Petri网章节时，把第四章的自动机模型和Petri网模型放在一起对比：哪些系统适合自动机描述，哪些系统用Petri网更自然。按我目前的体会，并发和资源竞争是自动机模型的痛点，而这正是Petri网建模擅长的地方。届时我会把第四章的语言视角带过去，看两者在表达能力上到底差在哪里。

如果你也在读这本书，我的建议很简单：别在定义处逗留太久，尽快进入“建模—枚举—检查”的循环。写完一个完整的自动机模型并亲手算出它的生成语言，比反复看十遍定义都有用。这一章的知识密度大，但每一分投入都会在后面变成实实在在的分析能力。