NFA确定化

一、实验目的：

1．设计、编制、调试一个确定有穷自动机的程序，加深对DFA确定化原理的理解。

2．掌握在对程序设计DFA确定化的过程。

二、实验要求：

1. NFA到DFA的转换过程

2. NFA初始状态集的λ合并集作为DFA的初始状态

3. 对DFA中一状态S，对a∈∑,进行符号合并和λ合并得到的状态设为S’,定义DFA的转换函数为f(S,a)=S’

三、实验环境：

Windows下的 Microsoft Visual C++ 6.0 或Visual Studio 2008;

四、实验步骤

1.查询资料，了解NFA确定化的工作过程与原理。

2.分析题目，整理出基本设计思路。

3.实践编码，将设计思想转换用c语言编码实现，编译运行。

五、调试程序：

举例说明

1、错误输入时

六、实验心得：

1：

通过此次实验，让我对老师在课堂上讲的有关DFA(确定有穷自动机)、NFA(非确定有穷自动机)的知识有了更深的理解，如它们的构造以及相互转化。在编写程序的过程中我们对C语言中有关数据结构及其相关的知识进行了复习，这更有利于我们目标的实现。在本次实验中，让我进一步的认识到组员的重要性，当遇到困难时，通过讨论、分析才能更好更快的解决问题，完成共同的任务。

2：

通过本次实验进一步的了解并掌握NFA确定化的运用，同时发现自己对关于NFA的很多知识不是很熟，运用的也不好。但是通过和同学的配合和学习知道了NFA，DFA的本质内容及其功能，以后会更多的学习这些知识，更好的掌握和熟练的运用所学的知识。

附录：

#include

#include

#include

#include

using namespace std;

///---------------------Function-------------------------------

void NFA_Input();

void Set_Insert(vector& vec, char ch);

bool Matching(vector >& Source, vector& Target);

vector EPSILON_CLOSURE(vector& T);

vector Transf(vector& vec, char ch);

void DFA_Output();

void Output(vector& vec);

///--------------------NFA-------------------------------------

struct Edge

{

char stat1;

char ch;

char stat2;

};

vector Alpha;

vector N_Stat;

vector N_Start;

vector N_End;

vector N_Transfer;

vector E_Transfer; //带 '~' 的状态转换

const char EPSILON = '~';

///--------------------DFA 部分---------------------------------

vector > D_Stats;

vector > D_End;

vector D_Start;

//-----------------------------------------------------------------------------

// 主函数

//-----------------------------------------------------------------------------

int main()

{

cout << "--------------------NFA-----------------" << endl;

NFA_Input();

D_Start = EPSILON_CLOSURE(N_Start); //NFA初态的闭包为DFA的初态

D_Stats.push_back(D_Start);

stack > Q;

Q.push(D_Start);

cout << "\n--------------------NFA-----------------" << endl

<< "Status transfer:" << endl

<< "Input stat\t" ;

for(vector::size_type i = 0; i != Alpha.size(); i++)

cout << Alpha[i] << "\t" ;

cout << endl;

vector V, T;

while(!Q.empty())

{

T = EPSILON_CLOSURE(Q.top());

Q.pop(); V.clear();

Output(T);

for(vector::size_type i = 0; i != Alpha.size(); i++)

{

V = Transf(T, Alpha[i]);

V = EPSILON_CLOSURE(V);

if((V.size() != 0)&&!Matching(D_Stats, V))

{

D_Stats.push_back(V);

Q.push(V);

}

Output(V);

}

cout << endl;

}

DFA_Output();

system("PAUSE");

return 0;

}

//-----------------------------------------------------------------------------

// NFA 输入

//-----------------------------------------------------------------------------

void NFA_Input()

{

char ch;

cout << "Input the Status(End With '#'):" << endl;

while(cin >> ch, ch != '#')

N_Stat.push_back(ch);

sort(N_Stat.begin(), N_Stat.end());

cout << "\nInput the Alpha(End With '#'):" << endl;

while(cin >> ch, ch != '#')

Alpha.push_back(ch);

sort(Alpha.begin(), Alpha.end());

cout << "\nInput the Status Transform Function: " << endl

<< " Input format: Q0 a Q1" << endl

<< " End format: # # #" << endl

<< " Use '~' instead of 'ε'." << endl;

while(1)

{

Edge edge;

cin >> edge.stat1;

cin >> edge.ch;

cin >> edge.stat2;

if(edge.stat1 == '#' && edge.ch == '#' && edge.stat2 == '#' )

break;

if(edge.ch == EPSILON)

E_Transfer.push_back(edge);

else

N_Transfer.push_back(edge);

}

cout << "\nInput the Start Status(End With '#'):" << endl;

while(cin >> ch, ch != '#')

N_Start.push_back(ch);

sort(N_Start.begin(), N_Start.end());

cout << "\nInput the End Status(End With '#'):" << endl;

while(cin >> ch, ch != '#')

N_End.push_back(ch);

sort(N_End.begin(), N_End.end());

}

//----------------------------------------------------------------------------

// stat_set Match

//----------------------------------------------------------------------------

bool Matching(vector >& Source, vector& Target)

{

bool flag;

vector >::size_type i;

for(i = 0; i != Source.size(); i++)

{

if(Source[i].size() != Target.size())

continue;

flag = true;

for(vector::size_type j = 0; j != Target.size(); ++j)

if(Source[i][j] != Target[j])

{

flag = false;

break;

}

if(flag)

return true;

}

return false;

}

//----------------------------------------------------------------------------

// Insert a stat into a stat set

//----------------------------------------------------------------------------

void Set_Insert(vector& vec, char ch)

{

if(find(vec.begin(), vec.end(), ch) == vec.end())

{

vec.push_back(ch);

sort(vec.begin(), vec.end());

}

}

//-----------------------------------------------------------------------------

// Epsilon Closure

//-----------------------------------------------------------------------------

vector EPSILON_CLOSURE(vector& T)

{

stack > S(T);

vector vec(T);

vector::iterator iter;

char v;

while (!S.empty())

{

v = S.top(); S.pop();

for(iter = E_Transfer.begin(); iter != E_Transfer.end(); iter++)

{

//if(((*iter).stat1 == v) && ((*iter).ch == EPSILON))

if((*iter).stat1 == v)

{

Set_Insert(vec, (*iter).stat2);

S.push((*iter).stat2);

}

}

}

return vec;

}

//----------------------------------------------------------------------------

// 转换函数,求 F(stat, ch)

//----------------------------------------------------------------------------

vector Transf(vector& vec, char ch)

{

vector T;

vector::iterator iter;

vector::size_type j;

for(iter = vec.begin(); iter != vec.end(); iter++)

for(j = 0; j != N_Transfer.size(); j++)

{

if((*iter == N_Transfer[j].stat1) && (N_Transfer[j].ch == ch))

Set_Insert(T, N_Transfer[j].stat2);

}

return T;

}

//----------------------------------------------------------------------------

// DFA 状态输出

//----------------------------------------------------------------------------

void DFA_Output()

{

cout << "All status:" << endl;

for(vector >::size_type i = 0; i != D_Stats.size(); i++)

{

for(vector::size_type j = 0; j != N_End.size(); j++)

if( find(D_Stats[i].begin(), D_Stats[i].end(), N_End[j]) != D_Stats[i].end())

{

D_End.push_back(D_Stats[i]);

break;

}

Output(D_Stats[i]);

cout << endl;

}

cout << "Start status: " ;

Output(D_Start); cout << endl;

cout << "End status: ";

for(vector >::size_type i = 0; i != D_End.size(); i++)

{

Output(D_End[i]);

cout << endl;

}

}

//----------------------------------------------------------------------------

// 输出辅助函数

//----------------------------------------------------------------------------

inline void Output(vector& vec)

{

vector::size_type i=0;

cout << "{ ";

for(i = 0; i != vec.size(); i++)

cout << vec[i] << " ";

cout << "}" << " ";

}

本文来源：https://www.2haoxitong.net/k/doc/7e9c562658fb770bf78a55d0.html