语言和自动机10[1].3-10.4.doc

第10章 语言和有限自动机Language and Finite－State Machine
§10.3有限状态自动机
Finite－State Machine

有限状态集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
输入
输出1
输出1

例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的图：
s0
b
s1
S2
b
b
a
a
a

Moore Machine识别机recognition machine
M＝(S, I, F, s0, T),
s0初始状态，TÍS，可接受状态集。

例2 中， T＝{S2}, 则
a*(bb)*b(ab*a)*ab* 是M可识别的语言.

自动机同余和商自动机
Machine Congruence and
Quotient Machine

设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的商Moore Machine.

例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}
S0
S4
S5
S2
S3
S6
S7
0
0
0
0
1
1
1
1
1
1
S1
0
0
0
0
1
1

S/R={{ s0, s4}, { s1, s2, s5}, {s6},{ s3, s7}}
0
0
1
[S0]
[S3]
[S6]
1
[S1]
0
0
1
1

Homework PP380-381
6, 8, 14, 18, 20

§10.4.半群，自动机和语言semigroups，machines and languages

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
S0
S2
S1
0
0,1
1
1

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(w1×w2)= T(w2) ×T(w1).
（b） M=T(I*)构成SS的子独异点。

a
例3.
b
S0
S2
S1
d
d
b,d
a,b
a

则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。
S0
S2
S1
1
1
1
0
0

证明. 归纳证明性质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) = f001 fw’ (s0) = f001(s2)
=f1(s2)=s0，
m＝3(k+1)+1
fw(s0)= fw’ 0*1(s0) = f0*1 fw’ (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)成立。

Moore Machine识别机recognition machine
M＝(S, I, F, s0, T),
s0初始状态，TÍS，可接受状态集
令语言 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
S0
S2
b
S1
b
a

求L(M).
解：L(M)={w∈I*| w含有2个以上的b}。
Homework PP385－386
4，5，6，7，10，12，14，16， 20