语言和自动机1013104.docx
《语言和自动机1013104.docx》由会员分享，可在线阅读，更多相关《语言和自动机1013104.docx（10页珍藏版）》请在冰点文库上搜索。
语言和自动机1013104
第10章语言和有限自动机LanguageandFinite－StateMachine________
§10.3有限状态自动机
Finite－StateMachine
有限状态集S＝{s0,s1,s2,……,sn}。
有限输入集I，每个x∈I，有一个
状态转换函数fx：
S→S。
F＝{fx|x∈I}.
M=（S，I，F）叫有限状态自动机。
状态si，输入x，fx（si）下一个状态。
M=（S,I,F）与M’=（S，I，F）等价：
F：
S×I→S，
F（si,x）=fx（si）.
例1．
S＝{s0,s1},I={0,1}.
f0（s0）=s0，f0（s1）=s1，
f1（s0）=s1，f1（s1）=s0，
状态变换表：
0
1
s0
s0
s1
s1
s1
s0
例2．I＝{a,b},S={s0,s1,s2},
fa（s0）=s0，fa（s1）=s2，fa（s2）=s1，
fb（s0）=s1，fb（s1）=s0，fb（s2）=s2，
定义S上关系RM，
siRMsj当且仅当存在一个输入x，fx（si）=sj.
M的图：
MooreMachine识别机recognitionmachine
M＝（S,I,F,s0,T）,
s0初始状态，TS，可接受状态集。
例2中，T＝{S2},则
a*（bb）*b（ab*a）*ab*是M可识别的语言.
自动机同余和商自动机
MachineCongruenceand
QuotientMachine
设M＝（S，I，F），R是M上同余关系：
R是S上等价关系，且对任意s，t∈S，sRt当且仅当对任意x∈I，fx（s）Rfx（t）.
令
＝S/R={[s]|s∈S}
对任意x∈I，令
由R是同余关系，
是
上的函数。
令
称有限自动机
＝（
，I，
）为M对应R的商，记做
＝M/R.
如果M＝（S,I,F,s0,T）,R是M上的同余关系，
＝（
，I，
，s0，
），
={[t]|t∈T}。
称为M的商MooreMachine.
例6.令S＝{s0,s1,s2,s3,s4,s5}，T={s1,s3,s4}.
状态变换表：
S上同余关系R：
a
b
s0
s0
s4
s1
s1
s0
s2
s2
s4
s3
s5
s2
s4
s4
s3
s5
s3
s2
[s0]={s0,s2}=[s2]
[s1]={s1,s3,s5}=[s3]=[s5]
[s4]＝[s4]
=S/R={[s0],[s1],[s4]}
a
b
[s0]
[s0]
[s4]
[s1]
[s1]
[s0]
[s4]
[s4]
[s1]
例7．I＝{0,1},
S={s0,s1,s2,s3,s4,s5,s6,s7}，
M={S,I,F}
S/R={{s0,s4},{s1,s2,s5},{s6},{s3,s7}}
0
0
1
HomeworkPP380-381
6,8,14,18,20
§10.4.半群，自动机和语言semigroups，machinesandlanguages
M={S,I,F}
S＝{s0,s1,s2,……,sn}。
F＝{fx|x∈I}.
I*是一个独异点，空串Λ是单位元。
S上所有函数的集合SS，关于复合组成独异点，恒等变换1s是单位元。
任意x∈I，fx∈SS,设w＝x1x2……xn∈I*,
令fw＝fxn◦fxn-1◦…◦fx1，fΛ=1s，
对每个w∈I*,fw∈SS,称fw是w对应的状态变换函数。
例1.M={S,I,F},S＝{s0,s1,s2},I={0,1}。
状态变换表F：
0
1
s0
s0
s1
s1
s2
s2
s2
s1
s0
设w＝011∈I*，
fw（s0）=f1◦f1◦f0（s0）=f1◦f1（s0）=f1（s1）=s2.
fw（s1）=f1◦f1◦f0（s1）=f1◦f1（s2）=f1（s0）=s1.
fw（s2）=f1◦f1◦f0（s2）=f1◦f1（s1）=f1（s2）=s0.
例2．上例Moor机
0
fw（s0）=s2，fw（s1）=s1，fw（s2）=s0.
w’=01011
fw’（s0）=s1,fw’（s1）=s2,fw’（s2）=s0.
令M={S,I,F},定义函数
T：
I*→SS，
对任意w∈I*，T（w）=fw∈SS。
定理1.
（a）T（w1w2）=T（w2）T（w1）.
（b）M=T（I*）构成SS的子独异点。
a
例3.
b
则fadd◦fbad=fbadadd.
证明.
fadd（s0）=s0,fadd（s1）=s0,fadd（s2）=s0,
fbad（s0）=s1,fbad（s1）=s1,fbad（s2）=s1,
fadd◦fbad（s0）=fadd（s1）=s0
fadd◦fbad（s1）=fadd（s1）=s0.
fadd◦fbad（s2）=fadd（s1）=s0.
fbadadd（s0）=s0,fbadadd（s1）=s0,fbadadd（s1）=s0,
因此fadd◦fbad=fbadadd.
例4.Moor机如下图，证明fw（s0）=s0当且仅当w含有3n个1。
证明.归纳证明性质P（n）成立：
P（n）:
w中含1的个数为l*（w）=m，
（a）m=3n,fw（s0）=s0，
（b）m=3n＋1,fw（s0）=s1，
（c）m=3n＋2,fw（s0）=s2。
P（0）成立，设P（k）成立，
m＝3（k+1）=3k+2+1
fw（s0）=fw’001（s0）=f001fw’（s0）=f001（s2）
=f1（s2）=s0，
m＝3（k+1）+1
fw（s0）=fw’0*1（s0）=f0*1fw’（s0）=f0*1（s0）
=f1（s0）=s1，
m＝3（k+1）+2=3（k+1）+1+1
fw（s0）=fw’10*（s0）=f10*fw’（s0）=f1（s1）
=f1（s1）=s2，
则P（k＋1）成立。
归纳完成。
因此对任意n，P（n）成立。
MooreMachine识别机recognitionmachine
M＝（S,I,F,s0,T）,
s0初始状态，TS，可接受状态集
令语言L（M）={w|w∈I*,fw（s0）∈T}。
例5．在例4中设T＝{s1},
fw（s0）=s1当且仅当w中含有3n＋1个1。
L（M）＝{w∈I*|w含有3n＋1个1}。
a,b
例6.S={s0,s1,s2},I={a,b},T={s2}
a
求L（M）.
解：
L（M）={w∈I*|w含有2个以上的b}。
HomeworkPP385－386
4，5，6，7，10，12，14，16，20
升级会员 