第2期 蒋运承，等：基于有限状态自动机的服务组合模型 ·49· 出一些基本概念 的状态转换，并且交互可用二元组<iput-com- 定义1（有限状态自动机）有限状态自动机 mand,output-message>来表示 finite state automata,FSA)是一个五元组(Q,∑， 定义2（服务弱形式化模型）2！给定一个服务 6,,),其中？是一个有穷集合，叫做状态集：∑ e-Service,则e-Service可以表示为一个有限状态自 是一个有穷集合，叫做字母表：6：Q×∑Q是转移 动机FSA,并且FSA是一个六元组(Q,1,O,6, 函数；φ∈Q是起始状态；F二Q是接收状态集 仰，可，其中Q是一个有穷集合，是FSA的状态集， e-Service可以看成是一个软件“黑箱”，它可以 其中状态表示客户与e-Service交互序列中的历史 与客户交互，包括3步：1)客户通过发送输入命令 记录：I是输入命令input-command的有穷集合 (input-command)调用e-Service;2)输入命令激发 O是输出消息output-message的有穷集合，IXO e-Service的内部计算(internal-computation);3) 是FSA的字母表：6：QX1×O→Q是转移函数，即 客户得到e-Service的输出消息(output-mes 给定一个状态，根据<input-command,output. sage).因此，e-Service交互可以用3元组<input- message>,FSA能够转移到另一个状态；∈Q是 command,internal-computation,output-mes- 起始状态；F∈Q是接收状态集，即用户能够与e sage>表示.由于采用“黑箱”的方法，交互可用二元 Service结束交互的状态集， 组<input-command,output-message>来表示. 图1是一个基于有限状态自动机的股票交易服 因而可用有限状态自动机来描述e-Service,即 务2 e-Service的每次交互可以看成是有限状态自动机 buy/displayedResults userData/checkedAccount continue/displayedStock Data stop/emailNotification userData/not ValidClient sell/displayedResults 图1股票交易服务 Fig.1 Stock service 股票交易服务的形式化模型可以定义为 定义3（命题逻辑公式）命题逻辑公式按下列 FSA=(Q,1,O,6,m,F),其中状态集Q= 规则生成： {o,s1,s,s3,4};输入命令集合I=fuserData, 1)常量true和false是命题逻辑公式： continue,buy,sel,stop},输出消息集合O= 2)命题变元是命题逻辑公式： /checkedAccount,notValidClient,displayedStock- 3)如果中是命题逻辑公式，则中也是命题逻辑 Data,displayedResults,emailNotification,字母表 公式： IXO =f userData/checkedAccount,userData/ 4如果中和μ是命题逻辑公式，则中“和中V not ValidClient,continue/displayedStockData, μ也是命题逻辑公式： buy/displayedResults,sell/displayedResults, 5)命题逻辑公式只能由上述规则生成： stop/emailNotification以，转移函数6为：0 Xuser 定义4（条件）条件是由状态和命题逻辑公式 Data/checkedAccount -si,so X userData/ 通过联结词组成的表达式，形式定义如下： not ValidClient-s4,s Xcontinue/displayedStock- 假设Q是有限状态自动机状态的集合，E是命 Data-s2,s2 Xbuy/displayedResults -s2.s2 Xsell/ 题逻辑公式的集合，or和and是条件联结词，则条 displayedResults -s2,s Xstop/emailNotification 件按下列规则生成： ;0∈Q是起始状态，接收状态集F={g,4}. l)p、q∈Q,则porq和p and g是条件： 服务组合是根据组合算子来实现的，而有些组 2)p∈Q,e∈E,则p and e是条件（如果e= 合算子（如If-Them Else算子）涉及到条件，因而需 true,则简写为pl: 要一种新的自动机的定义 3)如果a和a是条件，则a and a和aora 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net出一些基本概念. 定义 1 (有限状态自动机) 有限状态自动机 (finite state automata , FSA) 是一个五元组( Q , ∑, δ, q0 , F) ,其中 Q 是一个有穷集合 ,叫做状态集; ∑ 是一个有穷集合 ,叫做字母表;δ: Q ×∑→Q是转移 函数; q0 ∈Q 是起始状态; F ΑQ 是接收状态集. e2Service 可以看成是一个软件“黑箱”,它可以 与客户交互 ,包括 3 步 :1) 客户通过发送输入命令 (inp ut command) 调用 e2Service ;2) 输入命令激发 e2Service 的内部计算 (internal comp utation) ; 3) 客户 得到 e2Service 的输出消 息 ( outp ut mes2 sage) . 因此 ,e2Service 交互可以用 3 元组 < inp ut command , internal comp utation , outp ut mes2 sage > 表示. 由于采用“黑箱”的方法 ,交互可用二元 组 < inp ut command , outp ut message > 来表示. 因而可用有限状态自动机来描述 e2Service ,即 e2Service 的每次交互可以看成是有限状态自动机 的状态转换 ,并且交互可用二元组 < inp ut com2 mand , outp ut message > 来表示. 定义 2 (服务弱形式化模型) [12 ] 给定一个服务 e2Service ,则 e2Service 可以表示为一个有限状态自 动机 FSA ,并且 FSA 是一个六元组 ( Q , I , O , δ, q0 , F) ,其中 Q 是一个有穷集合 ,是 FSA 的状态集 , 其中状态表示客户与 e2Service 交互序列中的历史 记录; I 是输入命令 inp ut command 的有穷集合; O 是输出消息 outp ut message 的有穷集合 , I ×O 是 FSA 的字母表;δ: Q ×I ×O →Q 是转移函数 ,即 给定一个状态 , 根据 < inp ut command , outp ut _ message > ,FSA 能够转移到另一个状态; q0 ∈Q 是 起始状态; F Α Q 是接收状态集 , 即用户能够与 e2 Service 结束交互的状态集. 图 1 是一个基于有限状态自动机的股票交易服 务[12 ] . 图 1 股票交易服务 Fig. 1 Stock service 股票交易服务的形式化模型可以定义为 FSA = ( Q , I , O , δ, s0 , F) ,其中状态集 Q = { s0 , s1 , s2 , s3 , s4 } ;输入命令集合 I = { userData , continue , buy , sell , stop } , 输出消 息集合 O = { checkedAccount , notValidClient , displayedStock2 Data , displayedResults , emailNotification} ,字母表 I ×O = { userData/ checkedAccount , userData/ notValidClient , continue/ displayedStockData , buy/ displayedResults , sell/ displayedResults , stop/ emailNotification} ; 转移函数δ为 : s0 ×user2 Data/ checkedAccount → s1 , s0 × userData/ notValidClient →s4 , s1 ×continue/ displayedStock2 Data →s2 , s2 ×buy/ displayedResults →s2 , s2 ×sell/ displayedResults →s2 , s2 ×stop/ emailNotification →s3 ;s0 ∈Q 是起始状态;接收状态集 F = { s3 ,s4 } . 服务组合是根据组合算子来实现的 ,而有些组 合算子(如 If2Then2Else 算子) 涉及到条件 ,因而需 要一种新的自动机的定义. 定义 3 (命题逻辑公式) 命题逻辑公式按下列 规则生成 : 1) 常量 true 和 false 是命题逻辑公式 ; 2) 命题变元是命题逻辑公式 ; 3) 如果φ是命题逻辑公式 ,则┓φ也是命题逻辑 公式; 4) 如果φ和μ是命题逻辑公式 ,则φ∧μ和φ∨ μ也是命题逻辑公式; 5) 命题逻辑公式只能由上述规则生成. 定义 4 (条件) 条件是由状态和命题逻辑公式 通过联结词组成的表达式 ,形式定义如下 : 假设 Q 是有限状态自动机状态的集合 , E 是命 题逻辑公式的集合 ,or 和 and 是条件联结词 ,则条 件按下列规则生成 : 1) p、q ∈Q ,则 p or q 和 p and q 是条件; 2) p ∈Q , e ∈E, 则 p and e 是条件 (如果 e = true ,则简写为 p) ; 3) 如果 c1 和 c2 是条件 ,则 c1 and c2 和 c1 or c2 第 2 期 蒋运承 ,等 :基于有限状态自动机的服务组合模型 · 94 ·