有穷自动机
# 有穷自动机
课件
# 有穷自动机(FA)的基本定义
有穷自动机 ( Finite Automata,FA )由两位神经物理学家 MeCuloch 和 Pitts 于1948年首先提出,是对一类处理系统建立的数学模型
FA 的定义
- 这类系统具有一系列离散的输入输出信息和有穷数目的内部状态
- 状态:概括了对过去输入信息处理的状况
- 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。
- 每当系统处理了当前的输入后,系统的内部状态也将发生改变
FA 的典型例子: 电梯控制装置
- 输入:顾客的乘梯需求(所要到达的层号)
- 状态:电梯所处的层数+运动方向
- 电梯控制装置并不需要记住先前全部的服务要求,只需要知道电梯当前所处的状态以及还没有满足的所有服务请求
# FA 模型
模型图示
输入带 (input tape)
用来存放输入符号串
读头(head)
从左向右逐个读取输入符号,不能修改(只读)、不能往返移动
有穷控制器( finite control )
具有有穷个状态数,根据当前的状态和当前输入符号控制转入下一状态
# FA 的表示: 转换图 (Transition Graph)
转换图
结点
- 表示 FA 的状态
- 初始状态(开始状态):只有一个,由start箭头指向
- 终止状态(接收状态):可以有多个,用双圈表示
带标记的有向边
如果对于输入
# FA定义(接收)的语言
- 给定输入串
,如果存在一个对应于串 的从初始状态到某个终止状态的转换序列,则称串 被该 接收 - 由一个有穷自动机
接收的所有串构成的集合称为是该 FA 定义(或接收)的语言,记为
示例
# 最长子串匹配原则(Longest String Matching Principle)
- 当输入串的多个前缀与一个或多个模式匹配时,总是选择最长的前缀进行匹配
- 在到达某个终态之后,只要输入带上还有符号,DFA 就继续前进,以便寻找尽可能长的匹配
编辑 (opens new window)