当前位置：文档之家 › 自动机与形式语言_第三章_DFA_NFA..

自动机与形式语言_第三章_DFA_NFA..

  • 格式：ppt
  • 大小：1018.00 KB
  • 文档页数：111

下载文档原格式

  / 111

合集下载

第三章有穷自动机

第三章有穷自动机

例：将图示的DFA M最小化。
a
b
6
4
a
a
a
b
a
1
ab
5a
7
b3
b
b
2 b
1、将M状态分为两个子集： P0=({1,2,3,4},{5,6,7})
2、{1,2,3,4}读入a后划为： P1=({1,2},{3,4},{5,6,7})
3、进一步划分： P2=({1,2},{3},{4},{5,6,7})
对M的状态集S进行划分的步骤：
①把S的终态与非终态分开，分成两个子集， 形成基本划分，属于这两个不同子集的 状态是可区别的。
②假定某个时候已含m个子集，记={I(1) , I(2) , …,I(m) }且属于不同子集的状态是可 区别的，再检查中的每个I能否进一步划 分，对于某个I(i) ，令I(i) ={S1,S2,…,Sk}， 若存在一个输入字符使得move(I(i) ,a)不包 含在现行的某一子集I(i)中，则将I(i)一分 为二。
若M的某些结既是初态结，又是终态结，
或者存在一条从某个初态结到某个终态结 的道路，则空字可为M所接受。
例： NFA M=({0,1,2,3,4},{a,b},f,{0},{2,4})
f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1}
f(3,a)={4} f(1,b)={2} f(4,a)={4}
M’=(K, ,f,S,Z)
一个含有m个状态和n个输入字符的NFA 可表示为一张状态转换图，该图含有m个 状态结，每个结可射出若干条 箭弧与别的 结点相连接，每条弧用*中的一个字（不 一定要不同的字，且可以为空字）作标记 （称输入字），整个图至少含有一个初态 结以及若干个终态结。

编译原理第三章_有穷自动机

编译原理第三章_有穷自动机
5
例 过河问题 分析（续）
初始状态：MWGC-φ；终止状态：φ-MWGC。 g
MWGC-φ
WC-MG
问题：
6
例 过河问题 状态转换图
起始 g
MWGC-φ g
g φ-MWGC
g
7
WC-MG
m
m MWC-G
w
w
c
C-MWG
c W-MGC
g
g
MGC-W c
MG-WC
w
m
c G-MWC
m
gg MWG-C
+dd. ddd;
输入符号串
数字 数字
SB
.
数字
+
A
H
-.
数字
.G
接收：若扫描完输入串， 且在一个终止状态上结 束。
数字 阻塞：若扫描结束但未 停止在终止状态上；或 者为能扫描完输入串 （如遇不合法符号）。
不完全描述：某些状态 对于某些输入符号不存 在转换。
练习：+34.567 .123 3.4.5
w
有穷自动机（FA）
数字系统：可以从一个状态移动到另一个状态；每次 状态转换，都上由当前状态及一组输入符号确定的；可以 输出某些离散的值集。
FA：一个状态集合；状态间的转换规则；通过读头来 扫描的一个输入符号串。
读头：从左到右扫描符号串。移动（扫描）是由状态 转换规则来决定的。
8
读头
一个FA的例子
(3)运行： 串f(，Q,且t1tt21)∈= Σf(，f(Qt1,t2t1∈), Σt2*)，其中Q∈K， t1t2为输入字符
17
例３
题：试证abba可为例1的DFA M所识别（所接受）。

形式语言与自动机总结精品PPT课件

形式语言与自动机总结精品PPT课件
–DPDA 接受非歧义文法，但并不是所有非歧 义文法都可由DPDA接受。S->0S0|1S1|e
–定理6.20,6.21空栈机、终态机与非歧义文 法
• 前缀性质与DPDA
第7章 上下文无关语言的性质
本章是重点
SUCCESS
THANK YOU
2020/12/26
7.1 上下文无关文法的范式
• 文法的化简
• ~代数定律
第4章 正则语言的性质
• 正则语言的泵引理及其应用（重点！）
第4章 正则语言的性质 对于给定的同态（或逆同态）
映射，应能计算映射后的符
• ~的封闭性
号串及语言
– 交、并、补、差、闭包（*）、连 接
– 反转
– 同态
– 逆同态
• 判定性质（各种表示之间的转换、空性、 成员性）
• 最小化（状态的等价性、最小化的填表 算法P106）
7.4 CFL的判定性质
• CFL与PDA转换的复杂度（略） • CFG变换到CNF复杂度（不要求） • 测试空性 • 测试成员性（CYK算法 P209 必须掌握） • 不可判定问题一览（参阅P211）
第8章 图灵机导引
重点
8.2 图灵机
• ~的定义 • ID: q • ~的图形表示 • ~的设计技术（必须掌握） • ~的语言 • ~作为函数（程序） • 停机问题
6.2 PDA的语言（必须掌握）
• 以终态方式接受 • 以空栈方式接受 • 从空栈方式到终态方式（包装） • 从终态方式到空栈方式 • 构造PDA技术
6.3 PDA与CFG的等价性
• 从文法到PDA（必须掌握） • 从PDA到CFG（不要求）
6.4确定型的PDA
• ~定义 • 正则语言与DPDA • DPDA与CFL • DPDA与歧义文法

3 FA 语言与自动机导论

3 FA 语言与自动机导论

A
i FA M
B
状态 A i B d F
FA f (A, i) = B f (B, i) = B f (B, d) = B (B为终止状态)
RG AiB BiB BdB Bε
B
B
B
1
状态转换矩阵
11
FA的状态转换图

状态转换图显示了一个由状态、转换组成的状态 机。
有限自动机的状态转换图说明系统的动态视图。 状态图强调一个对象按事件次序发生的行为。
22
例3.3扩：接受语言{x000 | x {0,1}*} ∪{x001 | x {0,1}*}的 FA
解：该语言定义的句子以000或001结尾。设q0为DFA的开 始状态，用q1记住结尾串中的第一个0；用q2记住在q1之 后紧接着又读到的一个0；用q3记住在q2后紧接着又读到 的一个0，用q4记住在q2后紧接着又读到的一个1，识别 该语言的FA如下图（3-5）：
则 A也作为终止状态
13
3.2 有穷状态自动机



主要内容：
1、DFA的形式化定义
2、DFA的仿真算法（伪代码描述）
14
一.有穷自动机的形式化定义
1. 确定的有穷自动机DFA
一个确定的有穷自动机DFAM是一个五元组（5-tuple）： M=（K，Σ， δ ，q0，F） 其中：K：状态的非空有穷集 Σ：有穷输入字母表 δ：K× Σ到K的一个映射（是单值函数）
q0∈K 是开始状态
F K 是终止状态集
15

例3-2：构造一个DFA，识别语言{x000y | x,y {0,1}*} 解：该语言定义的句子都会有三个连续的0。设q0为DFA 的开始状态，用q1记住子串“000”的第一个0；用q2记住 在q1之后紧接着又读到的一个0，这可能是子串“000”的 第2个0；用q3记住在q2后紧接着又读到的一个0，发现子 串“000”即识别结束。识别该语言的确定的有穷状态自 动机如下图：

《编译原理实践及应用》第3章词法分析—DFA与NFA

《编译原理实践及应用》第3章词法分析—DFA与NFA

其中 Κ ={ S 0 ,S1 ,S 2 } Σ ={a,b}
Ѕ={ S 0 , S1 } ( S0 ,a)={ S1 }
F={ S 2 }
( S 0 ,b)={ S 0 ,S 2 }
( S1 ,a)= Φ
(S1 ,b)={S 2 }
( S 2 ,a)= Φ
(S 2 ,b)={S1 }
②以每个非终结符号做其它状态
③对于形如Q→q的规则,
q
S
Q
对于形如Q→Rq的规则,
Rq Q
④以文法开始符号为终止状态。
例3-1： 文法G[Z]： Z→Za|Aa|Bb
aA
a
A→Ba|a B→Ab|b
Sb a
Za
b
Bb
2.应用状态转换图识别句子
识别句子：从开始状态到终止状态经过的边上的符号序列。 识别句子的步骤： ①从开始状态出发，以欲识别符号串的最左字符开始，寻找标
Z→Cb C→b|Bb B→Ab A→a|Ba
有限自动机(FA)
FA可看作一个机器模型，由一个带读头的有限控制器和 一条字符输入带组成。
#
a b a ba
…
输入带
控制器
工作原理：读头从左到右扫描输入带，读到一个字符，状态改
变，同时读头右移一个字符，…，直到读头读到
“#”，状态进入终止状态。
控制器中包括有限个状态，读入一个字符形成状态转换。
( S1 ,a)= S0 ( S1 ,c)= S3 ( S 2 ,b)= S1
( S3 ,b)= S3
a
b
S2 a
S0 a S1
ba
C
S3 b
定义: 所接收的语言（正则集）
L( AD)={β | S β S, S∈ F },

离散数学(形式语言与自动机)

离散数学(形式语言与自动机)

(3) 状态转移函数δ:QΣ→Q
(4) 初始状态 q0Q (5) 终结状态集 FQ
控制器
a1 a2 … ai … an
2
DFA接受的语言
把δ扩张到QΣ*上 δ*:QΣ*→Q, 递归定义如下 qQ, aΣ和wΣ*
δ*(q,ε)=q δ*(q,wa)= δ(δ*(q,w),a)
定义 wΣ*,如果δ*(q0,w)F, 则称 M接受w. M接受的字符串的全体称作M接受的语言,记作
L(M)={ wΣ*| δ*(q0 ,w)∩F≠ }
7
例2 (续)
w 1 10 101 1011 10110
δ*(q0 ,w) {q0, q1} {q0, q3} {q0, q1}
{q0, q1 , q2} {q0, q2 , q3}
L(G) = { x00y, x11y | x,y{0,1}*}


1 {q0}
{q0} {q0} {q0}

10
模拟实例 (续)
不可达状态:从初始状态出发永远不可能达到的状态 删去所有的不可达状态, 不会改变FA接受的语言. 如M中的{q1},{q2},{q0,q2},{q1,q2}和都是不可达状态, 删去这些状态得到M
δ
0
1
→{q0} {q0, q1} {q0} {q0,q1} {q0,q1,q2} {q0} *{q0,q1,q2} {q0,q1,q2} {q0}
若δ(q,a)=p, 则有产生式q→ap 若qF, 则有产生式q→ε
20
模拟实例
DFA M
δ01 →q0 q1 q0
q1 q2 q1 *q2 q0 q2
G =V,T,S,P
V={q0,q1,q2}, T={0,1}, S= q0 P: q0→0q1 q0→1q0

形式语言与自动机 形式语言与自动机理论-蒋宗礼-第三章参考答案

形式语言与自动机形式语言与自动机理论-蒋宗礼-第三章参考答案导读：就爱阅读网友为您分享以下“形式语言与自动机理论-蒋宗礼-第三章参考答案”的资讯，希望对您有所帮助，感谢您对的支持!因此我们只需要证明对任何的2NFA M1?(Q1,?,?1,F1,q0)，都存在FAM2?(Q2,?,?2,F2,q0)与之等价。

对于任何的2NFA M1?(Q1,?,?1,F1,q0)，构造FA M2?(Q2,?,?2,F2,q0)，按三个方式构造?2：1．如果q?Q1,a??,?1(q,a)?{p,R},则?2(q,a)?p；2．如果q?Q1,a??,?1(q,a)?{p,S},则如果??1(p,a)?{o,R}，则?2(q,a)?o；如果??1(p,a)?{o,S}，则重复第二步；如果??1(p,a)?{o,L}，则对于集合A = {r|b?Q1,?1(r,b)?(o,R)}，?2(q,a)?r,r?A。

3．如果q?Q1,a??,?1(q,a)?{p,L},则设集合 A = {r|b?Q1,?1(r,b)?(p,R)}，?2(q,a)?r,r?A*************************************************** ****************************28．证明定理3-8：Moore机与Mealy机等价（郭会02282015）证明：不妨设Moore机M1=(Q1,?,?,?1,?1,q01)，Mealy机M2=(Q2,?,?,?2,?2,q02)，则根据Moore机和Mealy机等价的定义知，必须证明：T1(x)??1(q0)T2(x),其中T1(x)和T2(x)分别表示M1和M2关于x的输出。

??Moore机M1,?Mealy机M2,使M2与M1等价（1）构造M2，?2??1,q02?q01,Q2?Q1?q?Q1?{q01},?1(q)?a,?q'?Q1且?b??,?1(q',b)=q,就构造?2（q',b）=a（2）证明?x??*，?1(q0)T2(x)?T1(x)不妨设x?x1x2……xn,则?i?N,(i?1,2……n)则M1的输出为:T1(x)??1(q0)?1(?1(q0,x1))……?1(?1((…?1(q0,x1)，x2)…)，xn)由题意可知?1(q0,x1)，?1(?1(q0,x1),x2)，…，?1(……?1 (?1(q0,x1),x2) xn) 均为Moore机中的状态，由（1）中的构造假设知，M2的输出为：T2(x)??2(q0,x1)?2(?2(q0,x1),x2)…?2(……?2(?2(q0,x1),x2) ? ?1(q0,x1)?1(?1(q0,x1),x2)…?1(……?1(?1(q0,x1),x2) xn) xn) ?T1(x)??1(q0)T2(x)??Mealy机M2,?Moore机M1,使M1与M2等价（1）构造M1，q01?q02Q1?Q2?{qij|??2(qi,a)?qj,其中qi,qj?Q2,a??}?1?{?|?(qi,a)?qij,?(qij,?)?qj其中?2(qi,a)?qj}?1?{?|?1(qi,a)?qij,?1(qij,?)?qj,?(qij)??2(qi,a) }（2）证明?x??*，T1(x)＝?1(q0)T2(x)不妨设x?x1x2……xn,则?i?N,(i?1,2……n)则M1的输出为:T2(x)??2(?2(q0,x1))……?2(?2((…?2(q0,x1)，x2)…)，xn) 由题意可知?2(q0,x1)，?2(?2(q0,x1),x2)，…，?2(……?2 (?2(q0,x1),x2) xn) 均为Mealy机中的状态，由（1）中的构造假设知，M1的输出为：T1(x)??1(q0)?1(?2(q0,x1))?1(?1(q0,x1),x2)…?1(……?1(?1(q 0,x1),x2) xn)??1(q0)?2(?2(q0,x1))……?2(?2((…?2(q0,x1)，x2)…)，xn) ?T1(x)??1(q0)T2(x)综上所述，Moore机与Mealy机等价第三章作业答案1．已知DFA M1与M2如图3－18所示。

自动机与形式语言epsilonNFA介绍

3
3.4 带空移动的有穷状态自动机
• 接受语言{0n1m2k|n，m，k≥0}的NFA是否可 以构造成下图所示的“ε-NFA ”？
其构造显然比图1-13所示的NFA更容易。 当然还希望它们是等价的。
2020/5/22
4
例子: ε-NFA
ε
1
1
1
B
C
D
A εε
0
0
E
F
0
0 1ε
A {E} {B} ∅ B ∅ {C} {D} C ∅ {D} ∅ D∅ ∅ ∅ * E {F} ∅ {B, C} F {D} ∅ ∅
2020/5/22
20
3.4 带空移动的有穷状态自动机
• 与上图ε-NFA等价的NFA。
2020/5/22
21
3.5 FA是正则语言的识别器
3.5.1 FA与右线性文法
• DFA M=(Q，∑，δ，q0，F)，处理句子 a1a2…an的特性。
⑴ M按照句子a1a2…an中字符的出现顺序， 从开始状态q0开始，依次处理字符a1、 a2、…、an，在这个处理过程中，每处理一 的字符进入一个状态，最后停止在某个终 止状态。
包含接受状态。
13
3.4 带空移动的有穷状态自动机
• 对任意(P，a)∈2 Q×∑。
(5) (P, a) (q, a)
qP
(6)ˆ(P, w) ˆ(q, w)
qP
2020/5/22
14
3.4 带空移动的有穷状态自动机
• 在ε-NFA中，对任意a∈∑，q∈Q，
ˆ(q, a) (q, a)
16
Байду номын сангаас.4 带空移动的有穷状态自动机
• M接受(识别)的语言 对于x∈∑*，仅当

形式语言自动机理论基础


Ch2 形式语言自动机理论基础
2.2 自动机基础
2.2.1 确定的FA（DFA）
例如， 1） 电梯的控制系统； 2） 人的大脑也是有限控制系统； （235） 3） 计算机自身也是有限控制系统。 注意： 1） DFA是具有离散输入、输出系统的一个纯数 学模型； 2） DFA的技巧在于状态的设置； 3） DFA映射的唯一性和初态的唯一性 。
NFA M=（{q0, q1, q2, q3, q4},{0,1}, f , {q0}, { q2,q4}） S ∑ S0 Z 其中状态转换函数f为： f（q0，0）= q0 f（q0，1）= q0 f（q1，0）= Φ f（q2，0）= q2 f（q3，0）= q4 f（q4，0）= q4 f（q0，0）= q3 f（q0，1）= q1 f（q1，1）= q2 f（q2，1）= q2 f（q3，1）= Φ f（q4，1）= q4
Ch2 形式语言自动机理论基础
2.2 自动机基础
2.2.3 NFA确定化
子集法
对NFA M’ =（S, {∑1, ∑2, … , ∑n }, f, S0, Z） 设一矩阵形式的表：
I ε-closure(S0) I ∑1 I∑2 … I∑n
Step1:初始化
Ch2 形式语言自动机理论基础
2.2 自动机基础
40ch2形式语言自动机理论基础22自动机基础224dfa的化简41ch2形式语言自动机理论基础22自动机基础224dfa的化简所谓dfam的化简是指寻找一个状态数比较少的dfa使得lmlm?而且可以证明存在一个最少状态的dfadfam最小化的过程是把m的状态集q分割成一些互不相交的子集使得每个子集中任何两个状态是等价的而任何属于两个不同子集的状态都是可区别的

编译原理：第3章 有穷自动机

编译原理第3章内容简介学习目标第3章有穷自动机3.1 有穷自动机的形式定义3.1 有穷自动机的形式定义DFA的表示举例——状态转换表DFA的表示举例——状态转换图 3.13.1 FA的形式定义有穷自动机识别的符号串举例DFA A3.1 有穷自动机的形式定义 3.1 有穷自动机的形式定义NFA举例 3.13.1用NFA识别符号串yFA的构造FA的构造举例—1FA的构造举例—2FA的构造举例—3请构造一个有穷自动机FA的构造举例—4 3.1请构造一个有穷自动机FA的等价性举例3.2 NFA到DFA的转换 3.2 NFA到DFA的转换—NFA确定化3.2 NFA到DFA的转换3.2 NFA到DFA的转换—NFA确定化——ε闭包状态子集I的ε闭包——举例状态子集I的状态子集I的ε闭包——举例状态子集I的——Ia 子集3.2 NFA到DFA的转换Ia子集——举例Ia子集——举例 3.2 NFA到DFA的转换NFA到DFA的转换——子集法NFA=（Q NFA到DFA的转换——举例1aNFA到DFA的转换——举例2NFA DFA DFA NFA DFA DFADFA化简举例1DFA化简——注意NFA到最小化DFA的转换——举例33.3 正规文法与FA3.3 正规文法与FAFA⇒右线性正规文法FA⇒右线性正规文法——举例1y3.4 正规表达式RE与FA 正规表达式与有穷自动机3.4 RE与FA——RE的性质 3.4 RE与FA—RE⇒FARE⇒FA举例1RE⇒FA举例23.4 RE与FA——FA⇒RE FA⇒REFA⇒RE FA⇒RE举例FA⇒RE举例正规文法到正规表达式正规文法到正规表达式DFA的程序实现DFADFA的程序实现DFA DFA的程序实现lDFA的程序实现l第3章内容小结第3章内容小结参考文献。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2018/10/6
7
3.1 语言的识别
• ⑶ 系统在任何一个状态(当前状态)下，从 输入字符串中读入一个字符，根据当前状 态和读入的这个字符转到新的状态。当前 状态和新的状态可以是同一个状态，也可 以是不同的状态；当系统从输入字符串中 读入一个字符后，它下一次再读时，会读 入下一个字符。这就是说，相当于系统维 持有一个读写指针，该指针在系统读入一 个字符后指向输入串的下一个字符。
– 定义。 – ε-NFA与DFA的等价性。
• FA是正则语言的识别器
– 正则文法(RG)与FA的等价性。 – 相互转换方法。 – 带输出的有穷状态自动机。 – 双向有穷状态自动机。
2018/10/6 2
第3章 有穷状态自动机
• 重点：DFA的概念，DFA、NFA、ε-NFA 、 RG之间的等价转换思路与方法。 • 难点：对 DFA概念的理解，DFA 、RG 的构 造方法， RG与FA的等价性证明。
2018/10/6 12
3.2有穷状态自动机
δ——状态转移函数(transition function)， 有时候又叫做状态转换函数或者移动函数。 δ：Q×∑Q，对(q，a)∈Q×∑，δ(q， a)=p表示：M在状态q读入字符a，将状态 变成p，并将读头向右移动一个带方格而指 向输入字符串的下一个字符。 F——FQ，是M的终止状态(final state)集 合。q∈F，q称为M的终止状态，又称为 接受状态(accept state)。
q0 q1
q2
q1 q2
q1
14
3.2有穷状态自动机
• 例 3-1 下面是一个有穷状态自动机 M1=({q0，q1，q2}，{0}，δ1，q0，{q2}) 其中，δ1(q0,0)= q1，δ1(q1,0)= q2，δ1(q2,0)= q1
s
q0
0
q1
0 0
q2
2018/10/6
15
3.2有穷状态自动机
2018/10/6
5
3.1 语言的识别
• 系统识别语言{anc|n≥1}∪{and|n≥1}的字符 串过程中状态的变化图示如下：
2018/10/6
6
3.1 语言的识别
• 识别系统(模型) • ⑴ 系统具有有穷个状态，不同的状态代表 不同的意义。按照实际的需要，系统可以 在不同的状态下完成规定的任务。 • ⑵ 我们可以将输入字符串中出现的字符汇 集在一起构成一个字母表。系统处理的所 有字符串都是这个字母表上的字符串。
2018/10/6
3
到目前为止，我们学了什么？
• 文法：语言的产生
– RG, CFG, CSG, PSG – 对应的语言：RL, CFL, CSL, PSL
• FA：语言的识别
DFA NFA ε-NFA RE RG
2018/10/6
正则语言 (RL)
4
3.1 语言的识别
• 推导和归约中的回溯问题将对系统的效率产 生极大的影响 SaA|aB AaA|c BaB|d 分析句子aaac 的过程中可能需要回溯。
第3章 有穷状态自动机
• 主要内容 • 确定的有穷状态自动机(DFA)
– 作为对实际问题的抽象、直观物理模型、形式 定义，DFA接受的句子、语言，状态转移图。
• 不确定的有穷状态自动机(NFA)
– 定义； – NFA与DFA的等价性；
2018/10/6
1
第3章 有穷状态自动机
• 带空移动的有穷状态自动机(ε-NFA)
2018/10/6 13
3.2有穷状态自动机
• 例 3-1 下面是一个有穷状态自动机 M1=({q0，q1，q2}，{0}，δ1，q0，{q2}) 其中，δ1(q0,0)= q1，δ1(q1,0)= q2，δ1(q2,0)= q1 用表3-1表示δ1。
状态说明 状态 输入字符 0
开始状态
终止状态
2018/10/6
2018/10/6 8
3.1 语言的识别
• ⑷ 系统中有一个状态，它是系统的开始状 态，系统在这个状态下开始进行某个给定 句子的处理。 • ⑸ 系统中还有一些状态表示它到目前为止 所读入的字符构成的字符串是语言的一个 句子，把所有将系统从开始状态引导到这 种状态的字符串放在一起构成一个语言， 该语言就是系统所能识别的语言。
2018/10/6 9
3.1 语言的识别
• 相应的物理模型
一个右端无穷的输入带。 一个有穷状态控制器(finite state control,FSC) 。 一个读头。
• 系统的每一个动作由三个节拍构成：读入 读头正注视的字符；根据当前状态和读入 的字符改变有穷控制器的状态；将读头向 右移动一格。
2018/10/6 10
3.1 语言的识别
• 有穷状态自动机的物理模型
2018/10/6
11
3.2有穷状态自动机
• 有穷状态自动机(finite automaton,FA) M=(Q，∑，δ，q0，F) Q—— 状态的非空有穷集合。 q∈Q ， q 称为 M的一个状态(state)。 ∑——输入字母表(Input alphabet)。输入字 符串都是∑上的字符串。 q0——q0∈Q，是M的开始状态(initial state)， 也可叫做初始状态或者启动状态。
2018/10/6
16
3.2有穷状态自动机
表3-2 δ 2转换函数 状态说明 开始状态 终止状态 状态
0
输入字符
1 2
q0
q1
q1
q2
q3
q3
q3
q3
q2
q3
q1
q3
q3
q3
q3
q3
17
2018/10/6
3.2有穷状态自动机
1,2 s 0 0 0 1,2
q0
q1
q2
1,2
q3
0,1,2
2018/10/6
18
3.2有穷状态自动机
• 将δ 扩充为
* ˆ : Q Q对任意的q∈Q，w∈∑* Nhomakorabeaa∈∑，定义
ˆ ( q, ) q (1) ˆ(q, wa ) ( ˆ(q, w), a) (2)
M2=({q0，q1，q2，q3}，{0，1，2}，δ 2，q0，{q2}) δ 2(q0,0)= q1，δ 2(q1,0)= q2 δ 2(q2,0)= q1，δ 2(q3,0)= q3 δ 2(q0,1)= q3，δ 2(q1,1)= q3 δ 2(q2,1)= q3，δ 2(q3,1)= q3 δ 2(q0,2)= q3，δ 2(q1,2)= q3 δ 2(q2,2)= q3，δ 2(q3,2)= q3