内容发布更新时间 : 2024/5/13 21:42:14星期一 下面是文章的全部内容请认真阅读。

课程设计报告

( 2011--2012年度第一学期)

名 称： 编译技术课程设计 题 目： 自动机的状态转换图表示 院 系： 控制与计算机工程学院 班 级： 信安 1001 学 号： 学生姓名： 指导教师：

设计周数： 一周

成 绩：

日期：2013年 1 月12日

课程设计报告

1 课程设计的目的和要求

1.1 课程设计的目的

本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。

1.2 课程设计的要求

1. 2. 3. 4.

要求设计一个具有绘图功能的程序，可以手工以状态转换图的方式绘制自动机； 图形化的自动机可以保存，读取；

根据状态转换图得出自动机的状态转换矩阵； 根据状态转换矩阵，自动绘制出状态转换图。

2 系统描述

本次课程设计是在win 7的环境下，使用visual C++6.0软件制作的一个多功能绘图软件。主要功能为描述一个确定的有限状态自动机，具体功能为绘制自动机，自动机转化为转移矩阵，转移矩阵自动转化为自动机。本课设中用圆圈表示状态，用大写字母表示，用弧线表示状态之间的转移关系，输入符号用小写字母表示，初态前面加箭头，终态集用双圆圈表示。

本次课程设计只针对简单的自动机，状态表示仅限于26个大写字符，输入符号仅限于26个小写字符，存在一定的局限性。本软件支持图形文件的读取和保存，同时，可以读取描述状态机的TXT文件（固定格式），自动绘制状态机

2.1 确定的自动机的描述

一个确定的又穷自动机M是一个五元组:M=(K，∑，f，S，Z)，其中： 1， K是一个有穷状态集，这里我们用单个大写字母表示 2， ∑是一个有穷输入符号集，这里我们用单个小写字母表示

3， f是状态间的转换函数，形如：f(K, a)=D，表示K状态输入字符a之后自动转换到D状

态

4， S是唯一的初态 5， Z是终态集

1

课程设计报告

2.2 状态转移矩阵的描述

一个确定的有限状态自动机还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符号后将要转换成的新状态，用“—>”表示初态，终态行在表尾部标以“1”，非终态标以“0”。

3 概要设计

3.1 概要设计

打开软件界面，点击进行绘图操作，先选中图形，在界面上点击，出现一个图元。选中图元，右击出现快捷菜单，选择更改图元属性或者删除图元，重复操作，直到把整个自动机绘制完成。

所有的图元都存放在CDocument类的两个链表中，这两条链分别为m_StatusList和m_RelationList，分别存放状态和关系图元。在OnDraw()函数中调用该链表进行绘图，保证图元可重复刷新和不丢失。

对关系图元，我们用两个变量分别标记它的开始图元和终止图元，以表示状态和关系之间的联系，在装换成状态装换矩阵时，我们用这种联系找到状态和输入符号之间的转换关系，做出状态转换矩阵

对于关系图元的位置，我们是根据其起始图元和终止图元的位置唯一确定的，这样，只要把状态图元的位置摆好了，关系弧也就不难画出来，根据这个巧妙的结构，在由转移矩阵绘制状态图时，我先设置状态的位置，然后关系弧线也就能轻而易举地画出来了。

3.2 系统用例图 绘制图元 选择图元 点击绘制 删除 读取文件 状态图 修改属性 保存状态图

用户 读取状态转换矩阵 图3-1 系统用例图 2 生成状态装换矩阵