行政楼电梯DFA-形式语言大作业

哈工大行政楼电梯DFA设计小组成员：------------------2015年11月14日一、自然语言描述（一）电梯基本状况：1.行政楼一共6层，有两个电梯工作，两个电梯并非完全并行，但是若同时考虑两个电梯的话，例如关于同一指令的优先判定之类的问题变量过多，在这次DFA设计中出于方便和简洁的考虑我们只研究1个电梯的运行状态。2.在电梯外，一楼只有向上键，六楼只有向下键，其他楼层既有向上键，又有向下键。在电梯内部，有1-6六个按键，分别对应6个楼层。3.电梯有超重检测系统，承载重量超过额定重量之后会蜂鸣提示，同时保持停靠状态。4.在电梯中还有开关门及意外情况报警的按键，对构造电梯的DFA没有影响，可不予考虑。（二）电梯运行方式：为了设计DFA我们首先需要对实地考察得出的电梯运行规律用自然语言进行描述：现设有i,j,k三个变量其中1=ijk=6。（1）在i层向上的电梯，若电梯内有jk按键被按下，则先到j层再到k层；（2）在i层向上的电梯，在内部有j键按下，外部k层有向键按下，先到j再到k；（3）在i层向上的电梯，外部j，k层有向上键按下，先到j再到k；（4）在i层向上的电梯，外部j，k层有向下键按下，先到上到k再下到j；（5）在i层向上的电梯，外部j层有向下键按下，k层有向上键按下，先到k并继续向上达到目标后再到j；（6）在i层向上的电梯，在内部有k键按下，外部j层有向下键按下，先到k层后再回到j层；（7）在j层向上的电梯，在电梯内有i，k键被按下，则先到达k层后，i键被取消；（8）在j层向上的电梯，在电梯内有k键被按下，i层外有键按下，则先到k层再返回i层；（9）在j层向上的电梯，在电梯外i层k层有向下键按下，当电梯向上状态结束后，先到k层再到i层；（10）在电梯向下运动的过程中，与以上的行为相似，因此不再重述；（11）电梯内部的数字键和每一层楼电梯门外部的上下键一旦被按下就不能再由用户通过按键操作取消；（12）当电梯的乘客超员时，会提示超载并停止运行，直到轿厢内重量小于额定载重为止，电梯方可继续运行；二、DFA设计由于研究的是电梯的运行，所以自然想到以电梯的运行和停靠为DFA的基本状态。而用户的按键操作作为改变电梯运行状态的变量，所以依此构造状态转移函数。因为若单纯的考虑不同按键情况下的电梯的运行情况会发现按键组合过于复杂，所以必须分情况对不同的按键情况进行一定的整合。通过考察我们发现，不同的按键组合下，电梯都是首先收集所有的用户请求然后再按照一定的规律综合这些请求生成具体的指令，以便于最高效率地达到用户的目的，所以这些潜在的规律是构造我们的DFA的基础。而为了构造我们的DFA也需要以电梯基础的各种运行状况逐渐向深层分析电梯运行的规律，由此获得我们的DFA的状态转移函数。电梯的控制体统（一）DFA状态：根据行政楼电梯的楼层数，以及电梯向下、向上的实际不同情况，可将电梯分为以下几种状态：S1，S2，S3，S4，S5，S6Si表示电梯电梯停留在第i层（包括超重停靠的状态）；U1，U2,U3，U4，U5Ui表示电梯在第i层向上运行；D2,D3,D4,D5,D6Di表示电梯在第i层向下运行。（二）DFA输入：根据电梯的按键，电梯的输入可以用以下内容表示1，2，3，4，5，6i表示电梯内部相应楼层的按键被按下；1u，2u，3u，4u，5uiu表示电梯外部相应楼层的向上键被按下；2d，3d，4d，5d，6did表示电梯外部相应楼层的向下键被按下。在Si状态中会有一个特殊的输入W，这个输入仅会在Si状态出现，即超重输入。每个状态都应对所有的输入数据进行响应，但有些按键请求会被忽略。在电梯内的按键：1、例如当处在j层向上的电梯，一旦电梯停止后，会对电梯内部对i（ij）的按键请求进行忽略（即在电梯内按键低于j的会在到达当前上行的顶层时，自动取消）。即在向上状态时，只对大于等于当前层数的电梯内按键请求作出响应，小于当前层数的按键请求会被忽略；请求队列指令生成用户请求电梯运行指令电梯状态更新后队列请求队列指令生成用户请求电梯运行指令电梯状态更新后队列请求队列指令生成用户请求电梯运行指令电梯状态更新后队列2、当处在j层向下的电梯，一旦电梯停止后，会对电梯内部对i（ij）的按键请求进行忽略（即在电梯内按键高于j的会在到达当前下行的底层时，自动取消）。在电梯的向下状态时，只对小于等于当前层数的电梯内按键做响应，大于当前层数的按键请求会被忽略。在电梯外的按键：而当电梯处于向上状态时，会对大于等于当前层数的电梯外按键请求作出立即响应，小于等于当前层数中作出的按键请求会被放在所有向上的需求都处理结束后再作出响应；处于向下状态时，会对小于等于当前层数的电梯外按键请求作出响应，大于等于当前层数中作出的按键请求会被放在所有向下的需求都处理结束后再作出响应当电梯超重时，电梯不会运行，会在当前楼层保持停靠状态不动。（三）DFA输入处理：（1）电梯指令与用户请求的关系我们先根据电梯当前状态和用户的按键请求列出电梯最后所生成的指令，表示出来即以某种状态用户按键请求后，电梯会到达的状态。根据结果生成下表：纵列输入为电梯状态，横行输入为用户请求，输出为电梯生成指令，其中N代表暂不会立即为该请求去停于目标楼层。S1S2S3S4S5S6U1U2U3U4U5D2D3D4D5D61111111NNNNN1111122222222NNNNN2222333333333NNNNN3334444444444NNNNN4455555555555NNNNN5666666666666NNNNN1u111111NNNNN111112u2222222NNNNN22223u33333333NNNNN3334u444444444NNNNN445u5555555555NNNNN52d2222222NNNNN22223d33333333NNNNN3334d444444444NNNNN445d5555555555NNNNN56d66666666666NNNNN表-1（2）用户请求队列的处理电梯在实际使用的过程中，在同一时间可能会有多个用户请求，即可能需要按一定顺序依次停靠在多个楼层。我们可以用一六位二进制数表示123456iiiiii，其中ji=0表示j楼无请求，ji=1表示j楼有请求。例如100100表示3楼6楼有请求其他楼没有请求。我们需要再表示一下每种电梯状态时收到新的用户请求时，或者完成某个用户请求时，电梯的状态转移情况。这个过程有以下规律：用户请求指令可以将原状态对应位置的0更新为1，对应位置为1则不变；某请求完成指令可将原状态对应位置的1更新为0，对应位置为0则不变。有了这个状态转移的规律，我们就可以对电梯指令队列的改变有了清楚地认识。（3）电梯实际状态与请求队列生成控制指令做好了准备工作，我们就可以写出电梯的控制指令生成模块，在这个模块中根据电梯的位置和实际状态，以及在多个用户请求下生成的请求队列，生成实际控制电梯的控制指令。不同列表示不同的电梯运行状态Si为停靠在i楼，Ui为在i楼向上，Di为在i楼向下。（四）运行模块的DFA图对于不同状态的电梯，用户按下不同的按钮，对应不同的用户按键请求（表-1内容），电梯内部将这些请求汇总形成一个指令序列。该序列的信息与电梯不同的运行状态的信息会生成电梯的控制指令，这些指令对正在运行的电梯进行控制，也就是运行模块，我们通过画图进行表示：三、DFA表达式：{Q,Σ，δ，q0,F}Q={S1,S2,S3,S4,S5,S6,U1,U2,U3,U4,U5,D2,D3D4,D5,D6}Σ={1,3,4,5,6，w}1≤i≤6δ=(Si，w;i)=Siδ=(S1,2;3;4;5;6)=U1δ=(S2,3;4;5;6)=U2δ=(S3,4;5;6)=U3δ=(S4，5;6)=U4δ=(S5，6)=U5δ=(S2,1)=D2δ=(S3,1;2)=D3δ=(S4，1;2;3)=D4δ=(S5，1;2;3;4)=D5δ=(S6，1,2,3,4,5)=D6δ=(U1，1;2)=S2δ=(U1，1;2;3)=S3δ=(U1，3;4;5;6)=U2δ=(U1，4;5;6)=U3δ=(U2，3;4;5;6)=U3δ=(U3，1;2;3;4)=S4δ=(U2，1;2;3)=S3δ=(U3，5;6)=U4δ=(U4，1;2;3;4;5)=S5δ=(U4，6)=U5δ=(U5，1;2;3;4;5;6)=S6δ=(D2，1)=S1δ=(D3，2;3;4;5;6)=S2δ=(D3，1;2;3;4;5;6)=S1δ=(D4，3;4;5;6)=S3δ=(D4，1;2)=D3δ=(D3，1)=D2δ=(D5，4;5;6)=S4δ=(D5，1;2;3)=D4δ=(D6，5;6)=S5δ=(D6，1;2;3;4)=D5q0=S1F={S1,S2,S3,S4,S5,S6}