资源描述：
《第二章：有穷自动机和正规文法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、形式语言与自动机主讲：方敏西安电子科技大学1第一章目录2.1有穷自动机(有限自动机)2.2不确定有穷自动机2.3DFA与NFA等效2.4有ε转换的不确定有限自动机2.5正规集与正规式2.6右线性文法和正规集2.7右线性语言与有限自动机2.8右线性语言的性质2.9双向和有输出的有限自动机2上一页下一页退出第二章有穷自动机和正规文法2.1有穷自动机(有限自动机)文法：是对语言的有穷说明识别器：有穷地说明无穷语言的一种方法，例最简单的识别器--有穷自动机。有穷自动机不能定义所有由文法定义的语言，它所定义的语言正好是3
2、型语言。有穷自动机M＝(S，∑，δ，s，F)0S——有穷非空集∑——有穷输入字母表δ’(s,xa)=δ(δ’(s,x)，a)δ——是K×∑→K的一种映射，S×∑*→S映射s——起始状态，初态。F——终止状态集F⊆S0有限控制器一个有穷自动机01011101003上一页下一页退出接受：若δ(s,x)＝P,P∊F，则称句子x被M接受，0由M接受的所有x的集合用T(M)表示。T(M)＝｛X｜δ(q，x)在F中｝0正规集：由有穷自动机接受的字符串的任何集合。例：M＝(K，Σ，δ，q，F)0Σ＝｛0，1｝K＝｛q，q，q
3、，q｝0123F＝｛q｝0T(M)＝｛0,1｝*中的所有含偶数个0和偶数个1的句子集合。4上一页下一页退出2.2不确定有穷自动机1.NFANFAM＝(K，∑，δ，q，F)0δ:K×Σ*→K的子集当M在状态q并输入α时，M把字的输入头右移一个单元，并选择P，P，…，P中任意一个作为下一个状12K态。把映射δ定义域扩大到K×Σ*：当输入一个字符串时，将δ改为δ＇。△δʹ(q,ε)＝｛q｝和δ(q,xa)=∪δ(p,a)p在δ（q,x)中k△δ(｛P,P,…,P｝,x)＝∪δ(p,a)12kii=15上一页下一页退出
4、例：(M)＝｛含有两个相邻的0或含有两个相邻的1字集｝M＝(｛q,q,q,q,q｝,｛0,1｝,δ,q,｛q,q｝)012340241.2.确定的有限自动机设L为一个NFA接受的集合，则存在一个接受L的确定的有穷自动机DFAM＝(K，∑，δ，q，F)0δ：K×∑→K映射6上一页下一页退出对任意字符串ω∈T*，则δ(q,ω)表示DFA在状态q，输入字符串ω后的状态。δ定义：对q∈T*，有δ(q,ε)＝q,表示没有读到字符串，M状态不变。对任意a∈T和ω∈T*,有δ(q,ωa)＝δ(δ(q,ω),a)表示：在读入ω
5、之后,得到状态P＝δ(q,ω),再求δ(ｐ,a)当ω＝ε时,δ(q,a)＝δ(δ(q,ε),a)＝δ(q,a)所以当δ和δ都有定义时，两者的值没有差别，为书写方便，以后用δ代替δ。7上一页下一页退出3.格局为描述FA的工作状态，可用两个信息表明。一是在该时刻有限自动机所处的状态q,—当前状态一是在该时刻等待输入的字符串ω。构成一个瞬间描述，称为格局，用(q,ω)表示。定义(2.1)FAΜ＝(Q,T,δ,q,F),偶对(q,ω)∈K×T*称为Μ的0格局，并称(q,ω)是初始格局。0对于q∈F，(q，ε)是终止格局
6、（或接受格局）。当有δ(q，α)含有q,用格局形式可写成：1(q,aω)├(q,ω)1ω∊T*,符号”├”连接着两个格局，表示从一个格局变换为另一个格局。8上一页下一页退出例：上例中：输入字符串：abba，(q，abba)├(q,bba)├(q,ba)011├(q,a)├(q,ε)13＊也可写成:(q,ω)
7、----(q,ε)0＊符号“
8、----”表示经过若干次格局变化。例：有NFA如右图：9上一页下一页退出(q,abcca)├(q,bcca)├(q,cca)├000(q,bcca)(q,cca)13├(q,c
9、a)├(q,a)├(q,ε)×000(q,a)(q,ε)×51(q,ca)├(q,a)├(q,ε)←终止格局566如果δ(q,a)只含有一个状态的子集时，便是DFA。故DFA是NFA的特例。10上一页下一页退出2.3DFA与NFA等效由于DFA是NFA的特例，所以DFA能接受的语言必能为NFA所接受，相反，NFA接受的语言，则能找到一个等效的DFA接受语言。定理2.3.1设L(M)是NFAM接受的语言，则存在一DFANNM接受L(M)，满足L(M)＝L(M)DDDN11证明：设:NFAM＝(Q,T,δ,q,F)
10、接受L(M)N0N对应M构造DFAM＝(Q,T,δ,q,F).其中NDDD0DDQ＝2Q,Q中元素的形式为[q,q,…,q]DD12n{q,q,…q}⊆Q;12nq＝[q]；0DDF⊆Q,F的每个状态包含M的一个终止状态;DDDNδ定义为Dδ(［q,q,…,q］,a)=［ｐ,ｐ,…,ｐ］D12n12ｍ当且仅当δ({q,q,…,q},a)={ｐ,ｐ,…,ｐ}12n12ｍ说明δ的值是通过求
