有穷自动机 - 版本历史

镜华酱：// Edit via Wikiplus

2024-06-23T15:27:19Z

// Edit via Wikiplus

←上一版本		2024年6月23日 (日) 23:27的版本
第1行：		第1行：
	~~有穷自动机或称有穷状态自动机，~~'''是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。'''		有穷自动机（Finite Automaton, FA），也称为有限状态机（Finite State Machine, FSM），是计算理论中的一个基本概念，'''是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。'''用于模拟和识别具有离散输入输出的系统。

	== 确定性有穷自动机(DFA) ==		== 确定性有穷自动机(DFA) ==

镜华酱：/* 确定性有穷自动机 */ // Edit via Wikiplus

2024-06-23T15:23:41Z

确定性有穷自动机： // Edit via Wikiplus

←上一版本		2024年6月23日 (日) 23:23的版本
第1行：		第1行：
	有穷自动机或称有穷状态自动机，'''是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。'''		有穷自动机或称有穷状态自动机，'''是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。'''

	== 确定性有穷自动机 ==		== 确定性有穷自动机(DFA) ==

	=== 定义 ===		=== 定义 ===

镜华酱：/* 非确定性有穷自动机 */ // Edit via Wikiplus

2024-06-23T15:23:12Z

非确定性有穷自动机： // Edit via Wikiplus

←上一版本		2024年6月23日 (日) 23:23的版本
第73行：		第73行：
	</math>		</math>

	== ~~非确定性有穷自动机~~ ==		== 非确定性有穷自动机（NFA） ==

	=== 定义 ===		=== 定义 ===

2023年8月27日 (日) 06:12 星河

2023-08-27T06:12:56Z

←上一版本		2023年8月27日 (日) 14:12的版本
第1行：		第1行：
	~~有穷自动机或称有穷状态自动机，是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。~~		有穷自动机或称有穷状态自动机，'''是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。'''

	== 确定性有穷自动机 ==		== 确定性有穷自动机 ==

Rmolives：/* 扩展转移函数 */

2022-02-21T02:13:11Z

扩展转移函数

←上一版本		2022年2月21日 (一) 10:13的版本
第58行：		第58行：
	</math>		</math>

	其中<math>q \in Q$，$a \in \Sigma</math>， <math>w,x \in \Sigma^*</math>		其中<math>q \in Q</math>，<math>a \in \Sigma</math>， <math>w,x \in \Sigma^*</math>

	==== 定理一 ====		==== 定理一 ====

Rmolives：/* 运算 */

2022-02-19T09:44:54Z

运算

←上一版本		2022年2月19日 (六) 17:44的版本
第121行：		第121行：
	=== 运算 ===		=== 运算 ===

	假如对于上面的确定性有穷自动机<math>\mathcal M_2</math>，输入字符串<math>010</math>，此时从初始状态<math>q_0</math>开始，读入第一个字符<math>0</math>，因为~~<math>~~<math>\delta(q_0,0)=\{q_0,q_1\}</math>，此时有<math>2</math>个转移方向：		假如对于上面的确定性有穷自动机<math>\mathcal M_2</math>，输入字符串<math>010</math>，此时从初始状态<math>q_0</math>开始，读入第一个字符<math>0</math>，因为<math>\delta(q_0,0)=\{q_0,q_1\}</math>，此时有<math>2</math>个转移方向：

	# 转移状态至<math>q_0</math>，读入下一个字符1，因为<math>\delta(q_0,1)=\{q_0\}</math>，所以转移状态至<math>q_0</math>，读入下一个字符0，因为<math>\delta(q_0,0)=\{q_0,q_1\}</math>，此时有<math>2</math>个转移方向：		# 转移状态至<math>q_0</math>，读入下一个字符1，因为<math>\delta(q_0,1)=\{q_0\}</math>，所以转移状态至<math>q_0</math>，读入下一个字符0，因为<math>\delta(q_0,0)=\{q_0,q_1\}</math>，此时有<math>2</math>个转移方向：

2022年2月19日 (六) 09:41 Rmolives

2022-02-19T09:41:35Z

←上一版本		2022年2月19日 (六) 17:41的版本
第1行：		第1行：
			有穷自动机或称有穷状态自动机，是一个根据输入的内容，再根据自身的转移规则来改变自身状态，进而确定是否识别该内容的模型。

	== 确定性有穷自动机 ==		== 确定性有穷自动机 ==

2022年2月19日 (六) 09:40 Rmolives

2022-02-19T09:40:17Z

←上一版本		2022年2月19日 (六) 17:40的版本
第1行：		第1行：
	~~有穷自动机或称有穷状态自动机，它是根据输入的内容的不同，根据一系列规则来改变自身状态，最终确定是否识别该内容的一种模型。~~

	== 确定性有穷自动机 ==		== 确定性有穷自动机 ==

2022年2月19日 (六) 09:40 Rmolives

2022-02-19T09:40:14Z

←上一版本		2022年2月19日 (六) 17:40的版本
第1行：		第1行：
			有穷自动机或称有穷状态自动机，它是根据输入的内容的不同，根据一系列规则来改变自身状态，最终确定是否识别该内容的一种模型。

	== 确定性有穷自动机 ==		== 确定性有穷自动机 ==

2022年2月19日 (六) 09:37 Rmolives

2022-02-19T09:37:30Z

←上一版本		2022年2月19日 (六) 17:37的版本
第151行：		第151行：
	</math>		</math>

	== 带空转移的非确定性有穷自动机 =='''		== 带空转移的非确定性有穷自动机 ==
	带空转移的非确定性有穷自动机（<math>\varepsilon</math>-NFA）'''是一个5元组<math>(Q,\Sigma,\delta,q_0,F)</math>，其中		'''带空转移的非确定性有穷自动机（<math>\varepsilon</math>-NFA）'''是一个5元组<math>(Q,\Sigma,\delta,q_0,F)</math>，其中

	# Q是一个有穷集合，称为状态集		# Q是一个有穷集合，称为状态集
第168行：		第168行：
	# 它有一个接受状态集，表示处理表达为接受的状态		# 它有一个接受状态集，表示处理表达为接受的状态

	=== 状态的<math>\varepsilon</math>-闭包 ==		=== 状态的<math>\varepsilon</math>-闭包 ===

	状态<math>q</math>的<math>\varepsilon</math>-闭包(<math>\varepsilon</math>-<math>\mathcal {Closure}</math>)，记为<math>E_{CLOSE}(q)</math>，表示从<math>q</math>经过<math>\varepsilon \varepsilon \cdots \varepsilon</math>序列可达的全部状态集合，定义为		状态<math>q</math>的<math>\varepsilon</math>-闭包(<math>\varepsilon</math>-<math>\mathcal {Closure}</math>)，记为<math>E_{CLOSE}(q)</math>，表示从<math>q</math>经过<math>\varepsilon \varepsilon \cdots \varepsilon</math>序列可达的全部状态集合，定义为

有穷自动机 - 版本历史

镜华酱：​// Edit via Wikiplus

镜华酱：​/* 确定性有穷自动机 */ // Edit via Wikiplus

镜华酱：​/* 非确定性有穷自动机 */ // Edit via Wikiplus

2023年8月27日 (日) 06:12 星河

Rmolives：​/* 扩展转移函数 */

Rmolives：​/* 运算 */

2022年2月19日 (六) 09:41 Rmolives

2022年2月19日 (六) 09:40 Rmolives

2022年2月19日 (六) 09:40 Rmolives

2022年2月19日 (六) 09:37 Rmolives

镜华酱：// Edit via Wikiplus

镜华酱：/* 确定性有穷自动机 */ // Edit via Wikiplus

镜华酱：/* 非确定性有穷自动机 */ // Edit via Wikiplus

Rmolives：/* 扩展转移函数 */

Rmolives：/* 运算 */