有限状态机及其扩展PPT学习教案

1、会计学1有限状态机及其扩展有限状态机及其扩展2超级商场的自动门控制器超级商场的自动门控制器 自动门的前、后分别有两个缓自动门的前、后分别有两个缓冲区。自动门的前缓冲区用来检测是否有人接近。自动门冲区。自动门的前缓冲区用来检测是否有人接近。自动门的后缓冲区，使得控制器把门打开足够长的时间让人走进的后缓冲区，使得控制器把门打开足够长的时间让人走进去，并且不让门在打开的时候碰到站在它附近的人。自动去，并且不让门在打开的时候碰到站在它附近的人。自动门控制器依据前缓冲区、后缓冲区的检测信息给出打开或门控制器依据前缓冲区、后缓冲区的检测信息给出打开或闭合的动作指令。闭合的动作指令。 自动门的动作控制应满足

2、如下要求（规格）：自动门的动作控制应满足如下要求（规格）： 当前缓冲区和后缓冲区均无顾客出现，则自动门处于当前缓冲区和后缓冲区均无顾客出现，则自动门处于闭合状态；闭合状态； 当后缓冲区有顾客出现，则自动门维持其原有状态；当后缓冲区有顾客出现，则自动门维持其原有状态； 当前缓冲区有顾客且后缓冲区无顾客，则打开自动门。当前缓冲区有顾客且后缓冲区无顾客，则打开自动门。前缓冲区后缓冲区第1页/共51页closed openfrontneitherboth,rear,neitherboth,rear,front前缓冲区后缓冲区第2页/共51页401dec2incincincdecdecinc：增加1de

3、c：减少1第3页/共51页512A3B,CB,CCBA4A第4页/共51页6第5页/共51页7第6页/共51页8模3计数器 0 1 20 inc dec2 inc dec1 dec inc状态转移矩阵第7页/共51页9模3计数器 输入字符状态inc dec1 20 12 0 012状态转移表第8页/共51页1001dec2incincincdecdec状态转移图模3计数器 第9页/共51页11第10页/共51页121/10/01/20/11/00/2q0q2q1例例：模：模3余数余数Q = q0，q1，q2S= 0，1(qj) = j, j = 0,1,2在输入010100 下，输出为0122

4、12 第11页/共51页13状态转移函数为：(q0,0) = q1, (q0,1) = q2, (q1,1) = q2, (q1,0) = q1, (q2,1) = q2, (q2,0) = q1输出函数为： (q0,0) = n, (q0,1) = n, (q1,1) = n, (q1,0) = y, (q2,1) = y, (q2,0) = n。在输入01100 下，输出为nnyny 1/y0/n1/n0/y0/n1/nq0q2q1第12页/共51页1412A3B,Cctr3/ctr:=ctr+1 BA4errCctr3/ctr:=ctr+1 B,Cctr=3/ctr:=ctr+1 B,C

5、ctr=3/ctr:=ctr+1 A,Cctr=3/ctr:=ctr+1 B,Cctr3/ctr:=ctr+1 Actr3/ctr:=ctr+1 /ctr:= 0 第13页/共51页15err12A3BA4ctr= 2 ctr= 2 ctr= 2 ctr= 2 12A3BA4ctr= 3 ctr= 3 ctr= 3 ctr= 3 12A3BA4ctr= 1 ctr= 1 ctr= 1 ctr= 1 12A3BA4ctr= 0 ctr= 0 ctr= 0 ctr= 0 ctr= 4 B,CB,CB,CB,CB,CB,CB,CB,CA,CCCCAAA第14页/共51页16第15页/共51页17第1

6、6页/共51页1801dec2incincincdecdec模模3计数计数器器模模4计数计数器器01dec2incincdec3incincdecdecdeco 模3和模4计数器的笛卡尔积复合有34=12个状态o 每个状态下，两个模计数器均可相互独立地进行加数、减数或保持不变第17页/共51页192,02,12,32,21,01,11,31,20,00,10,30,2dec,decinc,inc,decinc,incdec,incdec,inc,dec模计数器的笛卡尔积模计数器的笛卡尔积复合复合 第18页/共51页20第19页/共51页212,02,12,32,21,01,11,31,20,0

7、0,10,30,2decincp模模3 3和模和模4 4计数器，可以进行耦合运行，阻止各自的独计数器，可以进行耦合运行，阻止各自的独立运行行为。立运行行为。只有只有incinc、incinc和和decdec、decdec两种共两种共2424个状态转移个状态转移第20页/共51页22第21页/共51页232,02,12,32,21,01,11,31,20,00,10,30,2incdecincdecp模模3 3和模和模4 4计数器，可以进行耦合运行，但在任何状态计数器，可以进行耦合运行，但在任何状态下仅有其中一个模计数器运行。下仅有其中一个模计数器运行。 分别有分别有incinc和和decdec

8、两种共两种共4848个状态转移个状态转移第22页/共51页生产生产者者P1生产P2写C1读C2消费读20读1写写缓存缓存器器消费消费者者第23页/共51页25第24页/共51页写生产读0, P1,C1 消费1, P1,C1 0, P1,C2 2, P1,C1 2, P1,C2 1, P1,C2 消费消费读读0, P2,C1 消费1, P2,C1 0, P2,C2 2, P2,C1 2, P2,C2 1, P2,C2 消费消费读生产生产生产生产生产写写写生产生产者者P1生产P2写C1读C2消费读20读1写写缓存缓存器器消费消费者者第25页/共51页27第26页/共51页生产者生产者1P11生产1

9、P12写1C1读C2消费消费者消费者生产者生产者2P21生产2P22写2P11, P21,C1 P11, P22,C1P11, P21,C2P11, P22,C2消费消费P12, P21,C1消费P12, P22,C1P12, P21,C2P12, P22,C2消费生产1生产1生产2生产2生产1生产2生产1生产2第27页/共51页29第28页/共51页30SS2S22S21S1S1FFS3S2T1TSUT2第29页/共51页31SFFUT SVFUTSS2S22S21S1第30页/共51页32S1FFS3S2T1TSUT2SS2S22S21S1第31页/共51页33S1Ein(S1)/Rt=2

10、/FS3S2T1TSRT2RF/EF/R第32页/共51页34第33页/共51页RFS2S22S21S1RFS2S22S21S1URFSS22S21S1TT2T1U第34页/共51页36S1S3S2C1ECC2S1S3S2EC1EC2第35页/共51页37S1S3S2E1ASE2E3S1S3S2AE1AE2AE3第36页/共51页38S1S3S2R/ASS1S3S2C1EFS1S3S2SETS1S3S2/AC1E等价 Statecharts图？第37页/共51页39US1S3SS2S4AE1/A1c2/A2US1S3SS2S4Ac1/A1E2/A2第38页/共51页40S1INTSS2S3AE

11、1/A1INTRINT第39页/共51页41S1HS2TS从状态从状态T进入状态进入状态S时，首先进入其历史状态时，首先进入其历史状态H，即进入最近访问的那个状态。若上次访问的状态为，即进入最近访问的那个状态。若上次访问的状态为S2，则进入状态，则进入状态S2。如果。如果H为空，则进入为空，则进入S1状态。状态。 第40页/共51页42第41页/共51页43第42页/共51页44ebonijeboffijarrives-atijpress-ebij第43页/共51页45fbonbjfboffbjcall-fbbjdepart-atbj第44页/共51页46第45页/共51页e-ue-u e-d

12、e-d a-us-ue-ue-ds-da-d e-ua-d s-us-d a-us-ue-ds-d a-us-uws-i a-d s-dws-ie-u s-uwe-ds-dw 第46页/共51页sensorsensorexitexit-downexit-upstopstop-upstop-downstop-idlecall-fbbjclose-doorclose-doorreduce-speedwaitapproachapproach-upapproach-down状态s-u、s-d和s-i可以合并为一个超状态超状态stop；状态a-u和a-d合并为超状态超状态approach；状态e-u和e

13、-d合并为超状态超状态exit。电梯经过在某楼层的暂停后，将合上门然后离开该楼层，这一过程规格为状态状态stop在触发事件在触发事件close-door下转移到状态下转移到状态exit。当存在某楼层对电梯的请求，并且此时的电梯正处于状态wait时，电梯将离开状态wait。这一过程规格为：在触发事件在触发事件call-fb(-,-)下，状态下，状态 wait转移到状态转移到状态stop. 对电梯运动过程进行如下假定：电梯在向上运动过程中，在进入状态电梯在向上运动过程中，在进入状态s-u之前要经过状态之前要经过状态a-u；同理，电梯在向下运动过程中，在进入状态s-d之前要经过状态a-d。这一转换过

14、程，在实际电梯系统运行中需要对电梯进行减速，用reduce-speed来表示所相应的内部事件。第47页/共51页sensorexitexit-downexit-upstopstop-upstop-downstop-idlecall-for-downclose-doorclose-doorsensorreduce-speedwaitapproachapproach-upapproach-downsensorclose-doorno-requestno-requestreduce-speedcall-for-upchange-directionchange-direction从超状态approach到超状态stop、或者从超状态stop到超状态exit的转换并没有在前图中明确指出。为此，需要对该规格进行细化规格进行细化，标记出与所有子状态相关的迁移。当电梯处于状态stop-idle时，如果发生某个用户对电梯进行请求，则转移到状态stop-up或stop-down；如果没有使用请求，则电梯将进入状态wait。这一过程通过迁移called_from_up、called_from_down、change_direction、和no_request等来描述第48页/共51页50exit-upstop-upopenclosedtimeoutclose-doorchange