加权Moore机的同余与最小化

CN 43 1258/ T P ISSN 1007 130X
计算机工程与科学
COM P U T ER EN GIN EERIN G & SCIEN CE
2010 年第 32 卷第 9 期 Vo l 32, N o 9, 2010
文章编号 : 1007 130X ( 2010) 09 0165 04
*
p , q # Q,
2
(! ( p) , x,
∃
=
*
% Y* & S ,
M
(x, y) =
定 理 2 ( 1) 设 ) 是加权 M oo re 机 M = ( Q, , Y , I , T ) 上 的同余 , 定义 h: M & M/ ) 为 p # Q, h( p ) = [ p ] , 则 h 是一个满同态。 ( 2) 设 M i = ( Qi , i , Y , I i , T i ) , 其中 i = 1, 2, 且 !: M 1 & M 2 为 满 同 态 , 则 : ker ! = { ( p , q) # Q1 % Q1 !( p ) = !( q) } 是 M 1 上的一个同余 , 且 M 1 / ker ! ! M2 。 证明 # Y , 有:
!(q 1 ) = q2
( !( p 1 ) , x , q2 ) =
( 2) 输入序列 x = x 1 (x k # q) =
q1 , (, qk- 1 # Q
∃
∃
1
( p 1 , x , q1 ) ;
*
,x ∋
时,
*
( p, x,
( 3) T 2 ( ! ( p1), y) = T1( p1, y) 。 则 称映射 ! 是 M 1 到 M2 的同态。若同态 ! 是满的则 ! 称为满同态 , 一 个 既满 又单 的 同态 称 为同 构 , 记 做 M 1 ! M 2 。若 ! 同构则条 件 ( 2) 可 换为 : !( q ) ) =
! (q ∗)= ! ( q) 2
( 2) 若 p i ) p j 且 y # Y , T ( p i , y ) = T ( p j , y) 。 则称这个等价关系为 M 的一个同余。 由于一个等价关系唯一 决定一 个状态 集合的 划分 , 对 p i # Q, 记 [ p i ] = { p j # Q p i ) p j } 。 用 H = {[ pi ] pi # Q} 表 示所有 Q 上等价类的集合。 定义 6 设 M = ( Q , , Y , I , T ) 是一个加权 M o or e 机 , 由 M 上的一个同余关系 ) 所决定的商加权 M oo re 机定义 为 M / ) = ( H , / ) , Y , I / ) , T / ) ) , 其中 p, q # Q, x #
*
收稿日期 : 2010 03 11; 修订日期 : 2010 06 19 基金项目 : 国家自然科学基金资助项目 ( 60873119) 作者简介 : 李苏妮 ( 1984 ) , 女 , 陕西周至人 , 硕士 , 研究方向为计算智能 ; 李永明 , 博士 , 教授 , CCF 会员 ( E200007329S) , 研究方 向为 计算智能。 通讯地址 : 710062 陕西省西安市陕西师范大学长安校区 179 信箱 ; T el: 13991154907; E mail: Lisuni 123@ 126. com Address: M ail Box 179, Chang an Cam pus, Shaanxi N ormal U nivers ity, X i an, Shaan xi 710062, P. R . China
( !( p∗) , x , q ) =
∃
1
( p∗ , x , q ∗) , T 1 ( p , y ) = T 2 ( !( p ) , y ) = T 2 ( !( p∗) , y )
( pj , x, q ∗) ;
q∗ker ! q
= T 1 ( p∗, y ) 。从而 ker ! 为 M 1 上的同余。 再设 ∀ : Q1 / ker ! & Q2 定义为 ∀ ([ p] ) = ! ( p) , 若 [ p] = [ p∗] 当且仅当 !( p ) = !( p∗) , 则 说明 ∀是单 射 , 且由于 ! 是满射 , 故 ∀为 满射且满足 Y,
( 4) 对每个 a # S, 0 a = a 0 = 0。 如 果对每个 a, b # S, a b = b a, 则称半环 S 是交换 半环 ; 如果 !S, + , 0∀ 是一个幂等 幺半群 , 则称 半环 S 是幂 等的。 定义 2 一个 定义 在半 环 S 和字 符集
∃
上 的加 权
M o or e 机是一个五元组 M = ( Q, , Y , I , T ) , 其中 Q 是一个
165
有穷状态集合 , : Q %
∃ % Q & S 为加权状态转移函数, Y ∃
*
为有穷输出字符集 , I : Q & S 为一个 加权初始状态 , T : Q % Y & S 为加权状态输出函数。 设由输入集合序列构成的集合为 把转移函数 扩展到 Q % ( 1)
*
M o or e 机 , 则 M 和 M / ) 等价。 定义 7 设 M1 = ( Q1 , 1 , Y , I 1 , T 1 ) , M 2 = ( Q2 , p∗ , p , p 1 , q1 # Q 1 , q2 # Q 2 , x # 条件 : ( 1) I 2 ( !( p ) ) = ( 2)
加权 M oore 机的同余与最小化 W eighted M oore M achine Congruences and M inimization
李苏妮 1 , 李天朝 2 , 李 永明1, 3 LI Su ni1 , LI Tian chao2 , LI Yong ming1, 3 ( 1. 陕西师范大学数学与信息科学学院 , 陕西 西安 710062; 2. 陕西师范大学网络信息中心 , 陕西 西安 710062; 3. 陕西师范大学计算机科学学院 , 陕西 西安 710062) ( 1. School of Mathematics and Information Science, Shaanxi Normal University, Xi an 710062; 2. Network Inf ormation Center, Shaanxi Normal University, Xi an 710062; 3. School of Computer Science, Shaanxi Normal University, Xi an 710062, China) 摘 要 : 本文定义了加权 M oo re 机的同余 、 同态 , 给出了同态定理并证明了同余关系 在加权 M oo re 机 中构成一个 完备 格 。 在同余关系下给出了加权 M o ore 机的商 M oo re 机 , 并给出了求最小状态 M o or e 机的算法 。 Abstract: T he congr uences and homomo rphisms o f a w eig hted M oo re machine are defined in this paper . M or eover , a ho momo rphism t heo rem is g iven and the co ng ruence relatio ns for m a complete lattice in the w eig hted M oor e machine are pr oved. U nder the cong ruence relation, t he factor M o or e machine of the w eig hted M oo re machine is g iv en. T he alg or ithm o f finding the m inimum state M o or e machine is presented. 关键词 : 加权 M oor e 机 ; 同余 ; 算法 Key words: weig hted M o or e machine; cong ruences; algo rithm doi: 10. 3969/ j. issn. 1007 130X. 2010. 09. 042 中图分类号 : T P301. 1 文献标识码 : A
2 ! ( p∗) = ! ( p)
2
, Y,
I 2 , T 2 ) 是两 个加 权 M oo re 机 , 给 定映 射 !: M 1 & M 2 , 若
, 表示空输入 ,
∃
*
, y # Y , ! 满足以下
∃
*
% Q 上, 即: ;
( p , , q) =
1, p = q 0, p ∋ q
∃
I 1 ( p∗) ;
1 ( p , x , q) 。
∃
( p , x 1 , q1 ) ( ( qk- 1 , x k , q) 。
类似于文献 [ 10] , 可以定 义加权 M oo re 机的响 应函数 如下 : 定义 3 加权 M oo re 机 M 的输入输 出响应 函数为 : 0, a, y ∋ y = x + 1 , 并当 x x + 1 a = T ( q1 ,
M2
定义 4 设两个 加权 M oo re 机 M 1 和 M 2 有相同 的输
先证 ( 1) , 首先 h 为满射且 /
)
p # Q, x #
)
∃
∃,y
I/ )
*
,
y #
Y
*
,
M 1
( x, y) =
( h( p ) , x , [ q] ) =
h(q∗) = [ q]