课程设计报告(2011--2012年度第一学期)名称：编译技术课程设计题目：自动机的状态转换图表示院系：控制与计算机工程学院班级：信安1001学号：学生姓名：指导教师：设计周数：一周成绩：日期：2013年1月12日课程设计报告1课程设计的目的和要求1.1课程设计的目的本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。1.2课程设计的要求要求设计一个具有绘图功能的程序，可以手工以状态转换图的方式绘制自动机；图形化的自动机可以保存，读取；根据状态转换图得出自动机的状态转换矩阵；根据状态转换矩阵，自动绘制出状态转换图。2系统描述本次课程设计是在win7的环境下，使用visualC++6.0软件制作的一个多功能绘图软件。主要功能为描述一个确定的有限状态自动机，具体功能为绘制自动机，自动机转化为转移矩阵，转移矩阵自动转化为自动机。本课设中用圆圈表示状态，用大写字母表示，用弧线表示状态之间的转移关系，输入符号用小写字母表示，初态前面加箭头，终态集用双圆圈表示。本次课程设计只针对简单的自动机，状态表示仅限于26个大写字符，输入符号仅限于26个小写字符，存在一定的局限性。本软件支持图形文件的读取和保存，同时，可以读取描述状态机的TXT文件（固定格式），自动绘制状态机2.1确定的自动机的描述一个确定的又穷自动机M是一个五元组:M=(K，∑，f，S，Z)，其中：K是一个有穷状态集，这里我们用单个大写字母表示∑是一个有穷输入符号集，这里我们用单个小写字母表示f是状态间的转换函数，形如：f(K,a)=D，表示K状态输入字符a之后自动转换到D状态S是唯一的初态Z是终态集2.2状态转移矩阵的描述一个确定的有限状态自动机还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符号后将要转换成的新状态，用“—>”表示初态，终态行在表尾部标以“1”，非终态标以“0”。3概要设计3.1概要设计打开软件界面，点击进行绘图操作，先选中图形，在界面上点击，出现一个图元。选中图元，右击出现快捷菜单，选择更改图元属性或者删除图元，重复操作，直到把整个自动机绘制完成。所有的图元都存放在CDocument类的两个链表中，这两条链分别为m_StatusList和m_RelationList，分别存放状态和关系图元。在OnDraw()函数中调用该链表进行绘图，保证图元可重复刷新和不丢失。对关系图元，我们用两个变量分别标记它的开始图元和终止图元，以表示状态和关系之间的联系，在装换成状态装换矩阵时，我们用这种联系找到状态和输入符号之间的转换关系，做出状态转换矩阵对于关系图元的位置，我们是根据其起始图元和终止图元的位置唯一确定的，这样，只要把状态图元的位置摆好了，关系弧也就不难画出来，根据这个巧妙的结构，在由转移矩阵绘制状态图时，我先设置状态的位置，然后关系弧线也就能轻而易举地画出来了。状态图选择图元点击绘制修改属性绘制图元读取文件读取状态转换矩阵删除保存状态图生成状态装换矩阵3.2系统用例图用户图3-1系统用例图3.3系统用例表3-1绘制自动机状态图用例名称绘制自动机状态图简述用鼠标点击结合键盘输入方式绘制自动机状态图前置条件打开软件基本流在软件菜单或工具栏中选中需要绘制的图元鼠标光标变成十字架形状，表示已经进入绘图状态若是绘制状态，鼠标左击窗口空白处，绘制相应的状态，状态默认为S；若是绘制关系，鼠标依次点击想要绘制的起点和终点，绘制相应的关系，输入符号默认为a选中绘制的状态圆或者关系弧（选中的图形会出现小方格表示选中状态），右击，出现快捷菜单，选择“删除”菜单来删除图元，选择“属性”菜单来修改图元的状态和输入符号重复步骤3,4，直到图形绘制完成备选流2.1鼠标右击，取消绘图，鼠标变成箭头形式3.1绘制一个图形后，光标回到初始状态，绘图结束，若需要继续画图，需重新选择图元。3.2绘制关系弧线时，若没有选择图元，光标回到初始状态，绘图结束3.3允许绘制从一个状态回到该状态本身的弧。4.1删除状态时应先删除和它联系的关系弧，否则会出错4.2允许一个状态既是初态又是终态，只需要在属性栏中将“初态”和“终态”多选框都选上4.3允许一条弧上有多个输入符号，只需要选择弧，右击选择“属性”菜单，用“重置”和“添加”按钮设置输入符号，输入符号不允许空后置条件自动机状态图绘制完成特殊需求只能绘制指定的图元，关系只能绘制成弧线待解决问题3.1由于弧线的确定是根据状态位置来的，所以不允许两个状态之间有两条同向的