【编译原理实验】Lab2（一）NFA确定化

您所在的位置：网站首页 › 编译原理将nfa确定化 › 【编译原理实验】Lab2（一）NFA确定化

【编译原理实验】Lab2（一）NFA确定化

2024-07-16 17:48| 来源: 网络整理| 查看: 265

目录一、实验目的二、实验任务三、实验内容四、实验步骤确定如何存NFA子集构造法-算法思想如何存储一个状态集？代码具体实现运行结果

一、实验目的

学习和掌握将NFA转为DFA的子集构造法。

二、实验任务

（1）存储NFA与DFA；（2）编程实现子集构造法将NFA转换成DFA。

三、实验内容

在这里插入图片描述

四、实验步骤确定如何存NFA

一个NFA如图所示在这里插入图片描述将NFA存在一个文件中，上图NFA表示信息如下

3 //字符数 a b c //字符集 10 //状态数，0 - n-1 0 //开始状态 9 //结束状态 12 //边数 0 a 1 //边的格式：起始状态边上的字符终结状态 1 # 2 //#表示空字符边 2 # 3 2 # 9 3 # 4 3 # 6 4 b 5 6 c 7 5 # 8 7 # 8 8 # 9 8 # 3 子集构造法-算法思想

NFA为什么要转DFA? 需要查看所有可能的状态转移结果，需要大量遍历、回溯在这里插入图片描述算法伪代码：

如何存储一个状态集？

set是一个不错的方法，因为还可以保证状态集中无重复状态，但是求状态集的并很麻烦（如果用并查集，用数组存状态集也很方便）。 vector，一维数组都很方便。

但是以上方法都是用一个容器来存，每个状态至少得用一个整数去表示，空间消耗还是较大的。于是按照自己定义的NFA的状态是从0 - n-1一个序列。考虑用一个int整数来存一个状态集。如果用int型最多可表示32位，如果需要更多状态，用long int或者数组。 int型变量占4字节，也就是32个二进制位，给二进制位编号0-31（从低位到高位）。如果第x位为1，则表示该状态集中包含了标号为x的状态。举个例子：上面图中NFA，状态0的闭包就是1（10进制）状态1的闭包是606（10进制） 606转二进制 10 0101 1110 从右往左从0开始数，第1位，第2位，第3位，第4位，第6位，第9位为1 因此表示状态集{s1,s2,s3,s4,s6,s9}。

接下来就需要用到一些位运算符（|,&,）

如何求状态集的并集？把两个int型整数按位或 |即可。

int x; int y; x|=y;

如何把一个状态加入状态集？等价于如何把某二进制位置为1

int s;//表示一个现有状态集 int x;//需要把x加入状态集 x |= (1> Begin >> End; int n;//NFA边数 in >> n; int x,y; char c; for(int i = 0;i > x >> c >> y; G[x][y] = c; } ZJGZ(); map mp;//DFA状态集映射到从0开始的状态标号 for(int i = 0;i

【本文地址】

【编译原理实验】Lab2（一）NFA确定化

【编译原理实验】Lab2（一）NFA确定化

今日新闻

推荐新闻