形式语言与自动机|DFA识别句子
source link: http://www.cnblogs.com/fisherss/p/12006862.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
实验二 DFA识别句子
一、实验目的
加深对DFA工作原理的理解。
二、实验内容
- 1.设计固定DFA。也就是说用if-then-else（一般用来实现字母表中只有两个字母的情况）、switch（大于两个字母的情况）、for（用于控制输入字符串，长度为n的字符串，for循环n次）等语句表示DFA。一个函数定义一个DFA；
- 2.设计文件形式存储DFA。设计文件格式，DFA动态生成，使用字符串来验证DFA的有效性和正确性；（使用面向对象的方法。对于k个状态的DFA，生成相应的k个状态对象；状态转换应通过对象间的消息传递来实现）
- 3.图形化表示。用java或者VC中图形功能实现图形化的dfa。（选作）
前置知识1：DFA
什么是FA，也叫有穷状态自动机；书上是这么说的:point_down:，是 一个五元组(状态集合，字母表，状态转移表，开始状态，终止状态集合)
什么是DFA，也是一个五元组，在FA的基础上加了一个 约束条件：每一个状态结点只能发出一条具有相同符号的边；也就是同一状态不能发出(输入字符相同的)两条边上。可以发出输入字符不同的多条边
下图就是一个 DFA 栗子:point_down:
下图就是 NFA 的栗子:point_down:(允许从一个状态发出多条具有相同符号的边，甚至允许发出标有ε（表示空）符号的边)
完成这个实验，只需要知道DFA就可以了。
前置知识2：有向图
什么是有向图：由顶点和有方向的边构成的图
如何在程序中存储有向图？
可以使用数据结构中学的“邻接矩阵”
“邻接矩阵”就是一个 “二维表”
DFA实质就是一个有向图，各个顶点和其它顶点之前，使用有向边相连接；而DFA的状态转移表，就是它的邻接矩阵。
开始写代码1.设计固定DFA
采用面向对象的方式编程，没有对象就new一个。
1-1：先写一个状态结点类
状态结点类的整体构造是这样的:point_down:
1-2：DFA类
DFA的整体构造是这样的:point_down:
5元组对应5个属性，其它还应该有状态表结点个数、字母表字符个数、最大存储的结点个数等属性。:point_down:
通过书上的一个DFA例子，理解一下状态集合、终结点集合、字母表集合是这样存储的:point_down:
1-3：几个必要的函数
1-4：选一个栗子
选用例3-1 有穷自动机M: ({q0,q1,q2},{0},转换函数,q0,{q2}) ，作为样例
这个自动机功能是：识别偶数个0，比如00是合法的句子；而000就是非法的句子。
状态转换表如下
下图是例题3-1的DFA图:point_down:
init()函数初始化例3-1的自动机:point_down:，把例3-1的五元组分别存储到实例对象的5个属性中
graphInit()函数初始化状态转换表
主要理解状态转换表(有向图的邻接矩阵):point_down:
状态集合、终结点集合、字母表集合是这样存储的:point_down:
然后试着理解状态转换表的存储:point_down:
1-5：核心，递归程序识别句子
run()启动函数:point_down:
dfs()核心递归程序:point_down:
1-6：运行，效果
例3-1的DFA，功能：只识别偶数个0的句子。
主函数：
运行效果：
开始写代码2.文件形式存储DFA
下次再写吧。
我太难了，给点个推荐吧。。。。有疑问可以在评论区提出
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK