NFA转DFA 感觉逻辑有问题，希望详细解答？如果能详细解答有帮助的悬赏100财富(用c++实现，NFA到DFA的转换，请教高手。)
用c++实现，NFA到DFA的转换，请教高手。
#include "stdafx.h"
#include <vector>
#include <string>
#include <queue>
#include <iostream>
using namespace std;
struct Transform
{
friend class FA;
char state1;
char letter;
char state2;
bool operator!=(char ch);
friend istream& operator>>(istream& in,Transform& t);
};
struct ChangeTable
{
string state;
int flag;
vector<string> changestate;
};
bool Transform::operator!=(char ch)
{
return state1!=ch||letter!=ch||state2!=ch;
}
namespace std
{
istream& operator>>(istream& in,Transform& t)
{
return in>>t.state1>>t.letter>>t.state2;
}
}
class FA
{
private:
vector<char> state; //状态集
vector<char> table; //输入字母表
vector<Transform> fun; //状态变迁函数
char q0; //初态
vector<char> Z; //终态集
string GetChangeState(char state1,char table);
void RemoveRepeat(string &str); //消除重复元素
private:
vector<ChangeTable> changetable;
bool IsInChangeTable(string str);
int GetIndexofChangeTable(); //找出第一个flag为0的索引
int GetIndexofChangeTable(string str); //找出str 在表中的索引
void GetChangeTable();
void OutputChangeTable();
public:
// FA(){}
void Deterministic(FA &dfa);
void input();
void output();
};
void FA::RemoveRepeat(string &str)
{
string mid;
string::size_type idx;
string::iterator pos;
for(pos=str.begin();pos!=str.end();++pos)
{
idx=mid.find(*pos);
if(idx==string::npos)
mid+=*pos;
}
str=mid;
}
bool FA::IsInChangeTable(string str)
{
vector<ChangeTable>::iterator pos;
for(pos=changetable.begin();pos!=changetable.end();++pos)
if((*pos).state==str)
return 1;
return 0;
}
int FA::GetIndexofChangeTable()
{
int index;
for(index=0;index<changetable.size();++index)
if(changetable[index].flag==0)
return index;
return -1;
}
int FA::GetIndexofChangeTable(string str)
{
int index;
for(index=0;index<changetable.size();++index)
if(changetable[index].state==str)
return index;
return -1;
}
string FA::GetChangeState(char state1,char table)
{
string str;
vector<Transform>::iterator pos;
for(pos=fun.begin();pos!=fun.end();++pos)
if((*pos).state1==state1&&(*pos).letter==table)
str+=(*pos).state2;
RemoveRepeat(str);
return str;
}
void FA::input()
{
char ch;
Transform tran;
cout<<"input the set of state,ended with '#'"<<endl;
cin>>ch;
while(ch!='#')
{
state.push_back(ch);
cin>>ch;
}
cout<<"input the set of input's table,ended with '#'"<<endl;
cin>>ch;
while(ch!='#')
{
table.push_back(ch);
cin>>ch;
}
cout<<"input the transform of function,formation is state1 letter state1 "<<endl;
cout<<"ended with '# # #'"<<endl;
cin>>tran;
while(tran!='#')
{
fun.push_back(tran);
cin>>tran;
}
cout<<"input the state of Initlization table"<<endl;
cin>>q0;
cout<<"input the set of termination,ended with '#'"<<endl;
cin>>ch;
while(ch!='#')
{
Z.push_back(ch);
cin>>ch;
}
}
void FA::GetChangeTable()
{
ChangeTable ct,midct;
string str;
string mid;
queue<string> q;
vector<char>::iterator pos;
string::iterator p;
ct.state=string(1,q0); //从初始状态开始
ct.flag=0;
changetable.push_back(ct);
int index=GetIndexofChangeTable();
while(index!=-1)
{
changetable[index].flag=1;
str=changetable[index].state; //弹出状态
for(pos=table.begin();pos!=table.end();++pos) //每种输入状态
{
mid.erase();
for(p=str.begin();p!=str.end();++p) //每个状态的每个字符
{
mid+=GetChangeState(*p,*pos);
RemoveRepeat(mid);
}
changetable[index].changestate.push_back(mid);
if(!mid.empty()&&!IsInChangeTable(mid))
{
ct.state=mid;
ct.flag=0;
changetable.push_back(ct);
}
}
index=GetIndexofChangeTable();
}
}
void FA::OutputChangeTable()
{
vector<ChangeTable>::iterator pos;
for(pos=changetable.begin();pos!=changetable.end();++pos)
{ cout<<"{"<<(*pos).state<<"} ";
for(int i=0;i<(*pos).changestate.size();i++)
cout<<"{"<<(*pos).changestate[i]<<"} ";
cout<<endl;
}
}
void FA::Deterministic(FA &dfa)
{
GetChangeTable();
//OutputChangeTable(); //输出中间状态转换表
dfa.table=table;
int size=0;
while(size<changetable.size()) //求状态集
{
dfa.state.push_back('A'+size);
size++;
}
dfa.q0='A'; //求初态
Transform tran;
vector<string>::iterator pos;
vector<char>::iterator p;
for(int i=0;i<changetable.size();++i)
{
tran.state1='A'+i;
for(p=table.begin(),pos=changetable[i].changestate.begin();pos!=changetable[i].changestate.end();++pos,++p)
{
tran.letter=*p;
int index=GetIndexofChangeTable(*pos);
tran.state2='A'+index;
if(index!=-1)
dfa.fun.push_back(tran);
}
//下面来求终态集
string mid;
string str=changetable[i].state;
for(p=Z.begin();p!=Z.end();++p)
{
mid.erase();
mid+=*p;
}
int idx=str.find(mid);
if(idx!=string::npos)
dfa.Z.push_back('A'+i);
}
}
void FA::output()
{
vector<char>::iterator pos;
cout<<"M={Vn,Vt,F,q0,Z},其中:"<<endl;
cout<<"Vn={";
for(pos=state.begin();pos!=state.end()-1;++pos)
cout<<*pos<<",";
cout<<*pos<<"}"<<endl;
cout<<"Vt={";
for(pos=table.begin();pos!=table.end()-1;++pos)
cout<<*pos<<",";
cout<<*pos<<"}"<<endl;
cout<<"F is:"<<endl;
for(std::vector<Transform>::iterator p=fun.begin();p!=fun.end();++p)
cout<<"f("<<(*p).state1<<","<<(*p).letter<<")="<<(*p).state2<<endl;
cout<<"q0="<<q0<<endl;
cout<<"Z={";
for(pos=Z.begin();pos!=Z.end()-1;++pos)
cout<<*pos<<",";
cout<<*pos<<"}"<<endl;
}
int main(int argc, char* argv[])
{
FA nfa,dfa;
nfa.input();
nfa.output();
nfa.Deterministic(dfa);
cout<<"转换成DFA为:"<<endl;
dfa.output();
return 0;
}
来源:http://topic.csdn/t/20041024/23/3486893.html
编译原理中为什么要将NFA转化为DFA
编译原理中DFA是确定的有限自动机，而NFA是非确定有限自动机，将NFA化为DFA是将状态数减少，更为简单确定
希望能给你帮助。
如何判别流程图是DFA还是nfa？
流程图（Flow Chart）：使用图形表示算法的思路是一种极好的方法，因为千言万语不如一张图。以特定的图形符号加上说明，表示算法的图，称为流程图或框图。流程图是流经一个系统的信息流、观点流或部件流的图形代表。在企业中，流程图主要用来说明某一过程。这种过程既可以是生产线上的工艺流程，也可以是完成一项任务必需的管理过程。例如，一张流程图能够成为解释某个零件的制造工序，甚至组织决策制定程序的方式之一。这些过程的各个阶段均用图形块表示，不同图形块之间以箭头相连，代表它们在系统内的流动方向。下一步何去何从，要取决于上一步的结果，典型做法是用“是”或“否”的逻辑分支加以判断。流程图是揭示和掌握封闭系统运动状况的有效方式。作为诊断工具，它能够辅助决策制定，让管理者清楚地知道，问题可能出在什么地方，从而确定出可供选择的行动方案。流程图有时也称作输入-输出图。该图直观地描述一个工作过程的具体步骤。流程图对准确了解事情是如何进行的，以及决定应如何改进过程极有帮助。这一方法可以用于整个企业，以便直观地跟踪和图解企业的运作方式。流程图使用一些标准符号代表某些类型的动作，如决策用菱形框表示，具体活动用方框表示。但比这些符号规定更重要的，是必须清楚地描述工作过程的顺序。流程图也可用于设计改进工作过程，具体做法是先画出事情应该怎么做，再将其与实际情况进行比较。
为正规式(a|b)*a(a|b)构造最简DFA。
|先化成带空转移的dfa，在去空符号。构造正规式1(0|1)*101相应的DFA。
(A|B)*表示A或者B出现若干次或者不出现。
(A*B*)* A出现若干次或者不出现，B出现若干次或者不出现，一起出现若干次或者不出现
(A*|B*)* A出现若干次或者不出现或者B出现若干次或者不出现，一起出现若干次或者不出现。
任何一个字符串都匹配这个字符串。
扩展资料：
正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式。
就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。