计算理论与算法分析设计课件：有穷自动机

CH2有穷自动机II

2024/6/302

of1582.4正则语言与非正则语言直觉

由于FA只有有限的状态，它只能“记住”有限的事物猜想一些非正则的语言2024/6/303

of1582.4正则语言与非正则语言定理(泵引理):设L是正则语言,则存在正整数n>0使得对任意wL,|w|n,存在分割w=xyz满足

1)

i0,xyizL;2)|y|>0;3)|xy|n.2024/6/304

of1582.4正则语言与非正则语言2024/6/305

of1582.4正则语言与非正则语言若FA接受一个“足够长”的字符串，则它必有重复状态2024/6/306

of1582.4正则语言与非正则语言2024/6/307

of1582.4正则语言与非正则语言应用(难点):B={anbn|n0}非正则2024/6/308

of1582.4正则语言与非正则语言2024/6/309

of1582.5状态最小化找出与给定的DFA等价的最小的DFA最小：状态数最少等价：接受相同的语言2024/6/3010

of1582.5状态最小化:消除不可达状态

在自动机中，从开始状态没有任何一条路径能达到的状态称为不可达状态。由于不可达状态事实上是无用的，因此也称多余的状态，可以删除它们。下面给出识别可达状态的算法。当该算法终止时，每一个未标记的状态就是不可达状态。

识别DFA中可达状态的算法。

①标记开始状态S；

②给定任意标记过的状态P，如果对某个输入符号存在从状态P到Q的转换，则标记每一个这样的状态Q；

重复步骤②，直到不再有可标记的状态为止。2024/6/3011

of1582.5状态最小化:消除不可达状态

2024/6/3012

of158DFA的化简(状态最小化)所谓DFA的化简是指寻找一个状态数比M少的确定的有穷自动机M

，使得L(M)=L(M

)。化简后的DFAM′应满足两个条件:(1)没有多余状态;（不可达状态）

(2)它的状态集合中,没有两个状态是相互等价的。定义

假定q1和q2是M中的两个不同状态，称q1和q2是等价的当且仅当如果从状态q1出发能扫描任意串w而停止于终态，那么从状态q2出发也能扫描同一个串w而停止于终态；定义

如果两个状态q1和q2不等价，则称这两个状态是可区分的。2024/6/3013

of158DFA的化简:划分法DFAM最小化的方法是把M的状态集合Q划分成一些不相交的子集，使得每个子集中的任何两个状态是等价的，而任何两个属于不同子集的状态都是可区分的；然后在每个子集中任取一个状态作为代表，而删去子集中其余状态，并把射向其余状态的弧都改为射向作为“代表”的状态中。2024/6/3014

of158算法:划分法（1）将DFAM的状态集Q分成两个子集：终态集F和非终态集Q-F，形成初始划分П。（2）对П建立新的划分ПNew

，对П的每个状态子集G，进行如下变换：

①把G划分成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a，状态s和t转换到的状态都属于П的同一子集。

②用G划分出的所有新子集替换G，形成新的划分ПNew

。2024/6/3015

of158算法:划分法(续)（3）如果ПNew＝П，则执行第（4）步；否则令П=ПNew

，重复第（2）步。（4）划分结束后，对划分中的每个状态子集，选出一个状态作代表，而删去其他一切等价的状态，并把射向其他状态的箭弧改为射向这个作为代表的状态。这样得到的DFAM′是与DFAM等价的一切DFA中状态数最少的DFA。2024/6/3016

of1582024/6/3017

of1582024/6/3018

of158划分法ab{1,3}2{4,6}253{4,6}355552024/6/3019

of158划分法ab{1,3}2{4,6}253{4,6}355552024/6/3020

of1582.6有关有穷自动机的算法(a)有一个指数算法，给定一台NFA，构造一台等价的DFA(b)有一个多项式算法，给定一个正则语言，构造一台等价的NFA(c)有一个指数算法，给定一台NFA，构造一个等价的正则表达式2024/6/3021

of1582.6有关有穷自动机的算法(a)有一个指数算法，给定一台NFA，构造一台等价的DFA2024/6/3022

of1582.6有关有穷自动机的算法(d)有一个多项式算法，给定一台DFA，构造一台等价的状态