哈工大正心楼电梯DFA设计

FormalLanguageandAutomata正心楼电梯DFA模型1100300311—石招阳1100300426—姚崇崇1100300401—刘燊2012年11月11日1.电梯的自然语言描述1.1.电梯基本情况一、正心楼一共有9层。二、正心楼正门大厅的电梯是由两部电梯组成的，而实际上，两部电梯与一部电梯的差别仅仅在于：①两部电梯都空闲时，有人在电梯外按下按钮，电梯需要进行调度来控制选择其中一部电梯进行工作；②当两部电梯同时向上或者同时向下运行时，若有人在电梯外按下按钮，只有先到达的电梯会在该楼层停下响应请求。三、9层楼电梯都可以到达，电梯内有9个楼层按键，以及两个开门关门按键。开关门按键在这里与我们讨论的所有东西无关，可以忽略。四、电梯内中的每个按钮第一次按下时是选中（即灯亮），第二次按下时按键灯保持5秒钟的闪烁状态，在闪烁期间按下第三次，则取消选中；若闪烁期间无动作，则恢复选中。五、每个电梯门外有两个按钮，可以表示当前门外的人乘坐电梯要去的方向是上还是下。1楼只有向上没有向下，9楼只有向下没有向上键。由第二条的情况可得，两部电梯的运行情况极为类似，且相互之间影响不大。因此在本文中，我们将两部电梯的运行情况简化为一部电梯。1.2.电梯的运行方式现在我们设有,,ijk三个变量，其中19ijk。一、在i层向上的电梯，若电梯内有jk、按键被按下，则电梯先到j层，再到k层。二、在i层向上的电梯，在电梯内部有j键按下，电梯外部k层有向上键被按下，则电梯先到j层再到k层。三、在i层向上的电梯，电梯外部jk、层有向上键按下，则电梯先到j层再到k层。四、在i层向上的电梯，电梯外部jk、层有向下键按下，则电梯先到k层再到j层。五、在i层向上的电梯，在电梯内部有k键按下，电梯外部j层有向下键按下，则电梯先到k层后再回到j层。六、在j层向上的电梯，在电梯内有ik、键被按下，则先到达k层后，i键被取消。七、在j层向上的电梯，在电梯内有k键被按下，i层外有键按下（无论是向上还是向下），则先到k层再返回i层。八、在j层向上的电梯，在电梯外ik、层有向下键按下，则当电梯向上状态结束后，先到k层再到i层。九、当电梯处在向下的状态时，和向上运行的情况对称，在这里就不做详细说明。十、当电梯超重时，电梯停止不动，并发出警报。此时无论电梯内还是电梯外有人按下转移楼层的按键，电梯都不会响应。十一、电梯满载时，电梯将只到达电梯内按下的楼层，而不会响应电梯外部的按键请求，直到电梯不再满载。十二、当电梯外部的向上向下按钮已经按下后，不能被取消。十三、电梯内每个按钮第一次按下时是选中，第二次按下时按键灯保持5秒钟闪烁状态，在此期间按下该按键第三次，则取消选中。若闪烁期间无动作，则恢复选中。2.DFA设计2.1.分析用户的按键操作是可并行的，即允许同一时刻有多个用户按下多个按键，因此如果直接以用户的按键的状态作为DFA模型的输入符号，将会导致所设计的DFA的状态集过于庞大，状态转移函数过于复杂，难以对电梯的运行状况进行准确细致的刻画。但是经过仔细分析不难发现，电梯本身并不是直接以用户的输入作为控制指令的，而是将多个用户的请求暂存起来，通过某种调度算法，每一时刻只响应一个请求，直至所有的用户请求都已经响应完毕。因此从电梯的角度分析，它对用户输入指令的执行是串行的。因此，本文将电梯控制系统抽象为用户请求调度模块和运行控制模块，分别进行分析并建立DFA模型。用户请求调度模块的输入为用户的按键及电梯的运动状态，输出为下一时刻电梯需要响应的请求。运行模块的输入为请求调度模块的输出，输出抽象为电梯的运动状态，即运动方向和位置。这两个模块形成了循环反馈机制。2.1.1.模块结构如图：用户请求调度模块电梯运行模块执行的请求用户输入电梯运动状态图1电梯模块结构2.2.DFA定义0(,,,,)MQqF其中,,|19,18,29ijkQSUDijk是内部状态的有限集合，,,|19,18,29ijUkDijk是符号的有限集合，为转移函数，01qS是初态，|19iFSi是终态集合。2.3.DFA解析2.3.1.非空有限状态集及可接受状态集：而对于电梯自身的状态，从电梯的工作过程不难将其抽象为如下三类状态：1）iS：在某一楼层静止或暂时停下，此时是请求得到了响应或者是初态。2）jU：在楼层j与1j之间向上运行，即在楼层间的上升过程。3）kD：在楼层k与1k之间向下运行，即在楼层间的下降过程。在这三类状态中，显然只有第一类能被看作可接受状态。其余状态都是处在楼层间的中间态，因此，对于正心楼正门大厅的电梯来说，其电梯运行模块DFA的非空有限状态集为：,,|19,18,29ijkQSUDijk2.3.2.电梯的运动状态描述：1S电梯停留在第1层2S电梯停留在第2层3S电梯停留在第3层4S电梯停留在第4层5S电梯停留在第5层6S电梯停留在第6层7S电梯停留在第7层8S电梯停留在第8层9S电梯停留在第9层1U表示电梯在第1、2层之间向上运行2U表示电梯在第2、3层之间向上运行3U表示电梯在第3、4层之间向上运行4U表示电梯在第4、5层之间向上运行5U表示电梯在第5、6层之间向上运行6U表示电梯在第6、7层之间向上运行7U表示电梯在第7、8层之间向上运行8U表示电梯在第8、9层之间向上运行2D表示电梯在第1、2层之间向下运行3D表示电梯在第2、3层之间向下运行4D表示电梯在第3、4层之间向下运行5D表示电梯在第4、5层之间向下运行6D表示电梯在第5、6层之间向下运行7D表示电梯在第6、7层之间向下运行8D表示电梯在第7、8层之间向下运行9D表示电梯在第8、9层之间向下运行2.3.3.输入集：对于电梯的运行模块，其功能是针对输入及调度模块的输出（输入信号处理模块的输出信号），令电梯做相应操作。在此过程中，输入及调度模块的输出一直作为运行模块DFA的输入，即,,|19,18,29ijUkDijk2.3.4.输入信号处理模块的输出信号：1电梯内部按下1层2电梯内部按下2层3电梯内部按下3层4电梯内部按下4层5电梯内部按下5层6电梯内部按下6层7电梯内部按下7层8电梯内部按下8层9电梯内部按下9层1U1层按下向上键2U2层按下向上键3U3层按下向上键4U4层按下向上键5U5层按下向上键6U6层按下向上键7U7层按下向上键9U8层按下向上键2D2层按下向上键3D3层按下向上键4D4层按下向上键5D5层按下向上键6D6层按下向上键7D7层按下向上键8D8层按下向上键9D9层按下向上键W电梯超重由于iS状态转移有两个方向（即电梯向上或向下）。假设iS是由1iU转移过来的，那么如果iS有向上转移的信号，那么iS就应继续向iU转移。实际上就是如果电梯是向上运行到第i层的，那么电梯应优先响应向上运行的请求。对于向下运行的电梯则优先响应向下运行的请求。2.3.5.初始状态：理论上每一个楼层都可以作为电梯运行的起始楼层，在这里，我们假定第1层为起始楼层，即01qS2.3.6.终结状态：当电梯执行完所有的按键请求后，最终将停止在某一楼层（不固定），所以终结状态集为：|19iFSi转移详见DFA转移图（附录）。3.小组分工石招阳：实地考察电梯，获取电梯运行方式的数据，DFA的设计；姚崇崇：DFA图表审查，整体实验报告的撰写；刘燊：DFA的设计，图形DFA绘制，实验报告的审查。