字符串(1) 字母表: 任意非空有穷集合 (字符)串: 连接: ={0,1} ={a,b,c,…,x,y,z,空格}

字符串(1) 字母表: 任意非空有穷集合 (字符)串: 连接: ={0,1} ={a,b,c,…,x,y,z,空格}
x=01001, w=madam 连接: xw=01001madam xx=x2= 《理论计算机科学基础》

字符串(2) 串长度: |x|=5, |w|=5, |xw|=10 空串: , ||=0, x0= 子串: 子序列:
空串空格: |空格|=1 子串: ada是madam的子串子序列: m,d,m是m,a,d,a,m的子序列《理论计算机科学基础》

语言(1) * = { x | x是上有穷长度的串 } + = { x | x是上正有穷长度的串 }
《理论计算机科学基础》

语言(2) 语言: 串的集合空语言:  语言连接: A* 空串语言: {} 空串:  AB = { xy | xA且yB }
{}A=A{}=A A=A=. 《理论计算机科学基础》

标准序先短后长, 等长逐位比较 1={0,1}, 0<1
1*={, 0, 1, 00, 01, 10, 11, 000, 001,… } 2={a,b,c,…,x,y,z}, a<b<c<…<x<y<z 2*={,a,b,c,…,x,y,z, aa,ab,…,ay,az,ba,…,bz, ca,…cz,…,za,…zz,aaa,…,zzz,aaaa,…… } 《理论计算机科学基础》

商场自动门(1) 关前后《理论计算机科学基础》

商场自动门(2) 开前后《理论计算机科学基础》

商场自动门(3) 关前后《理论计算机科学基础》

商场自动门(4) 开前后《理论计算机科学基础》

自动门控制器-状态图后满空前后满前关开空《理论计算机科学基础》

自动门控制器-状态表后满空前后满前关开空空前后满关开《理论计算机科学基础》

有穷自动机状态图状态, 初始状态, 接受状态转移, 输入符号 1 1 q1 q2 q3 0,1 《理论计算机科学基础》

有穷自动机M1 1 1 q1 q2 q3 0,1 1 q1 q2 q3 《理论计算机科学基础》

M1在1101上运行 1 q1 q2 q3 单向只读输入带 $ 1 1 1 $ 单向只读头 q1 q2 q3 有穷状态控制器
1 $ 单向只读头 q1 1 q1 q2 q3 q2 q3 有穷状态控制器《理论计算机科学基础》

M1接受哪些串? 1 q1 q2 q3 1 1 q1 q2 q3 0,1 从初始状态到接受状态的路径上标注的字符串 1 0*1 0*1 1*
1 1 q1 q2 q3 1 q1 q2 q3 0,1 从初始状态到接受状态的路径上标注的字符串 1 0*1 0*1 1* 0*1 1*00 0*1 1*(00)* 0*1 1*(01)* 《理论计算机科学基础》

有穷自动机的形式定义定义2.1: 有穷自动机M=(Q,,,q0,F) L(M)={w* | (q0,w)F} Q: 有穷状态集
: 输入字母表 : QQ, 转移函数 (: Q*Q, 扩展转移函数) q0Q: 初始状态 FQ: 接受状态(终结状态) L(M)={w* | (q0,w)F} 《理论计算机科学基础》

例2.2 M2=({q1,q2},{0,1},, q1,{q2}) 1 q1 q2 1 1 q1 q2
1 1 q1 q2 1 q1 q2 L(M2) = { w | w以1结束 } 《理论计算机科学基础》

例2.3 M3=({q1,q2},{0,1},, q1,{q1}) 1 q1 q2 1 1 q1 q2
1 1 q1 q2 1 q1 q2 L(M3) = { w | w=或w以0结束 } 《理论计算机科学基础》

例2.4 a b b q1 q2 a a b a s a b r1 r2 b L(M4) = { w | w开头和结尾符号相同 }

例2.5 q1 0, <RESET> 2, <RESET> 1 q0 1 2 2 1, <RESET>
q1 0, <RESET> 2, <RESET> 1 q0 1 2 2 1, <RESET> q2 L(M4) = { w | 最后一个<RESET>之后w的数字之和是3的倍数 } 《理论计算机科学基础》

例2.6(推广例2.5)  = { 0, 1, 2, <RESET> }
Ai = { w |最后一个<RESET>之后w数字之和是i的倍数 } L(Bi)=Ai; 自动机 Bi = ? Bi = ( Qi, , i, q0, {q0} ) Qi = { q0, q1, q2, … , qi-1 } i( qk, 0 ) = qk i( qk, 1 ) = qk+1(mod i) i( qk, 2 ) = qk+2(mod i) i( qk, <RESET> ) = q0 《理论计算机科学基础》

计算的形式定义 M=(Q,,,q0,F); 计算: 状态序列r0,r1,…, rn; 接受计算: M接受w M识别(接受)的语言:
输入串w=w1w2…wn; 计算: 状态序列r0,r1,…, rn; r0=q0; (ri,wi+1)=ri+1; (i=0,1,…,n-1) 接受计算: M接受w rnF; M识别(接受)的语言: L(M)={ x | M接受x } 《理论计算机科学基础》

正则语言正则语言: L=L(M) M是有穷自动机《理论计算机科学基础》

例2.8(续例2.5) L(M5) = { w | 除了<RESET>将计数重新置0外, w符号之和模3为0 }
输入: w = 10<RESET> 22<RESET>012 计算: q0, q1, q1, q0, q2, q1, q0, q0, q1, q0 《理论计算机科学基础》

设计有穷自动机状态: 需要记住的东西转移: 根据输入符号, 从一种状态到另一种状态《理论计算机科学基础》

例 L(E1)={ w | w中有奇数个1 }, ={0,1} 《理论计算机科学基础》

例 L(E1)={ w | w中有奇数个1 }, ={0,1} qeven qodd 《理论计算机科学基础》

例 L(E1)={ w | w中有奇数个1 }, ={0,1} 1 qeven qodd 1 《理论计算机科学基础》

例2.9 L(E2)={ w | w中含有子串001 }, ={0,1} 《理论计算机科学基础》

例2.9 L(E2)={ w | w中含有子串001 }, ={0,1} q q0 q00 q001 《理论计算机科学基础》

例2.9 L(E2)={ w | w中含有子串001 }, ={0,1} 1 0,1 1 q q0 q00 q001 1
0,1 1 q q0 q00 q001 1 《理论计算机科学基础》

正则运算设A,B是两个语言,正则运算是: 定理: 正则语言对正则运算封闭. 并 AB={x | xA或xB}
连接 AB={xy | xA且yB} 星号 A*=A0A1A2A3… ={}AAAAAA… ={x1x2…xk| k0且每个xiA} 定理: 正则语言对正则运算封闭. 《理论计算机科学基础》

对补运算的封闭性定理: 正则语言对补封闭. 证明思路 1 1 q1 q2 q3 0,1 M1 1 1 q1 q2 q3 0,1 M2
1 1 q1 q2 q3 0,1 M1 1 1 q1 q2 q3 0,1 M2 《理论计算机科学基础》

对补运算的封闭性定理: 正则语言对补封闭. 证明: 设正则语言L=L(M), M=(Q,,,q0,F). 令F’=Q-F.
(q,a1…ak)=(…((q,a1),a2),…,ak) x, xL(M)  (q0,x)F  (q0,x)F’  xL(M’)  L(M’)=*-L(M)= L(M)c. # 《理论计算机科学基础》

对并运算的封闭性定理2.12: 正则语言对并封闭. 证明思路 $ 1 1 1 $ 《理论计算机科学基础》

对并运算的封闭性定理2.12: 正则语言对并封闭. 证明: 设正则语言Li=L(Mi),
Mi=(Qi,,i,qi,Fi), i=1,2. 令Q3=Q1Q2; q3=(q1,q2); 3((r1,r2),a)=(1(r1,a),2(r2,a)); F3=(F1Q2)(Q1F2). M3=(Q3,,3,q3,F3). L1L2=L(M1)L(M2)=L(M3). # 《理论计算机科学基础》

对交运算的封闭性定理: 正则语言对交封闭. 证明思路一: 推论: 布尔运算: 交, 并, 补正则语言对布尔运算封闭.
正则语言对差,对称差封闭. 《理论计算机科学基础》

对交运算的封闭性定理: 正则语言对交封闭. 证明思路二: $ 1 1 1 $ 《理论计算机科学基础》

对交运算的封闭性定理: 正则语言对交封闭. 证明: 设Li=L(Mi), Mi=(Qi,,i,qi,Fi); i=1,2.
令Q3=Q1Q2; q3=(q1,q2); 3((r1,r2),a)=(1(r1,a),2(r2,a)); F3=F1F2. M3=(Q3,,3,q3,F3). L(M3)=L(M1)L(M2)=L1L2. # 《理论计算机科学基础》

对连接运算的封闭性定理2.13: 正则语言对连接封闭. 证明思路 $ 1 1 1 1 $ 《理论计算机科学基础》

对连接运算的封闭性定理2.13: 正则语言对连接封闭. 证明思路 $ $ 1 1 1 1 $ 《理论计算机科学基础》

对连接运算的封闭性定理2.13: 正则语言对连接封闭. 证明: Mi=(Qi,,i,qi,Fi); i=1,2,3.
L(M3)=L(M1)L(M2). Q3=Q1P(Q2). 扩展定义 :P(Q)P(Q), (R,a)={(s,a)|sR}. q3=(q1,s). 3((r1,r2),a)=(1(r1,a),2(r2,a)t). {q2},若q1F {q2},若1(r1,a)F1 , 否则 ,否则. F3={ (r1,r2) | r2F2 }. # s= t= 《理论计算机科学基础》

对星号运算的封闭性定理2.24: 正则语言对星号封闭. 证明思路 $ 1 1 1 1 $ 《理论计算机科学基础》

对星号运算的封闭性定理2.24: 正则语言对星号封闭. 证明思路 $ $ 1 1 1 1 $ 《理论计算机科学基础》

对星号运算的封闭性定理2.24: 正则语言对星号封闭. 证明思路 $ $ $ 1 1 1 1 $ 《理论计算机科学基础》

对星号运算的封闭性定理2.24: 正则语言对星号封闭. 证明: ? 非确定性《理论计算机科学基础》

非确定性(nondeterminism)
确定型(deterministic)计算下一个状态是唯一确定的非确定型(nondeterministic)计算下一个状态可以不唯一确定 移动, 多种选择(含0种选择) 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

非确定型计算非确定型计算 移动和多种选择产生不同备份无法移动时, 该备份就消失有一个备份接受, 整个计算就接受 0,1 0,1 1
0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

N1在1101上计算(0) $ 1 1 1 $ q1 q4 q2 q3 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

N1在1101上计算(1) $ 1 1 1 $ q1 q1 q4 q2 q4 q2 q3 q3 0,1 0,1 1 0,  1 q1 q2
1 $ q1 q1 q4 q2 q4 q2 q3 q3 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

N1在1101上计算(2) $ 1 1 1 $ q1 q1 q1 q4 q2 q4 q2 q4 q2 q3 q3 q3 0,1 0,1 1
1 $ q1 q1 q1 q4 q2 q4 q2 q4 q2 q3 q3 q3 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

N1在1101上计算(4) q1 $ 1 1 1 $ q4 q2 q1 q1 q1 q3 q4 q2 q4 q2 q4 q2 q3 q3
1 $ q4 q2 q1 q1 q1 q3 q4 q2 q4 q2 q4 q2 q3 q3 q3 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

N1在1101上计算(0) $ 1 1 1 $ 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

N1在1101上的计算树拒绝 q1 1 q1 拒绝拒绝 q1 1 q2 q3 1 q3 q1 1 q2 q4 接受 1 1  q1
拒绝拒绝 q1 1 q2 q3 1 q3 q1 1 q2 q4 接受 1 1  q1 拒绝 1 q3 1  q2  q3 1 1 接受 q4 q4 q4 0,1 0,1 1 0,  1 q1 q2 q3 q4 《理论计算机科学基础》

N1接受的语言 L(N1) = { w | w包含子串101或11 } 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1

例2.14 L(N2)={w|w倒数第3个字母为1} ={0,1} 《理论计算机科学基础》

例2.14 L(N2)={w|w倒数第3个字母为1} ={0,1} 非确定型: 猜测倒数第3个字母 q1 q2 q3 q4

例2.14 L(N2)={w|w倒数第3个字母为1} ={0,1} 非确定型: 猜测倒数第3个字母 0,1 1 0, 1 0,1 q1

例2.14 L(N2)={w|w倒数第3个字母为1} ={0,1} 确定型: 记忆最后3个字母 q000 q100 q010 q110

例2.14 L(N2)={w|w倒数第3个字母为1} ={0,1} 确定型: 记忆最后3个字母 q000 q100 q010 q110 1
q000 q100 q010 q110 1 1 1 1 1 1 q001 q101 q011 q111 1 1 《理论计算机科学基础》

例2.14(比较) 0,1 1 0, 1 0,1 q1 q2 q3 q4 q000 q100 q010 q110 1 1 1 1 1 1 q001 q101 q011 q111 1 1 《理论计算机科学基础》

例2.15 一元字母表上语言称为筹码集(Tally Sets)   N3 《理论计算机科学基础》

例2.15 L(N3) = { 0k | k是2或3的倍数 }   N3 《理论计算机科学基础》

例2.16 N4接受, a, baba, baa, 拒绝b, bb, babba. a b q1 q2 a a, b  q3 N4

NFA的形式定义定义2.17: 非确定型有穷自动机 N = (Q,,,q0,F), 其中 Q: 有穷状态集
: 输入字母表; ( ={} ) : QP(Q), 转移函数 q0Q: 初始状态 FQ: 接受状态(终结状态) 《理论计算机科学基础》

例2.18 N1=(Q,,,q1,F); Q={q1,q2,q3,q4}; ={0,1}; F={q4}; 表 1  q1
1  q1 {q1} {q1,q2}  q2 {q3} q3 {q4} q4 0,1 0,1 1 0,  1 q1 q2 q3 q4 N1 《理论计算机科学基础》

NFA计算的形式定义 NFA N=(Q,,,q0,F) 计算: 状态序列 r0,r1,…,rm 接受计算: M接受w: 存在接受计算
输入w=w1w2…wm 计算: 状态序列 r0,r1,…,rm r0=q0 ri+1(ri,wi+1) (i=0,1,…,m-1) 接受计算: rmF M接受w: 存在接受计算 L(M)={x | M接受x} 《理论计算机科学基础》

N1在1101上的计算计算1: q1,q1,q1,q1,q1 计算2: q1,q1,q1,q1,q2
拒绝 q1 1 计算6: q1,q2 q1 计算7: q1,q2,q3,q4,q4,q4 拒绝拒绝 q1 1 q2 q3  1 q3 q1 1 q2 q4 接受 1 1  q1 拒绝 1 q3 1  q2  q3 1 1 接受 q4 q4 q4 0,1 0,1 1 0,  1 q1 q2 q3 q4 《理论计算机科学基础》

NFA与DFA的等价性等价: 两台机器识别同样的语言. 《理论计算机科学基础》

NFA与DFA的等价性等价: 两台机器识别同样的语言. 定理2.19:每台NFA都有等价DFA. 《理论计算机科学基础》

NFA与DFA的等价性定理2.19:每台NFA都有等价DFA. 证明思路: 给定NFA, 构造等价DFA 用DFA模拟NFA 闭包:
设NFA有k个状态, 则共有2k个不同状态子集合 闭包: 对每个状态子集合, 经移动可到达的新状态子集合《理论计算机科学基础》

例2.21(续例2.16) N4=({1,2,3},{a,b},,1,{1}) 求等价的DFA. 1 b a  a 2 3 a,b

例2.21 写出子集状态 1 b a  a 2 3 a,b  {1} {2} {1,2} {3} {1,3} {2,3} {1,2,3}

例2.21 求闭包 E({1})={1,3} 1 b a  a 2 3 a,b  {1} {2} {1,2} {3} {1,3}
{2,3} {1,2,3} 《理论计算机科学基础》

例2.21 添加转移 1 b a  a 2 3 a,b a,b a b  {1} {2} {1,2} b a a,b b b a a a
{3} {1,3} {2,3} {1,2,3} a b b 《理论计算机科学基础》

例2.21 初始状态接受状态不可达状态 1 b a  a 2 3 a,b a,b a b  {1} {2} {1,2} b a
{3} {1,3} {2,3} {1,2,3} a b b 《理论计算机科学基础》

例2.21 删除不可达状态 {1}, {1,2}; 1 b a  a 2 3 a,b a,b  {2} b a b b a a a
{3} {1,3} {2,3} {1,2,3} a b b 《理论计算机科学基础》

NFA与DFA的等价性定理2.19: 每台NFA都有等价DFA. 证明: 设NFA N=(Q,,,q0,F), 构造
DFA M=(Q’,,’,q0’,F’), L(M)=L(N). 令Q’=P(Q). 对RQ’和a, E(R)={q | 从R出发沿0个或多个移动可达q }; ’(R,a)=UrRE((r,a)). q0’=E({q0}). F’={RQ’ | RF}. # 《理论计算机科学基础》

推论2.20 推论2.20: 一个语言是正则的, 当且仅当有一台NFA识别它. 《理论计算机科学基础》

对正则运算的封闭性定理2.22: 正则语言对并封闭. 《理论计算机科学基础》

对并运算的封闭性定理2.22: 正则语言对并封闭. 证明思路: N N1   N2 《理论计算机科学基础》

对并运算的封闭性定理2.22: 正则语言对并封闭. 证明:设NFA Ni=(Qi,,i,qi,Fi)
识别Ai, i=1, 构造NFA N=(Q,,,q0,F)识别A1A2. 令Q=Q1Q2{q0}; F=F1F2. 《理论计算机科学基础》

对连接运算的封闭性定理2.23: 正则语言对连接封闭. 《理论计算机科学基础》

对连接运算的封闭性定理2.23: 正则语言对连接封闭. 证明思路: N1 N2 N   《理论计算机科学基础》

对连接运算的封闭性定理2.23: 正则语言对连接封闭. 证明:设NFA Ni=(Qi,,i,qi,Fi)
识别Ai,i=1,2. 构造NFA N=(Q,,,q1,F2)识别A1A2. 令Q=Q1Q2; 《理论计算机科学基础》

对星号运算的封闭性定理2.24: 正则语言对星号封闭. 证明思路: N1 N   《理论计算机科学基础》

对星号运算的封闭性定理2.24: 正则语言对星号封闭. 证明思路: N1 N    《理论计算机科学基础》

对星号运算的封闭性定理2.24: 正则语言对星号封闭. 证明思路:设 A1=L(N1), A1*=L(N),
NFA N1=(Q1,,1,q1,F1). 构造 NFA N=(Q,,,q0,F). Q=Q1{q0}; F=F1{q0}; 《理论计算机科学基础》

字符串(1) 字母表: 任意非空有穷集合 (字符)串: 连接: ={0,1} ={a,b,c,…,x,y,z,空格}

Similar presentations

Presentation on theme: "字符串(1) 字母表: 任意非空有穷集合 (字符)串: 连接: ={0,1} ={a,b,c,…,x,y,z,空格}"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

字符串(1) 字母表: 任意非空有穷集合 (字符)串: 连接: ={0,1} ={a,b,c,…,x,y,z,空格}

Similar presentations

Presentation on theme: "字符串(1) 字母表: 任意非空有穷集合 (字符)串: 连接: ={0,1} ={a,b,c,…,x,y,z,空格}"— Presentation transcript:

Similar presentations

About project

反馈