当前位置：文档之家 › 形式语言与自动机理论二

形式语言与自动机理论二

  • 格式：ppt
  • 大小：230.00 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

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

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

2．1回答下面的问题： （周期律 02282067）（1）在文法中，终极符号和非终极符号各起什么作用？✓ 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语言中字符的范围。

✓ 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。

（2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？✓ 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式中关于A 的产生式推导实现的✓ 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ）={w S T w w **|⇒∈且}（3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？✓ 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句型的语言。

（4）文法中的归约和推导有什么不同？✓ 推导：文法G = {V ，T ，P ，S}，如果,)(,,*Y T VP ∈∈→δγβα则称γαδ在G 中推导出了γβδ。

✓ 归约：文法G = {V ，T ，P ，S}，如果,)(,,*Y T VP ∈∈→δγβα则称γβδ在G 中归约到γαδ。

✓ 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下（从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。

（5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？✓ 非空：根据字母表幂的定义：εε,}{0∑=为字母表中０个字符组成的。

形式语言与自动机基础PPT课件

形式语言与自动机基础PPT课件

f(qoe,0)= qee f(qoe,1)= qoo f(qeo,0)=qoo f(qeo,1)= qee
f（ qeo ,1）= qeeZ
所以串$1= 110101可以被M1接受。
f(qoo,0)=qeo f(qoo,1)= qoe
f（ qee , 110101 ）= f(f（ qee ,11010）,1)=
Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA)
一. NFA的定义
DFA的确定性表现在其映射函数是一个单值函 数。但是实际问题中，映射函数往往是一个多值函 数。
例如，源程序中扫描到一个字母时，不同的语言 对应多种情况：
FORTRAN中： 标识符/格式转换码E、D…
Ch2 形式语言自动机理论基础 2.2 自动机基础
第 2 章 形式语言与自动机基础
2.2 有限自动机基础 2.2.1 确定的有限状态自动机(DFA) 2.2.2 非确定的有限状态自动机(NFA) 2.2.3 NFA确定化 2.2.4 DFA化简
Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）
Q
q0
Z
其中状态转换函数f为：
f（q0，0）= {q0,q3}
f（q1，0）=
f（q2，0）= {q2} f（q3，0）= {q4} f（q4，0）= {q4}
f（q0，1）= {q0, q1} f（q1，1）={ q2} f（q2，1）= {q2}
f（q3，1）=
f（q4，1）={ q4}
Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA)
1) p0＝q0 2) f（pi，wi＋1）＝pi＋1，i＝0，1，，n－1 3) pnZ

形式语言与自动机理论第二章蒋宗礼

形式语言与自动机理论第二章蒋宗礼
第18页/共106页
2.2 形式定义
• P——为产生式(production)的非空有穷集合。P中的元素均具有 形式αβ，被称为产生式，读作：α定义为β。其中 α∈(V∪T)+，且α中至少有V中元素的一个出现。β∈(V∪T)*。 α称为产生式αβ的左部，β称为产生式αβ的右部。产生 式又叫做定义式或者语法规则。
A1A }，A)。
第20页/共106页
2.2 形式定义
⑸ ({S ， A ， B ， C ， D},{a ， b ， c ， d,#} ， {SABCD ， Sabc# ， AaaA ， ABaabbB ， BCbbccC，cCcccC，CDccd# ，CDd#， CD#d}，S)。
⑹ ({S},{a ， b} ， {S00S ， S11S ， S00 ， S11}，S)。
第32页/共106页
2.2 形式定义
• 例 2-5 设G=({S，A，B}，{0，1}，{SA|AB，A0|0A，B1|11}，S)
对于n≥1，
A n 0n
首先连续n-1次使用产生式；A0A， 最后使用产生式A0；
A n 0nA
连续n次使用产生式A0A；
B1
使用产生式B1；
B 11
使用产生式B11。
• CFL
• CFG(CNF、GNF)、PDA、CFL的性质。
• TM
• 基本TM、构造技术、TM的修改。
• CSL
• CSG、LBA。
第4页/共106页
教材及主要参考书目
1.蒋宗礼，姜守旭. 形式语言与自动机理论. 北京：清华大学出版 社，2003年
2.John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001

形式语言与自动机_课件_陈有祺第02章 文法的一般理论

形式语言与自动机_课件_陈有祺第02章 文法的一般理论

的情况。若从S出发，先用第一个产生式ｎ-1次，即S aSb
aaSbb … an-1S bn-1，最后再使用第二个产生式一次，得
到S
aｎbｎ，这个推导对于任何ｎ>1都是对的。再加上ｎ=1的
情况，即可得到L(G)＝{an bn∣n≥1 }。
文法语言
例2.9 给出文法G，它的产生式是：
S→aB∣bA
形式文法与形式语言
例2.4 下面的各四元组都是文法。
① G1 = ({A, B}, {0,1},{A→0B, B→1B, B→0}, A)。
② G2 =( {A,B,C},{a,b,C},{A→aBC, B→b, C→CC, C→ε}, A)。
③ G3=( {L,M,N}, {0,1,2}, { M→0LN, L→1, 0L→2, LN→12，N→0}，M)。
其他的符号如：iF,tHEn,ElsE,；,:=,<，>,+,-,*,/， a,b,C,x,y,z,等等都是构成语言的基本符号，也就是 字母表中的符号。
第五条规则关于<语句表>的定义，这是一种递归的 定义形式。
问题的提出
例2.2 根据例2.1中的各规则，我们指出下述的字符串 wHilE x≤5 Do x := (x+2) 是一个合法的语句。
形式文法与形式语言
例2.5 对例2.3 中 给出的文法用定义2. 1加以规范化。其四 元组表示就是： （{<SEntEnCE>，<Noun pHrasE>，<DEtErminEr>， <Noun>, <VErb pHrasE>, <VErb>}, {tHE, a, applE, Cat, man, Eats, sinGs, runs}, {<SEntEnCE>→<Noun pHrasE><VErb pHrasE>, <Noun pHrasE>→<DEtErminEr><Noun>, <DEtErminEr>→tHE, <DEtErminEr>→a, <Noun>→applE,<Noun>→Cat,<Noun>→man, <VErb pHrasE>→<VErb><Noun pHrasE>, <VErb pHrasE>→<VErb>, <VErb>→Eats,<VErb>→sinGs,<VErb>→runs}, <SEntEnCE>）

形式语言与自动机理论第二版教学设计

形式语言与自动机理论第二版教学设计

形式语言与自动机理论第二版教学设计介绍形式语言与自动机理论是计算机科学中的基础学科之一。

自动机是指能够对输入符号进行处理的计算机模型，形式语言是指一种基于符号的语言，用来描述系统或计算过程的规则。

本文档将介绍形式语言与自动机理论第二版的教学设计。

目标通过本次教学，学生应该能够掌握以下知识：1.形式语言和自动机的基本概念2.正则表达式和有限自动机的等价性3.上下文无关文法和下推自动机的等价性4.图灵机的概念和应用5.不可判定性问题和带限图灵机的概念和应用教学方式本课程采用拓扑学习法进行教学。

教学流程如下：1.把形式语言和自动机的基本概念进行系统讲解，包括有限自动机的概念和确定性有限自动机的概念，同时介绍正则表达式和有限自动机的等价性。

2.介绍上下文无关文法和下推自动机的概念，并讲解它们与图灵机的关系。

3.介绍图灵机及其应用，包括图灵机的概念、语言的可判定性和不可判定性问题以及带限图灵机的概念和应用。

4.课程设计，安排课程实验等辅助活动，加强实践操作，辅助学生掌握理论知识。

教学内容形式语言和自动机的基本概念形式语言和自动机是理解计算机科学中的许多核心概念的必要基础。

本课程的第一部分将讲解形式语言和自动机的基本概念，主要包括以下几个方面：1.什么是形式语言？2.什么是自动机？3.有限自动机的概念和有限自动机的种类4.确定性有限自动机和非确定性有限自动机5.正则表达式和有限自动机上下文无关文法和下推自动机上下文无关文法和下推自动机是计算机科学中另外一组重要的概念。

上下文无关文法是一类可以用来描述形式语言的语法，下推自动机则是一种可以对任何上下文无关文法生成的句子进行处理的自动机。

本课程的第二部分将涵盖以下内容：1.上下文无关文法和下推自动机的概念和定义2.上下文无关文法和下推自动机的等价性3.特殊上下文无关文法和下推自动机的应用图灵机和不可判定性问题图灵机是理论计算模型，类比于通用计算机，但是其仍然有着其基本限制——不可判定性问题。

形式语言与自动机理论第二版教学大纲

形式语言与自动机理论第二版教学大纲

形式语言与自动机理论第二版教学大纲课程简介该课程主要介绍形式语言、自动机和计算复杂性理论的基本知识。

通过学习这些理论，学生将能够理解计算机语言和计算的本质，以及计算机处理问题时的优劣势和限制。

本课程将重点介绍自动机的概念、使用和应用。

学习目标•理解形式语言和自动机的基本概念和术语，如有限状态自动机、正则语言、上下文无关文法等。

•学习计算复杂性理论的基本知识，理解P、NP等复杂度概念。

•掌握自动机模型的使用和应用，能够构造和证明特定自动机模型的特性和性质。

课程内容第一章：形式语言与自动机•形式语言和自动机的基本概念和术语•正则语言和正则表达式•上下文无关文法和上下文无关语言•上下文有关文法和上下文有关语言第二章：有限状态自动机•有限状态自动机的定义和运作原理•正则语言和有限状态自动机的等价性•正则表达式到有限状态自动机的转换•有限状态自动机的最小化问题第三章：上下文无关文法和语言•上下文无关文法的定义和特点•文法的基本组成部分：终结符、非终结符和产生式•上下文无关语言和上下文无关文法之间的关系•Chomsky范式和柯尔莫戈洛夫复杂度下限第四章：推导树和语法分析器•推导树的概念和用途•自下而上（LR分析器）和自上而下分析器（LL分析器）的概念和区别•LR、LL分析器的构造算法第五章：上下文有关文法和语言•上下文有关文法的定义和特点•上下文有关语言和上下文有关文法之间的关系•推导和语言识别•非概率上下文有关文法和语言第六章：计算复杂性理论•P、NP问题的定义和区别•NP问题的证明方法：证书、多项式可验证和非确定图灵机•NP完全问题和可还原性的概念•NP问题的P约简和相对问题第七章：图灵机及其变体•图灵机的概念和基本结构•图灵机的相对能力•图灵机的变体：可计数和带计数的图灵机•智能计算和互模拟教学方法本课程将采用讲授、课堂互动、案例分析等多种教学方法，以帮助学生更好地理解理论和应用。

在每章节结束时，还将提供一些简单的练习题和课后作业，以帮助掌握相关的理论和算法。

蒋宗礼送形式语言与自动机理论-资料


2019/10/15
19
补集(Complementary Set)
A是论域U上的一个集合，A补集是由U中的、 不在A中的所有元素组成的集合
AUA
U
U
9/10/15
20
补集(Complementary Set)
如果AB，则 B A
AAU
AA
B A A B U & A B
2019/10/15
8
1.1.2 集合之间的关系
•集合相等
– 如果集合A，B含有的元素完全相同，则称集 合A与集合B相等(Equivalence)，记作A=B。
•对任意集合A、B、C： ⑴ A=B iff AB且BA。 ⑵ 如果AB，则|A|≤|B| ⑶ 如果AB，则|A|≤|B|。 ⑷ 如果A是有穷集，且AB，则|B|>|A|。
2019/10/15
12
交(Intersection)
• ⑷ A∩B=A iff A B • ⑸ Φ∩A=Φ • ⑹ |A∩B|≤min{|A|，|B|} • ⑺ A∩(B∪C)=(A∩B)∪(A∩C) • ⑻ A∪(B∩C)=(A∪B)∩(A∪C) • ⑼ A∩(A∪B)=A • ⑽ A∪(A∩B)=A
2019/10/15
30
1.2.3递归定义与归纳证明
• 归纳证明
– 与递归定义相对应
– 归纳证明方法包括三大步
• 基础(Basis)：证明最基本元素具有相应性质
• 归纳(Induction)：证明如果某些元素具有相 应性质，则根据这些元素用所规定的方法得 到的新元素也具有相应的性质。
• 根据归纳法原理，所有的元素具有相应的性 质
形式语言与自动机理论

《编译原理》.第二章形式语言与自动机理论基础（ＰＤＦ）

7
2、有关正规式及正规集的说明
说明：
1. 正规式与相应的正规集是等价的，正 规集给出了相应正规式所描述的全部单 词（句子）；
2. 正规式的运算结果是正规集；
3. 正规式不是集合，其运算结果正规集 是集合。Ф是特例。
8
正规表达式及正规集
正规表达式的定义
是字母表
正规表达式 1. ， 2. a , a 3. 若 r, s 则 (1) (r)(s)
例 (r) •((s)*)|(r)——可简写：r •s*|r。 • 常常可省略不写，可写成 rs*|r。
10
例题
=a,b, 上的正规式和对应的正规集是：
正规式
正规集
(a) a b
a,b
(b) (a b )(a b )
aa,ab,ba,bb
(c) a*
,a,aa,aaa,aaaa,…
(d) (a b)*
终态Z
Z →
3
NFA的状态图如图所是，求其等价的正规文法（右线性）
a
a S
b
A
a
Z
b
G[S]: S→aS|bS S→aA A→aZ|bZ Z →
4
2.3.1正规文法与有限自动机(FA)
2、由正规文法构造等价的NFA 文法的终结符号集为有穷自动机的字母表 文法的非终结符号集为有穷自动机的状态集 文法的开始符号作为有穷自动机的初态 对文法中形如A→tB的产生式，构造有穷自动机的一个 转换函数f(A,t)=B, 对文法中形如A→t的产生式，构造有穷自动机的一个 转换函数f(A,t)= Z
a
r1
r2 b
r3
c
r
r*
代之以
a
b
c

形式语言与自动机课后习题答案部分


– 产生语言{0x|x{0, 1}*}的文法
• S0A；
– G: S0A A|0A|1A
2013-7-24 (C)Guohong Fu, CS@HLJU 11
G F H
课后作业二 (cont.)
• 习题8(3)的解答
– 分析：语言的特点
• {11x11|x*}{111, 11}；
– 产生语言{x|x{0, 1}*}的文法
G F H
课后作业二 (cont.)
• pp.84：习题 8
设={0, 1}，构造产生下列语言的文法 (1) 所有以0开头的串； (3) 所有以11开头，以11结尾的串；
• 8(1)解答
– 分析语言的特点: {0x|x{0, 1}*}； – 产生子语言{x|x{0, 1}*}的文法
• A|0A|1A；
– 习题 15(1) --- -NFANFA
2013-7-24
(C)Guohong Fu, CS@HLJU
20
G 课后作业四 (cont.) F H pp.128 习题 11(1) 构造与NFA M等价的DFA M
2013-7-24 (C)Guohong Fu, CS@HLJU 2
G F H – – – –
课后作业一
• pp.39-41：L基本概念
习题 21 ---字母表 习题 22 --- 前/后缀 习题 23 --- 前/后缀 习题 28(1)(2)(10) --- L的描述
2013-7-24
(C)Guohong Fu, CS@HLJU
用自然语言描述下列文法定义的语言
G: AaaA|aaB BBcc|D#cc DbbbD|#
• 解题思路
– 观察每个产生式及其组合产生的子语言的特点； – 根据开始符的产生式将它们并起来就是整个文法产生的语言；

第二章 形式语言与自动机理论


上下文无关文法（CFG）
定义为四元组(VT,VN,S,P)



VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S VN P是产生式的集合，且具有下面的形式： AX1X2…Xn 其中AVN，Xi (VTVN) ，右部可空。

推导：如果A是一个产生式，则有 A ,其中表示一步推导(用A →)。 这时称是由A直接推导的。 的含义是， 使用一条规则，代替左边的某个符号，产 生右端的符号串
第二章 形式语言与自动机理论
主要内容： 文法及文法二义性 文法等价变换 DFA与NFA等价性 DFA化简 正则表达式
2.1 语言和文法
基本概念
字母表 符号串 符号串的连接 符号串的方幂 前缀和后缀 子字符串 符号串集合

符号串集合的乘积 符号串集合的方幂 符号串集合的正闭包 符号串集合的星闭包 语言 给定字母表∑，则 ∑ 上任一字符串集合就 是∑上的一个语言
删除状态S2。

状态分离法
初始化为两个不等价状态集组：非终止状态 组和终止状态组。 对每组中的某个状态分离出与之不等价的状 态组，直至所有状态组内部状态都等价为止

二义性文法
二义性文法：如果一个句型有两棵不同
的语法分析树，则称其文法具有二义性 文法G=( {+,*,I,(,)}, {E}, E, P),其中P为： Ei EE+E EE*E E(E)
E E E * + E E i E i
E * E E + E
i
i
i
i
推导1的语法树 句型i*i+i: 推导1:
NFA到DFA的转换（子集法）
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

q0
qf
q0 q0 a qf
第四章 正规表达式
定理：每个正规表达式 r 都存在一个-NFA M 使得L(M) = L(r)。
(2)运算符个数不为0
r=r1+r2
q1 M1 f1
q0
q2 M2 f2
f0
第四章 正规表达式
定理：每个正规表达式 r 都存在一个-NFA M 使得L(M) = L(r)。
正规语言类在代换下是封闭的。
第五章 正规语言的性质
5.2 正规语言的封闭性
(5) 同态
定义：设，是两个字母表，映射 f: *
如果对x,y*,有f(xy)=f(x)f(y)， 则称f是从到*的同态映射。
正规语言在同态和逆同态下是封闭的。
第五章 正规语言的性质
5.2 正规语言的封闭性
定义：假设L1,L2 *,则L1和L2的商定义 为： L1/L2={x|yL2，使得xyL1}
形式语言与自动机理论
山东大学计算机科学与技术学院 2007.3
第四章 正规表达式
4.1 正规表达式的形式定义
❖ 定义：设是一个字母表，字母表上正规式 （Regular Expression,RE）和正规集定义如下： （1）是上的正规式，对应的正规集为； （2） 是上的正规式，对应的正规集为{}； （3）对a，a是上的正规式，对应的正规
正规语言在商运算下是封闭的。
第五章 正规语言的性质
5.3 Myhill-Nerode定理和 DFA 极小化
一、相关概念 1、等价关系 2、划分 3、划分加细 4、等价类 5、商集 6、等价关系的指数
第五章 正规语言的性质
5.3 Myhill-Nerode定理和 DFA 极小化
二、 Myhill-Nerode定理
5.2 正规语言的封闭性
(1) 正规语言在并、乘积、闭包运算下是封 闭的；
(2) 正规语言类在补运算下是封闭的；
(3) 正规语言类在交运算下是封闭的；
第五章 正规语言的性质
5.2 正规语言的封闭性
(4) 代换
定义：设，是两个字母表，映射 f: p(*) 称为到的代换。 如果对a,f(a)是上的RL，则称f是 正则代换或正规代换。
(2)运算符个数不为0
r=r1r2
q1 M1 f1
q2 M2 f2
第四章 正规表达式
定理：每个正规表达式 r 都存在一个-NFA M 使得L(M) = L(r)。
(2)运算符个数不为0
r=r1*
q0
q1 M1 f1
f0
第四章 正规表达式
4.2 正规表达式与FA的等价
定理：设 L 是被 DFA M 接受的语言，则 L 可以被正规表达式表示。
第四章 正规表达式
4.2 正规表达式与FA的等价
假设 r 是上的正规式，M 是一个 FA。若 L(r)= L(M)，则称正规式 r 与 FA M 等价。
第四章 正规表达式
4.2 正规表达式与FA的等价 定理：每个正规表达式 r 都存在一个-NFA M
使得L(M) = L(r)。
(1)运算符个数为0
集为{a}；
第四章 正规表达式
4.1 正规表达式的形式定义
（4）如果r和s分别是上的正规式，对应的正 规集为R和S。那么 (r+s)为正规式，对应的正规集为RS； (rs)为正规式，对应的正规集为RS； (r*)为正规式，对应的正规集为R*
（5）只有满足上述形式定义的表达式才是上的 正规式，它所表达的语言是正规集。
第五章 正规语言的性质
5.3 Myhill-Nerode定理和 DFA 极小化
第五章 正规语言的性质
5.1 Pumping 引理
(1) Pumping 引理的提出
Pumping引理： 假设 L是正规集，那么存在正整数 n 使
得当 wL 并且|w|n,就可以写出 w=，这 里，，||n，且对k0,则 kL。
第五章 正规语言的性质
5.1 Pumping 引理
(2) Pumping 引理的应用 例1：证明 L1={anbn|n1}不是RL。
0
q0
q1
0
1
1
q2
q3
10
0
1
q4
1
q5
0
0,1
第五章 正规语言的性质
5.3 Myhill-Nerode定理和 DFA 极小化 二、 Myhill-Nerode定理
推论 1：对任意正规语言 L，如果DFA M满足 L(M)=L，则|*/RL||Q|
推论 2：在同构（即状态重新命名）的意义下， 接受一个语言 L 的最小DFA是唯一的。
例2：证明 L2={w|w*且={0,1},w = w-1} 不是 RL。这里w是回文。即w与w的逆 相同。
第五章 正规语言的性质
5.1 Pumping 引理
(2) Pumping 引理的应用
例3：证明 L3={an2|nN}不是RL。 例4：证明 L4={ap|p是素数}不是 RL。
第五章 正规语言的性质
RE
-NFA
NFA
DFA
RG
第五章 正规语言的性质
5.1 Pumping 引理
(1) Pumping 引理的提出
定理：假设 为有限字母表，L*。若 L 是 正规语言，那么存在正整数 n 使得对任意的 w1,w2,w3*,当w1w2w3L 并且|w2|n,可以写成 w2= ,这里，，||n.则
w1kw3L (k=0,1,2,….)。
第四章 正规表达式
4.1 正规表达式的形式定义
❖正规表达式的运算性质 假设r,s,t都是上正规式，则有以下性质：
（1）结合律；（2）分配律；（3）交换律； （4）幂等律；（5）加运算单位元； （6）乘运算单位元；（7）乘运算零元；
（8）(r*)*=r*；（9）r*=r++表，L *,以下三个命题等价： （1）L是正规语言； （2）L是*上具有有穷指数的右不变等价关系的某些等价
类的并； （3）如果 RL={<x,y>|x,y*,对z*,xzL当且仅当
yzL}，则RL的指数有穷。
第五章 正规语言的性质
5.3 Myhill-Nerode定理和 DFA 极小化
例：假设 L=0*10*它被下 列自动机接受。能否简化？
q0: (00)nR(00)m q1: 0(00)nR(00)m0 q2: (00)n1R(00)m1 q3: (00)n01R(00)m01 q4: (0)n10(0)mR(0)p10(0)q q5: xRmy,x和y至少含有两个1 的串。(这里m,n,p,q 0)