[5] 黄林鹏等译, Manber著, 算法引论-一种创造性方法, 电子.[M] [6] 刘汝佳等, 算法艺术与信息学竞赛, 清华大学.[刘]
计算理论 第1章 有限自动机
从字符串匹配问题说起
• 输入: 两个字符串x, y, (|x|=n, |y|=m)
• 输出: 所有y在x中出现的起点位置
• 例: x=abaabababbabababbababaa, y=ababbababaa
• 每步可以0至多种方式进入下一步 • 转移箭头上的符号可以是空串, 表示不读任何输入就可以转移过去
非确定型计算
0,1
q1 0 1 q2 1 0, 0 q3 1 1 0,1 q4 1
输入 01011
q3 ×
q1 q1 q2 q1
q4 q3 q1
q3
q4 q3
q2 × q 2
q1
q1
注: 若起始状态有射出的箭头?
符号集, m=Length(y), 计算转移函数
1. 对 q = 0:m
2. 对每个符号a, 3. k=min{m,q+1}
= {a,b}
f(0,a)=1, f(0,b)=0, abab|b, f(4,b)=5, abab|a, f(4,a)=0,
4.
5.
若 yk不是yqa的后缀, 则k-f(q,a)=k
计算理论与 算法分析设计
刘庆晖
教材:
[1] 王晓东,计算机算法设计与分析,电子工业.[王] [2] Lewis等著, 计算理论基础, 清华大学.[L] 参考资料: [3] 潘金贵等译, Cormen等著, 算法导论, 机械工业.[C]
[4] 唐常杰等译, Sipser著, 计算理论导引, 机械工业.[S]
算法 朴素 自动机 Knuth-MorrisPratt 预处理时间 0 O(m||) (m) 匹配时间 O((n-m+1)m) (n) (n)
其中是字母表
正则语言与正则运算
如果语言A被一DFA识别,则称A是正则语言 算术中, 对象是数, 操作是运算, 如+. 计算理论中, 对象是语言, 操作是语言的运算. 定义: 设A和B是两个语言,定义正则运算 并,连接,星号如下: 并: AB={x|xA或xB} 连接: AB={xy|xA且yB} 星号: A*={x1x2…xk|k0且每个xiA}
q1
有限自动机的设计(难点)
• 自己即自动机 • 寻找需要记录的关键信息
设计识别下列语言的DFA:
{ w{0,1}* | w从1开始, 以0结束 } 证明
{ w{0,1}* | w含有子串1010 }
{ w{0,1}* | w的倒数第2个符号是1 }
{ 0k | k是2或3的倍数 }
字符串匹配算法
匹配算法
1. n=Length(x), q=0 2. 对 i = 1:n 3. q=f(q,x[i]), 4. 若q=m, 打印 i-m+1
字符串与语言
字母表: 任意一个有限集. 常用记号, . 符号: 字母表中的元素 字符串: 字母表中符号组成的有限序列 如asdf, 通俗地说即单词 串的长度|· |, 例: |abcde|=5 串的连接*, 例: (abc)*(de)=abcde 串的反转R, 例: (abcde)R=edcba 空词: 记为, 长度为0 语言: 一些字符串的集合
b a
7
ababbab
b
a 6
ababba
x: a b a a b a b a b b a b a b a b b a b a b a a
0
1 2 3 1 2 3 4 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 输出 23-10 = 13
输入x,y, 串匹配的有限自动机算法
M1
0
q1 1
1
q2
0
q3
0,1
• 状态图等价于形式定义
0 1
q1
q2 q3
q1
q3 q2
q2
q2 q2
图灵对计算的观察
图灵: 计算通常是一个人拿着笔在纸上进行的. 他根据 眼睛看到的纸上符号, 脑中的若干法则, 指示笔 在纸上擦掉或写上一些符号, 再改变他所看到的范围. 继续, 直到他认为计算结束.
构造状态和转移函数
y=ababbababaa
b a
f: {0:11} {a,b} {0:11}
b a a 3
aba
a b 4
abab
b b 5
ababb
0
a
1 a
b
2
ab
a
ababbababaa a ababbababa
a b b 10
11
a
b 9
ababbabab
b
a 8
ababbaba
NFA的计算方式
Step 1.设读到符号s, 对(每个副本)机器状态q, 若q有多个射出s箭头,则机器分裂成多个副本. 状态相同的副本视为同一副本. Step 2. 对每个副本的状态,若其上有射出的箭头, 则不读任何输入, 机器分裂出相应副本. Step 3. 读下一个输入符号, 转step1. 若无输入符号, 计算结束, 并且, 若此时有一个副本处于接受状态,则接受, 否则拒绝.
NFA的形式定义
0,1 q1 1 q2 0, q3 1 0,1 试写出该状态图 q4
对应的形式定义
定义: NFA是一个5元组(K,,,s,F), 1) K是状态集; 状态图 2) 是字母表; 与 3) : K P(K)是转移函数; 形式定义 包含 4) sK是起始状态; 相同信息 5) FK是接受状态集;
上的语言与N等势
决定性问题与语言一一对应
决定性问题(Dicision Prob): 只需回答是与否的问题
“一数是否是偶数” --------------{ 以0结尾的01串 }
“串0,1个数是否相等”------{ 0,1个数相等的01串 } “串长度是否是2的幂次”----------------{
对于输入, NFA计算的路径可能不唯一.
NFA计算形式定义举例
0,1
N
0
q1
1 1
q2
0,
0
q3 1 1 q4
0,1 q4 1 q4 q3
q3 ×
q1
q1
q2
q1
q3 q1
q3
q2 × q 2
q1
q1
NFA的设计(难点)
• 自己即自动机 • 寻找需要记录的关键信息
设计识别{0,1}上以下语言的NFA:
脑:控制器 纸:存储带 眼睛和笔:读写头 法则:转移函数
有限自动机是简化的图灵机
读写头不能改写, 且只能右移的图灵机
M1 0
q1 1
1
q2
0
q1
q3 1 1 0 1
0,1
状态: q1,q2,q3 起始状态q1 接受状态q2 转移: 箭头 运行: 从起始状态开始沿转移箭头进行. 输出: 输入读完处于接受状态则接受, 否则拒绝.
{ w{0,1}* | w从1开始, 以0结束 }
{ w{0,1}* | w含有子串1010 }
{ w{0,1}* | w是倒数第2位是1 }考虑习题1.61
{ 0k | k是2或3的倍数 }
NFA与DFA等价
定理: 每个NFA都有一台等价的DFA.
0,1
N
0
q1
1 1
q2 0
0,
q3 1 1 q4 q3
问题:
1. 正则运算对于正则语言是否封闭?
2. 如何判断一个语言是正则语言?
非确定型机器(难点)
前面因为: Q Q是一个函数, 所以 • 每步存在唯一的方式进入下一状态 • 称为确定型有限自动机(DFA) 现在引入非确定型有限自动机(NFA)
0,1 q1 1 q2 0, q3 1 0,1 q4
1
q2
0
M1
q3
所以只需记录当前状态和读头右边的串.
0,1
(q1, 000) ˫(q1, 00) ˫(q1, 0) ˫(q1, ) 拒绝
称M1拒绝000
• M1的语言 L(M1) = { w* | M1 接受 w } = ?来自DFA计算的形式定义[S]
设M=(K,,,s,F)是一个DFA, w=w1w2…wn是字母表上的一个字符串. 若存在K中的状态序列r0,r1,…,rn, 满足 1) r0 = s; 2) (ri, wi+1) = ri+1; 3) rn F 则M接受w.
格局与机器运行([L])
• 因为有限自动机读头只右移, 读头左边符号不影响后面的计算, • 对机器M1输入1101, 计算过程记录为 (q1, 1101) ˫ (q2, 101) ˫ (q2, 01) ˫(q3, 1) ˫(q2, ) 接受 简记为(q1, 1101) ˫*(q2, ), 称M1接受1101 • 对机器M1输入000, 计算过程记录为 0 q1 1
语言举例与字典序
取字母表 = {0,1}, 上的语言举例: A={0,00,000,000000} B={1,01,11,001,011,101,111,…}
C={,0,1,00,11,000,010,101,111,…}
上所有有限长串记为*, 可数 *的字典序排列: , 0, 1, 00, 01, 10, 11, 000, … 上所有无限长串记为N, 不可数
q0
w1
r1
w2
r2
…
rn-1 wn rn
有限自动机识别的语言:正则语言
对有限自动机M, 若 A = { w* | M接受w }, 即A是有限自动机M的语言, 也称M识别A, 通常记有限自动机M的语言为L(M). 称两个有限自动机等价若它们语言相同. 0