【正文】 tic FSM (or NFA) ?NFSM is 5tuple: FSM = (S, s0, I, ?, F), where ? S = {s0, s1, …, s n}: 有限狀態(tài)集合。在任一確定時(shí)刻， FSM只能處于一個(gè)確定的狀態(tài) si。 ? I = {a0, a1, …, a m}: 有限輸入字符集合。在任一確定的時(shí)刻，F(xiàn)SM只能接收一個(gè)確定的輸入 aj。 ?? ： S ? I ? 2S是狀態(tài)轉(zhuǎn)換函數(shù)，如果在某一確定的時(shí)刻，F(xiàn)SM處于某一狀態(tài) si ? S, 并接收一個(gè)輸入字符 aj? I，那么下一時(shí)刻將處于一個(gè)某一個(gè)狀態(tài)子集 = ?(si , aj) = {p0, p1, …, pk}(pi ? S, I=1,2,…,k) 。在這里規(guī)定， s = ?(s , ?)， 即對(duì)任何狀態(tài) s，當(dāng)讀入空字符 ?時(shí)，有很狀態(tài)機(jī)不發(fā)生任何狀態(tài)轉(zhuǎn)移。 ? s0 ? S是初始狀態(tài)， FSM由此狀態(tài)開(kāi)始接收輸入 ? F ? S是一個(gè)終態(tài)集（可空）， FSM到達(dá)終態(tài)后不再接收輸入 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 23 FSM: Formal Definition (Cont.) ?在一些情況下，如果討論問(wèn)題的重點(diǎn)集中在 FSM的狀態(tài)集 (S)、輸入集 (I)和狀態(tài)轉(zhuǎn)換函數(shù) (?)上。這時(shí)可用如下兩種方式來(lái)表示 FSM： ?FSM = (S, I, ?)或 ?FSM = (S, s0, I, ?) 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 24 Finite State Machines (FSMs) 三、 Representation 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 25 State Transition Diagrams ?Used to Visually represent an FSM ?Emphasis is on identifying states and possible transitions ?Circles represent States ?Arrows represent Transitions ?ei are inputs ?xi are outputs S1 S2 e1/x1 e1/x2 e2/x4 e2/x3 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 26 FSM Tables (狀態(tài)轉(zhuǎn)換表 ) ? All inputs, states, state transitions and outputs of a FSM can be listed in a Table format input events outputs current state next state S1 S2 S1 S2 x1 x2 x3 x4 S2 e1 e1 e2 e2 S2 S1 S1 ? Each row of the table is one unique bination of Input Events and Current State ? For plete definition of FSM all Event/State binations shall be provided ? Table is another way to represent an FSM with an emphasis on exploring all Event/State binations 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 27 FSM Table Compact Form ? Here in the top row of the Table has a list of all States while first column has a list of all Input Event. ? Table Field on the intersection represents the transition function for the State, Event bination ? Each field contains list of outputs and next state S1 S2 X1, S2 X3, S1 X2, S2 e1 e2 X4, S1 state event 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 28 Rocker Switch Example ? Events such as “switch on” and “switch off” may cause the machine to change state, as in the state diagram below for a light with a rocker switch. off on switch on/ make click sound switch on/ stay quiet switch off/ make click sound switch off/ stay quiet input events outputs current state next state on off on off click click on Switch on Switch on Switch off Switch off on off off On Off click, off click, on Switch on Switch off state event ? Some events don’t cause a state transition at all, as in attempting to turn on a light that is already on. ? Behaviour of the system in each state has to be defined: State ON light is emitted out of bulb, State OFF no light emitted 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 29 FSM Example Telephone ?What are possible states ?What are possible events ?Create FSM Table ?Create State Transition Diagram ?When we model an object we consider behavior which is of interest for us. ?In this case we will consider ability of phone to be used to dial another subscriber, to be used to pass voice between subscribers and to be able to receive ining calls. 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 30 Telephone States ? Following States can be identified ? IDLE no calls in progress handset is onhook ? DIALING handset is offhook, but call is not in progress ? RINGING handset is onhook, ining call alert ? PATH ACTIVE handset in offhook and call is in progress ? Relevant events are: ? offhook User takes handset offhook ? onhook User places handset onhook ? dial digit User dials digit ? call alert Exchange alerts phone ining call 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 31 Telephone FSM Table IDLE D IALING R ING I N G PAT HA C TIVEOn h o ok IDL E IDL EOf f h oo k Send Di alT o n e,DI A L INGP A T HA C T IV E DI A L INGD ial d igi t(Note 1) P A T HA C T IV E C all A le rt Rin gPh o n e,RINGI NG/ / /Note 1: if last digit in phone number is dialed lower option shall be selected “ /“ Unexpected event, “” No State Change 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 32 Telephone State Transition Diagram IDLE PATH ACTIVE DIALING OffHook Dialing Tone Dial Digit RINGING Dial Digit OnHook OnHook OffHook Stop Ringing This is Starting state Call Alert Start Ringing 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 33 Timers amp。 FSMs ? Sometimes there is a need to perform some actions after some period of time. For that purpose timers are used ?Timers can be started specifying amount of time before timeout will happen ?When timeout occurs the timer event will be sent to the FSM. Name of event is typically same as name of timer ?Timers can be stopped, so timer event is not generated 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 34 Telephone FSM Table with Timers IDLE DI A LI NG RING ING P A THA C TI V EOn hook IDL E / IDL EOff hook Send Dia lTone,DIA LIN GStop T1PATHACT IVEDIA LIN GDia ldi gi t(No te 1 ) PATHACT IVE Ca ll A le rt Star tT1= 20s ecRIN GIN G/ / /T1/ / IDL E /Note 1: if last digit in phone number is dialed lower option shall be selected 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 35 Telephone STD with Timers IDLE PATH ACTIVE DIALING OffHook Dialing Tone Dial Digit RINGING Dial Digit OnHook OnHook OffHook Stop Ringing This is Starting state Call Ale