形式语言与自动机有穷自动机PPT学习教案.pptx

会计学
1
形式语言与自动机有穷自动机
2
有穷状态系统
指针式钟表共有12*60*60个状态
小时×分钟×秒
围棋共有3361个状态
每一个格子：（空，黑，白）；
格子数量：19行×19列
某些电子产品中的开关电路，
具有n个门的开关网络有2n种状态
“网上购物”系统（示例：）
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第1页/共55页
3
2007年图灵奖
模型检验（model checking）:基于自动机理论的形式化方法(formal methods)
E. Clark
Emerson
Sifakis
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第2页/共55页
4
有穷自动机的基本定义
一个有穷自动机(Finite Automata)简称FA，是一个五元组：M = (Q,∑,δ,q0,F)，其中
（1）Q是有穷状态集；（States）
（2）∑是有穷的输入字母表 （Alphabet）
（3）δ是转移函数，它将Q×∑→Q (全映射)；（Transiston function）
（4）q0∈Q，是初始状态；（Initial state）
（5）F Q，是终结状态集。（Accepting states）(终止状态，接受状态)
上述定义的另一个说法：确定型的有穷自动机(Deterministic Finite Automata： DFA)
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第3页/共55页
5
DFA例子
q0
q1
q2
1
0
0
0,1
1
字母表： S = {0, 1}
状态集： Q = {q0, q1, q2}
初始状态： q0
终结状态: F = {q0, q1}
状态集
输入
0
1
q0
q1
q2
q0
q1
q2
q2
q2
q1
转换函数表 d:
*
*
→
问题：
1. 接受什么特征的字符串？
2. 状态q2起什么作用？
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第4页/共55页
6
这两个DFA所接受的字符串集合分别是什么？
DFA 例子
q0
q1
b
a
a
b
S = {a, b}
q0
q1
q2
q3
q4
a
a
a
a
a
b
b
b
b
b
S = {a, b}
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第5页/共55页
7
设计一个DFA(字母表为{0,1}),接受如下字符串：
设计一个DFA (字母表为{0,1}),接受如下特征的字符串：最多有三个1.
q0
q1
0
1
1
q2
0
q3
1
q4+
0, 1
0
1
0
DFA 例子
L = {010, 1}
qe
q0
q1
q01
q010
qdie
0, 1
0
1
0
0, 1
1
0
1
0, 1
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第6页/共55页
8
设计一个DFA(字母表为{0,1}),接受所有结尾是01的字符串。
提示：DFA得记住
读入字符串的最后两位。
DFA 例子
qe
0
1
q0
q1
q00
q10
q01
q11
0
1
0
1
0
0
1
1
1
0
0
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第7页/共55页
9
设计一个DFA(字母表为{0,1}),接受所有结尾是101的字符串。
DFA 例子
2021年4月29日星期四
南京航空航天大学计算机学院 胡军
第8页/共55页
10
给出一个有穷自动机
Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0})
其中：转移函数δ具体定义如下：
δ(q0,1)= q1 δ(q0,0)= q2