你好呀!在本文中,我们将学习计算机科学的一些基础知识。当然不是整个课程!只是计算理论的一部分。本主题是关于有限自动机的设计。我们将在后续部分讨论所有术语。那么,让我们来做吧。
Python 中的状态机是什么?
状态机是一种行为模型,它定义对象如何响应事件的行为。在 Python 中,状态机通常实现为有限状态机 (FSM)。FSM 是一种计算数学模型,可用于设计数字逻辑电路和计算机程序。它由一组状态、这些状态之间的转换以及转换发生时执行的操作组成。
有限状态机 (FSM) 是一种计算数学模型,可用于设计数字逻辑电路和计算机程序。它由一组状态、这些状态之间的转换以及转换发生时执行的操作组成。FSM 可以表示为有向图,其中状态表示为节点,转移表示为边。边缘标有触发转换的事件,并且操作与边缘相关联。
什么是 TOC 和自动机?
自动机理论和 TOC 都用于研究机器的行为,但它们采用不同的方法。自动机理论关注的是抽象机器本身,而 TOC 着眼于使用该机器可以解决的问题。
自动机理论是对抽象机器和自动机以及可以使用它们解决的计算问题的研究。自动机理论也与形式语言理论密切相关,因为自动机经常被用作形式语言的计算模型。计算理论(TOC)是数学的一个分支,研究算法及其效率。它涉及算法、数据结构和复杂性理论的设计和分析。
在计算理论这个主题中,我们设计了一些基于基本输入和输出的虚拟机。从最根本的层面来看,工作从接受确定长度的字符串开始。这些机器的基本术语是自动机。
自动机有两种类型:
- 确定性有限自动机(DFA)。
- 非确定性有限自动机 (NDFA)。
确定性有限自动机(DFA)的理解
确定性有限自动机 (DFA) 是一种特殊类型的有限状态机,它基于确定性算法接受或拒绝一串符号(称为输入字符串)。DFA 可以表示为有向图,其中状态表示为节点,转移表示为边。边缘标有触发转换的事件,并且操作与边缘相关联。
了解非确定性有限自动机 (NDFA)
非确定性有限自动机 (NDFA) 是一种特殊类型的有限状态机,可以基于非确定性算法接受或拒绝输入字符串。NDFA 可以表示为有向图,其中状态表示为节点,转移表示为边。边缘标有触发转换的事件,并且操作与边缘相关联。
基本自动机是五个单元的元组:
Automata = (Q, F, δ, q0, Σ) |
- Q = 所有状态的集合。
- F = 所有最终状态的集合。
- δ = 将状态运动与每个输入进行映射的转换函数或映射函数。
- q0 = 初始状态。
- Σ = 有限的输入符号集。
基本 DFA 的图
本机接受字符串“aa”。此处的图表是 DFA 最简单的表示。我们先来了解一下它的参数:
- 这里 Q = {q0, q1, q2}。一组最终状态。
- q0 是初始状态。
- q2 是最终状态
- Σ = {a} 是所有输入符号的集合。
该机器由三个状态组成——q0、q1 和 q2。最初,当我们向一个状态提供输入时,它会转移/移动到另一个状态。转换函数 ( δ ) 跟踪所有这些活动。当所需的字符串达到特定状态时,我们将其定义为该机器的最终状态。
自动机的应用
自动机理论是对抽象机器以及可以使用它们解决的计算问题的研究。自动机用于各种应用,包括验证、模型检查、调度和数据库更新。这是Automata的3个应用
- 游戏开发
- 人工智能_
- 编译器设计
现在让我们开始使用 Python 的状态机库构建状态机。
使用 Python 构建状态机
我们将使用 Python 编写我们自己的状态机。这与在纸上绘制相同。此外,我们将使用一些特殊操作来检查转换。
1.安装状态机库
打开命令提示符并输入pip 命令:
pip install python - statemachine |
工具和技术
- Python版本: 3.8.x或更高版本。
- 支持库: python-statemachine。
- 一个好的IDE:VSCode、Spyder等。
代码:
from statemachine import StateMachine, State class LightBulb(StateMachine): # creating states offState = State( "off" , initial = True ) onState = State( "on" ) # transitions of the state switchOn = offState.to(onState) switchOff = onState.to(offState) bulb = LightBulb() print (bulb.current_state) |
输出:
State( 'off' , identifier = 'offState' , value = 'offState' , initial = True ) |
解释:
- 我们首先导入该
state machine
模块以及State class
. - 我们首先创建一个LightBulb类。然后,要继承属性,请在括号内指定StateMachine 。
- 我们创建两种状态。
- offState:表示最初灯泡关闭。将初始参数设置为 True。
- onState:打开灯泡。
- 然后,创建两个过渡:
- switchOn:从 offState 转换到 onState。
- switchOff:从 onState 转换到 offState。
- 创建我们类的一个实例,即灯泡。
- 然后,为了检查当前状态,我们只需调用灯泡对象的current_state属性即可。
- 我们看到灯泡的当前状态是“关闭”。
状态机的动态属性
当我们创建状态机时,模块会为该机器中存在的每个状态创建一组特殊的属性。我们可以使用实例和属性检查该属性是否适用于该状态。在上面的代码中,我们有两个这样的状态。因此,创建的属性也是True。
检查属性的代码:
bulb.is_offState # returns True bulb.is_onState # returns False |
检查状态和转换的数量
让我们看看如何从 State 类中提取转换和所有状态。当我们的类只有两个状态时,这可能看起来没什么用。但考虑具有多种可能状态的类,这时这些技术就会派上用场。
检查状态数的代码:
在自动机中,我们需要记录所有当前状态。为此,我们使用以下列表理解。
a = [s.identifier for s in bulb.states] print (a) |
输出:
[ 'offState' , 'onState' ] |
解释:
- 我们使用列表推导式将所有状态存储在列表中。
- 然后使用“identifier”属性运行 for 循环。
- 使用states属性获取每个状态。我们需要使用灯泡对象来调用它,该对象是 LightBulb 类的实例。
- 将此列表分配给变量“a”。
- 然后打印它。我们得到了所有的状态。
检查转换的代码:
自动机总是从一种状态转移到另一种状态。简单来说,我们称之为过渡。因此,为了记录它们,我们的状态机有转换属性。
b = [s.identifier for s in bulb.transitions] print (b) |
输出:
[ 'switchOff' , 'switchOn' ] |
解释:
所有代码与状态代码保持相同。我们只需将“transitions”关键字与灯泡对象一起使用即可。
结论
那么,这样,我们就可以使用Python构建一个简单的状态机了。当我们设计人工智能算法或游戏时,这些机器是需要研究的重要概念之一。对于逻辑构建,状态机也是很好的页面主题。那么,到这里我们就结束这个话题了。
参考
您可以通过访问以下链接查看更多信息:https ://pypi.org/project/python-statemachine/