第四章把离散事件系统的抽象工具一股脑端了上来自动机、形式语言、正则运算、阻塞分析。前面几章还在用自然语言和图示讨论“事件驱动”的直觉到了这一章直接从“描述系统”跳到了“严格定义系统”。这篇笔记我会尽量按原书的逻辑走但会把容易绕晕的地方拆开讲包括我自己第一次读的时候理解错的几个点。如果只让我用一句话概括这一章那就是用一套完全形式化的语言来描述事件序列的合法性。读完你会掌握状态机怎么用五元组表达什么叫生成语言和标记语言以及怎么判断一个系统模型会不会“卡死”或者“停不下来”。这套东西是后续学习监督控制、故障诊断和时序分析的地基适合正在读原书第四章、或者已经读完但希望把细节串一遍的读者。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 阻塞检测的手工判断方法对于小规模自动机手工检测阻塞有一套固定流程。我从这章学到的做法是从标记状态集合出发反向寻找所有能到达标记状态的状态得到“反向可达集合”。把自动机限制在反向可达集合内检查每个状态是否都存在至少一个合法转移如果没有说明系统存在从某些路径上无法继续推进的死锁。再检查从初始状态出发是否能保证最终进入反向可达集合。如果初始状态本身就在反向可达集合内且限制后的自动机每个状态都有出路那基本可以判断系统非阻塞。这个流程看起来简单实际操作时最容易出错的地方是反向搜索时把转移方向看反。转移函数是“状态事件→下一状态”反向搜索时要从下一状态找回到上一状态的所有可能事件注意此时可能需要遍历所有状态和事件组合。我建议用一张转移表先逐行标记每个状态的所有入边再反向推进能减少遗漏。从语言视角看非阻塞性质等价于生成语言中任何有限序列都能被延拓成一个标记语言序列。换句话说系统无论走到哪一步都存在一个继续推进到完成状态的方案。这个表述非常直观做证明题时用语言定义做直觉判断时用反向可达搜索。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网建模擅长的地方。届时我会把第四章的语言视角带过去看两者在表达能力上到底差在哪里。如果你也在读这本书我的建议很简单别在定义处逗留太久尽快进入“建模—枚举—检查”的循环。写完一个完整的自动机模型并亲手算出它的生成语言比反复看十遍定义都有用。这一章的知识密度大但每一分投入都会在后面变成实实在在的分析能力。