[科普中国]-变迁系统

在计算机科学和控制理论中，“变迁系统”用数学的方法描述离散系统的行为。变迁系统主要由“状态”和状态之间的“状态迁移”组成。

简介有标号的变迁系统可以从已定义的标签集合中选择相应标签来标记状态迁移，而且相同的标签可能被应用在多个状态迁移上。 变迁系统也可以是无标记的，此时也可以认为标签集合中只有单一标签元素，从而省略了状态迁移上的标签记号。变迁系统在数学定义上和有向图一致，但与有限状态自动机有一定不同。1

特点变迁系统的特点有：

系统状态的集合不一定是有限的或可数的；

状态迁移的集合不一定是有限的或可数的；

变迁系统并不需要给出“开始”状态或“最终”状态；

变迁系统可以表示为有向图，有限状态自动机则不能。1

操作语义学操作语义学是计算机科学中的一个概念，它是使得计算机程序在数学上更加严谨的一种手段。其它类似的手段包括提供形式语义学，包括公理语义学和指称语义。

一个计算机语言的操作语义描述一段合理的程序是怎样被理解为一系列计算机步骤的。这些步骤就是这个程序的意义。在函数编程语言中一段终结性的序列在最后一步的返回程序的值。（由于一个程序可能是非非决定的，一般来说一个程序能够有许多不同的计算步骤和许多不同的返回值。）

操作语义最早被用来定义Algol 68的语义。下面这句话引用修正的ALGOL 68报告：

一个使用严格语言编写的程序的意义是通过一个假设的计算机来执行该程序的组成部分时完成的行动来解释的。（Algol68，第二章）

丹纳·司科特是第一个在今天的这个定义下使用操作语义这个概念的（Plotkin04b）。以下是司科特关于形式语义学的讲稿，其中他提到了语义的“操作”观点。1

有限状态机有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

状态存储关于过去的信息，就是说：它反映从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述。有多种类型的动作：

进入动作（entry action）：在进入状态时进行

退出动作：在退出状态时进行

输入动作：依赖于当前状态和输入条件进行

转移动作：在进行特定转移时进行2

本词条内容贡献者为:

李航 - 副教授 - 西南大学