实验一 利用子集法构造DFA

实验一 利用子集法构造DFA

一、实验目的

掌握将非确定有限自动机确定化的方法和过程

二、实验要求及内容

实验要求：

1.输入一个NFA，输出一个接受同一正规集的DFA； 2.采用C++语言，实现该算法； 3.编制测试程序； 4.调试程序。 实验步骤：

1.输入一个NFA关系图；

2.通过一个转换算法将NFA转换为DFA； 3.显示DFA关系图。

三、实验环境

计算机、Windows 操作系统、Visual C++ 程序集成环境。

四、程序代码

#include \#include #include #include #include #include using namespace std; struct edge{ int start,end; char c; }

E[100],Ekong[100];//E保存所有的边，Ekong保存转换字符为空的边 struct State{

int H[100];//状态集合

int count;//状态集合中的元素个数 int flag;//是否是接受状态 int mark;//状态编号 };

int n;//n:边数

1

int nk=0;//空字符转换的边数

int first,accept;//开始状态，接受状态 char alpha[100];//输入字母表,#代表空串 int numof_char=0;//字母表中的字符个数 int useof_char[256];//该转换字符是否用过

int f[200];//状态属性标志：0表示始态，1表示接受态，-1表示中间态 State DFA[100];//DFA状态集

int useof_DFA[100];//标志构造出来的状态是否已存在 int numof_Dtran=0;//最后得到的DFA中的状态数 char Dtran[100][100];//DFA状态转换表 void input() {

int i,s,e; char ch;

cout<<\请输入转换的有向边数n：\cin>>n;

cout<<\请输入NFA的开始状态：\cin>>first;

cout<<\请输入NFA的接受状态(输入-1结束)：\memset(f,-1,sizeof(f));

memset(useof_char,0,sizeof(useof_char)); f[first]=0; cin>>accept; while(accept!=-1) {

f[accept]=1; }

cout<<\请输入NFA，起点，终点，转换字符('#'表示空字符)：\int k=0;

for(i=0;i

cin>>s>>e>>ch; E[i].start=s; E[i].end=e; E[i].c=ch;

if(ch!='#'&&!useof_char[ch]) {

cin>>accept;

alpha[numof_char++]=ch; useof_char[ch]=1;

}

if(ch=='#') {

Ekong[nk].start=s;

2

Ekong[nk].end=e; Ekong[nk].c=ch; nk++; } }

State move(State T,char s)//c!='#' {

State temp; temp.count=0; temp.mark=T.mark; int i,j=0,k=0;

for(i=0;i

while(j

}

if(E[j].start==T.H[i]&&E[j].c==s) { temp.H[temp.count++]=E[j].end; } j++; } }

return temp; }

void arriveBynone(int t,int result[],int& num)//搜索状态t通过一个或多个空字符到达的状态,结果存在result中 { int k=0; int m=0; num=0; stack S; S.push(t); int j;

while(!S.empty()) {

j=S.top(); S.pop(); m=0; while(m

if(Ekong[m].start==j) {

result[num++]=Ekong[m].end;

3

} }

bool check(int i,State T)//判断状态i是否在T中 { int j;

for(j=0;j

if(T.H[j]==i) return true; }

return false; }

State closure(State T)//求闭包 {

stack STACK; State temp; int i,j,k;

for(i=0;i

temp.count=T.count; temp.mark=T.mark; }

}

while(!STACK.empty()) {

int t=STACK.top(); STACK.pop();

//搜索状态t通过一个或多个空字符到达的状态 int search_result[100]; int num;

arriveBynone(t,search_result,num); for(j=0;j

if(!check(search_result[j],temp)) {

temp.H[temp.count++]=search_result[j]; STACK.push(search_result[j]);

STACK.push(T.H[i]); temp.H[i]=T.H[i]; S.push(Ekong[m].end);

} m++; }

4

}

for(k=0;k

sort(temp.H,temp.H+temp.count); for(i=0;i

return temp; }

int check_inDFA()//检查DFA中是否存在未被标记的状态,有则返回标号，否则返回-1 { }

return -1; }

bool check_whetherin_DFA(State T) { int i,j;

sort(T.H,T.H+T.count);

int i;

for(i=0;i

if(!useof_DFA[i]) return i;

if(temp.count!=DFA[i].count) continue;

sort(DFA[i].H,DFA[i].H+DFA[i].count); for(j=0;j

if(DFA[i].H[j]!=temp.H[j]) break; }

if(j>=DFA[i].count) temp.mark=DFA[i].mark;

if(f[temp.H[k]]==1) {

temp.flag=1; break; }

if(f[temp.H[k]]==0) {

temp.flag=0; }

break;

5

for(i=0;i

if(i>=numof_Dtran) }

void child_method() { int m,n;

for(m=0;m<100;m++)

for(n=0;n<100;n++)

Dtran[m][n]='#'; DFA[m].flag=-1; for(m=0;m<100;m++) State S0,U;

return false; return true;

else

if(T.count!=DFA[i].count) continue;

sort(DFA[i].H,DFA[i].H+DFA[i].count); for(j=0;j

if(DFA[i].H[j]!=T.H[j]) break; }

if(j>=DFA[i].count) return true;

S0.flag=0; S0.count=1; S0.H[0]=first; State T; T=closure(S0); T.mark=0; T.flag=0;

DFA[numof_Dtran++]=T;

memset(useof_DFA,0,sizeof(useof_DFA)); int j=check_inDFA();

int k; while(j!=-1) {

useof_DFA[j]=1;

for(k=0;k

U=closure(move(DFA[j],alpha[k]));

6

} }

void print() { int i,j;

for(i=0;i

cout<

for(i=0;i

void judge(string ch) {

int i,j,k; State temp; k=0;

for(i=0;i

for(j=0;j

int num=ch.length();

for(j=0;j

{ cout<

cout<

for(j=0;j

cout<<\此为DFA的接受状态\if(DFA[i].flag==0)

cout<<\此为DFA的开始状态\cout<

//if U不在DFA中

if(!check_whetherin_DFA(U)) { U.mark=numof_Dtran; }

Dtran[DFA[j].mark][U.mark]=alpha[k]; }

j=check_inDFA();

DFA[numof_Dtran++]=U;

7

}

if(temp.flag!=1) }

int _tmain(int argc, _TCHAR* argv[]) { input(); child_method(); cout<>s)

judge(s);

system(\return 0; }

cout<<\字符串 \无法由该DFA得到\cout<<\字符串 \可以由该DFA得到\

else cout<

if(Dtran[k][j]==alpha[i]) { } }

temp=DFA[j]; k=j; break;

五、实验结果

8

六、算法分析

使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量。相比子集构造法,算法能更有效地对非确定有限自动机进行确定化。

七、实验小结

以前上课时有许多的问题并没有真正的认识到，但通过这次实验，使我掌握了许多更重要的知识点。通过实验，我们可以知道将NFA转换成接受同样语言的DFA的算法称为子集构造算法。NFA变换到DFA的基本思想是：让DFA的每个状态对应NFA的一个状态集。实验实现了NFA到DFA的转换。

实验二 THOMPSON 算法的实现

一、实验目的

掌握将正规表达式转换为NFA的方法和过程

三、实验要求及内容

1. 输入一个正规表达式，输出一个接受同一语言的NFA 2. 采用C++语言，实现该算法 3. 编制测试程序 4. 调试程序

三、实验环境

计算机、Windows 操作系统、Visual C++ 程序集成环境。

四、程序代码

#include \void main() {

9

string Regular_Expression = \ cell NFA_Cell;

input(Regular_Expression);//调试需要先屏蔽

Regular_Expression = add_join_symbol(Regular_Expression); Regular_Expression = postfix(Regular_Expression); NFA_Cell = express_2_NFA(Regular_Expression); Display(NFA_Cell);

}

cell express_2_NFA(string expression) {

int length = expression.size(); char element; cell Cell,Left,Right; stack STACK; for(int i=0;i

case '|': Right = STACK.top(); STACK.pop(); Left = STACK.top(); STACK.pop();

Cell = do_Unite(Left,Right); STACK.push(Cell); break;

case '*':

Left = STACK.top(); STACK.pop();

Cell = do_Star(Left); STACK.push(Cell); break;

case '+':

Right = STACK.top(); STACK.pop(); Left = STACK.top(); STACK.pop();

Cell = do_Join(Left,Right); STACK.push(Cell); break;

default:

Cell = do_Cell(element);

STACK.push(Cell);

10

本文来源：https://www.bwwdw.com/article/rslf.html