有限自动机逻辑
页面进行中。 |
有限状态机 - 有限自动机是一种抽象的计算模型,可根据输入数据或事件在不同状态之间顺序转换。有限自动机包含两种建模方法—状态机和转换图。
状态机逻辑
状态机有限自动机的一个例子:
执行算法包括以下步骤
状态机运行的一般逻辑
-
状态机的运行在任何状态被激活之前就已开始:
.3.3. 如果没有默认转换且只有一个状态,则会自动激活。+ 过渡到步骤 2。
-
在下一个机器步骤中,状态被激活后,将检查从激活状态可能发生的转换。这种转换可以是零、一个或多个。
.2.2. 如果从当前状态开始的过渡是唯一的过渡,则检查其条件。如果条件不满足,则自动机保持当前状态不变,并执行该状态的 "during "和 "on "部分(如果已设置)。如果条件为真,则首先执行过渡动作(如果给定)。其次是
-
如果任何一个过渡(第 2.2 和 2.3 条)是复合的(由两个或两个以上的分段组成),并且有分叉,则可以采用回溯脚注机制:[*回溯*是一种解决问题的方法,它试图按顺序搜索所有可能的解决方案,以找到正确的解决方案。当程序到达一个解决方案节点(例如,在过渡图中,它可以是一个输出节点),而所有可能的进一步行动变体都被证明是错误的(例如,从该节点出发的所有过渡都有错误的条件),它就会返回(回溯)到上一个解决方案节点,并尝试另一个(替代)变体。如果下一个过渡的条件不满足,自动机就会返回到最近的已通过分叉处,在那里仍有备选分支未测试,自动机就会沿着另一条路径进行新的尝试。如果没有可供选择路径的分叉,则当前状态保持激活,并执行其 "during "和 "on "部分(如果已设置)。
操作符组
在状态机运算符组 中,"进入"、"持续 "和 "退出 "在状态改变时和处于状态时启动执行动作。这些操作符的执行逻辑与转换、状态和激活顺序密切相关。让我们仔细看看每组操作符是如何工作的,以及它们是如何相互影响的:
-
为过渡检查条件--在每一步,状态机都会检查当前状态是否有激活的过渡。过渡的条件可以是变化指示器 条件(
hasChanged
等),也可以是时间逻辑(after
等),这些条件表明何时可以进行过渡; -
*如果条件满足,则执行过渡:
-
如果满足了过渡条件,有限自动机就会停用当前状态;
-
exit
- 如果指定了exit
运算符组,则在当前状态终止前执行。它会终止与该状态相关的所有操作; -
然后过渡到新的状态,在新状态中执行该状态的
进入
操作符组。
-
-
*如果过渡没有发生:
-
如果不满足过渡条件,有限自动机将保持当前状态;
-
期间":如果状态处于活动状态,且指定了 "期间 "的操作,则执行 "期间 "操作。只要自动机仍处于该状态且未满足过渡条件,则每一步都会继续执行;
-
on`:如果当前状态处于活动状态,且一组
on
操作符与该条件相关联,则在出现特定条件时执行。
-
运算符组执行的优先级
1.过渡条件 - 首先检查以确定是否进行过渡;
2.Transition Actions (过渡操作)--在确认过渡后,在检查条件后执行;
3.exit
- 在过渡前完成当前状态的执行;
4.on
- 如果状态处于激活状态,且发生了指定事件,则执行该操作;
5.entry
- 新状态激活时执行,为执行操作做准备;
6.during
- 当当前状态保持激活状态时,在自动机的每一步执行。
那么,带有转换和运算符组的有限自动机的逻辑如下:
-
在每一步,有限自动机都会检查转换的条件。如果可能发生转换,则对当前状态执行 "退出 "操作,然后对新状态执行 "进入 "操作;
-
如果不可能发生转换,则对当前状态执行 "持续 "操作;
-
on`增加了对事件做出反应的能力,只有当事件在状态激活时发生,才会激活动作。
过渡图逻辑
过渡图的逻辑包括从默认过渡开始依次分析节点和过渡。该算法可分为以下几点:
-
与状态机不同,转换图的每一步都要经过全面检查。如果条件为真,则执行转换;如果没有条件,则默认执行转换。如果过渡是可能的(条件为真或非真),图会执行与过渡相关的操作。过渡到步骤 2。
-
执行过渡时,如果条件为真或不存在,则执行该过渡所定义的操作。之后,执行到图中指定的下一个节点的过渡。动作的执行完成第二步,进入第三步。
-
如果自动机到达了一个节点,则会根据三种可能的结果执行以下操作:
-
如果一个节点的转换已经完成,自动机将移动到下一个节点,并从第 1 点开始继续执行。如果从节点开始的转换未执行,但有可能进行回溯,则执行回溯。如果无法回溯,则自动机步骤终止。整个执行逻辑完全基于节点之间的转换,以及对分支节点中转换序列号的记忆和顺序检查。
节点
节点 是过渡图的关键元素,是过渡的共轭点。节点是过渡图的关键元素,是过渡的共轭点,定义了过渡经过的点,组织了模型中步骤的有序序列。
过渡
转型 是节点之间的连接,指定了从一个节点移动到另一个节点的逻辑。每个转换都可能有一个条件,通过检查该条件来确定是否应该进行转换。过渡可以是有条件的(只有当某个条件为真时才执行),也可以是无条件的(如果激活则始终执行)。如果一个状态或节点有多个过渡,程序会为它们分配明确的优先级,并以数字形式显示(1,2,3 等)。在仿真过程中,将按此顺序检查转场,并执行第一个条件为真的转场。
过渡逻辑的典型案例:
-
节点间的简单转换,在满足与变量、参数或计算结果相关的条件时执行;
-
依赖于变化指示符(
hasChanged
,hasChangedFrom
,hasChangedTo
)、时序逻辑运算符等的转换,当某些参数的值发生变化时执行; -
回溯逻辑,如果当前转换的条件未满足,转换可返回前一个节点执行,以检查是否有其他路径。
过渡条件
转场条件 []`指定了定义转场发生时间的逻辑表达式。这些条件可能包括比较值、检查逻辑表达式或使用逻辑运算符(如 `hasChanged
)。如果条件为真,则执行转换并继续执行下一个节点。
在转换中使用条件的示例
-
条件可以检查值的范围,例如,只有达到某个参数级别时才执行转换;
-
逻辑表达式可以包含多重检查,例如一组条件(
A > 5 || B < 10
); -
变化指标用于确定系统状态在特定时间点是否发生了变化。
时态逻辑运算符
时间逻辑运算符 通过时间逻辑运算符,可以考虑与事件发生频率相关的时间方面或条件。逻辑运算符 "after"、"at "和 "every"(等)根据时间、事件的重复性或频率为转换设置条件。可在状态机中的状态内使用一组 on
操作符和 at 过渡。
时态逻辑应用举例
-
使用
after
运算符指定一个过渡,该过渡在与该运算符相关的状态激活后的给定时间间隔或状态机步数后执行; -
使用 "at "操作符设置一个过渡,该过渡仅在与该操作符相关的状态激活后的给定步骤执行;
-
使用 "every "操作符执行重复操作,以指定执行频率。
内存节点
内存节点 记忆节点允许有限自动机记住上一次激活的子状态,并在父状态重新激活时将其恢复。记忆节点适用于需要保留自动机上下文并从同一位置继续执行的情况,即使在退出和重新进入某一状态后也是如此。记忆节点的逻辑基础是记忆当前的子状态,并在满足特定条件时(如执行父状态的 "during "和 "on "组后)激活子状态。
内存节点应用实例:
-
当父状态被重新激活时,恢复上次激活的子状态;
-
执行需要暂时退出状态并在上下文保持不变的情况下返回状态的复杂场景;
-
管理子状态之间的转换,并将记忆状态考虑在内。