有穷自动机的分类
# 有穷自动机的分类
课件
- 确定的FA (Deterministic finite automata, DFA)
- 非确定的FA (Nondeterministic finite automata, NFA)
# 确定的有穷自动机 (DFA)
定义
: 有穷状态集 : 输入字母表,即输入符号集合 - 假设
不是 中的元素
- 假设
: 将 映射到 的转换函数 表示从状态 出发,沿着标记为 的边所能到达的状态
:开始状态 (或初始状态), : 接收状态(或终止状态)集合,
例: 一个 DFA
- 可以用转换表来表示 DFA
# DFA 的算法实现
输入输出
- 输入:以文件结束符eof结尾的字符串
。DFA 的开始状态 ,接收状态集 ,转换函数 - 输出: 如果
接收 ,则回答“yes”,否则回答“no”
算法实现
方法:将下列算法应用于输入串
s = s0 ; c = nextChar(); while(c! = eof ){ s = move ( s , c ) ; c = nextChar ( ) ; } if (s在F中) return“yes”; else return “no”;
1
2
3
4
5
6
7
8- 函数
nextChar()
返回输入串x
的下一个符号 - 函数
move(s, c)
表示从状态s
出发,沿着标记为c
的边所能到达的状态
- 函数
# 非确定的有穷自动机 (NFA)
定义
: 有穷状态集 : 输入字母表,即输入符号集合 - 假设
不是 中的元素
- 假设
: 将 映射到 的转换函数 表示从状态 出发,沿着标记为 的边所能到达的状态集合(可能不止一个) 为集合 的幂集,表示集合 中所有子集的集合
:开始状态 (或初始状态), : 接收状态(或终止状态)集合,
例: 一个 NFA
- 转换图
- 转换表
- 转换表
- 如果转换函数没有给出对应于某个状态-输入对的信息,就把
放入相应的表项中
- 如果转换函数没有给出对应于某个状态-输入对的信息,就把
- 转换表
# DFA 和 NFA 的等价性
DFA 和 NFA 可以识别相同的语言
- 对任何非确定的有穷自动机
,存在定义同一语言的确定的有穷自动机 - 对任何确定的有穷自动机
,存在定义同一语言的非确定的有穷自动机
例: 由 DFA 和 NFA 来表示正则表达式
- 正则表达式:
- NFA 和 DFA 的转换图
-
- 状态1:串以
结尾 - 状态2:串以
结尾 - 状态3:串以
结尾
- 状态1:串以
-
# 带有“ε-边”的NFA
定义
: 有穷状态集 : 输入字母表,即输入符号集合 - 假设
不是 中的元素
- 假设
: 将 映射到 的转换函数 表示从状态 出发,沿着标记为 的边所能到达的状态集合(可能不止一个) 为集合 的幂集,表示集合 中所有子集的集合
:开始状态 (或初始状态), : 接收状态(或终止状态)集合,
示例
- 正则表达式
的带有“ 边” 的转换图
# 带有和不带有“ε-边”的NFA 的等价性
示例
编辑 (opens new window)