JAVA实现nfa到dfa的转换_用c++实现，NFA到DFA的转换，请教高手。讲一下思想。

展开全部

#include "stdafx.h"

#include

#include

#include

#include

using namespace std;

struct Transform

{

friend class FA;

char state1;

char letter;

char state2;

bool operator!&＃61;(char ch);

friend istream& operator>>(istream& in,Transform& t);

};

struct ChangeTable

{

string state;

int flag;

vector changestate;

};

bool Transform::operator!&＃61;(char ch)

{

return state1!&＃61;ch||letter!&＃61;ch||state2!&＃61;ch;

}

namespace std

{

istream& operator>>(istream& in,Transform& t)

{

return in>>t.state1>>t.letter>>t.state2;

}

}

class FA

{

private:

vector state; //状态集

vector table; //输入字母表

vector fun; //状态变迁函数

char q0; //初态

vector Z; //终态集

string GetChangeState(char state1,char table);

void RemoveRepeat(string &str); //消除重复元素

private:

vector changetable;

bool IsInChangeTable(string str);

int GetIndexofChangeTable(); //找出第一个flag为0的索引e5a48de588b662616964757a686964616f31333238653266

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&＃61;str.begin();pos!&＃61;str.end();&＃43;&＃43;pos)

{

idx&＃61;mid.find(*pos);

if(idx&＃61;&＃61;string::npos)

mid&＃43;&＃61;*pos;

}

str&＃61;mid;

}

bool FA::IsInChangeTable(string str)

{

vector::iterator pos;

for(pos&＃61;changetable.begin();pos!&＃61;changetable.end();&＃43;&＃43;pos)

if((*pos).state&＃61;&＃61;str)

return 1;

return 0;

}

int FA::GetIndexofChangeTable()

{

int index;

for(index&＃61;0;index

if(changetable[index].flag&＃61;&＃61;0)

return index;

return -1;

}

int FA::GetIndexofChangeTable(string str)

{

int index;

for(index&＃61;0;index

if(changetable[index].state&＃61;&＃61;str)

return index;

return -1;

}

string FA::GetChangeState(char state1,char table)

{

string str;

vector::iterator pos;

for(pos&＃61;fun.begin();pos!&＃61;fun.end();&＃43;&＃43;pos)

if((*pos).state1&＃61;&＃61;state1&&(*pos).letter&＃61;&＃61;table)

str&＃43;&＃61;(*pos).state2;

RemoveRepeat(str);

return str;

}

void FA::input()

{

char ch;

Transform tran;

cout<

cin>>ch;

while(ch!&＃61;&＃39;#&＃39;)

{

state.push_back(ch);

cin>>ch;

}

cout<

cin>>ch;

while(ch!&＃61;&＃39;#&＃39;)

{

table.push_back(ch);

cin>>ch;

}

cout<

cout<

cin>>tran;

while(tran!&＃61;&＃39;#&＃39;)

{

fun.push_back(tran);

cin>>tran;

}

cout<

cin>>q0;

cout<

cin>>ch;

while(ch!&＃61;&＃39;#&＃39;)

{

Z.push_back(ch);

cin>>ch;

}

}

void FA::GetChangeTable()

{

ChangeTable ct,midct;

string str;

string mid;

queue q;

vector::iterator pos;

string::iterator p;

ct.state&＃61;string(1,q0); //从初始状态开始

ct.flag&＃61;0;

changetable.push_back(ct);

int index&＃61;GetIndexofChangeTable();

while(index!&＃61;-1)

{

changetable[index].flag&＃61;1;

str&＃61;changetable[index].state; //弹出状态

for(pos&＃61;table.begin();pos!&＃61;table.end();&＃43;&＃43;pos) //每种输入状态

{

mid.erase();

for(p&＃61;str.begin();p!&＃61;str.end();&＃43;&＃43;p) //每个状态的每个字符

{

mid&＃43;&＃61;GetChangeState(*p,*pos);

RemoveRepeat(mid);

}

changetable[index].changestate.push_back(mid);

if(!mid.empty()&&!IsInChangeTable(mid))

{

ct.state&＃61;mid;

ct.flag&＃61;0;

changetable.push_back(ct);

}

}

index&＃61;GetIndexofChangeTable();

}

}

void FA::OutputChangeTable()

{

vector::iterator pos;

for(pos&＃61;changetable.begin();pos!&＃61;changetable.end();&＃43;&＃43;pos)

{ cout<

for(int i&＃61;0;i

cout<

cout<

}

}

void FA::Deterministic(FA &dfa)

{

GetChangeTable();

//OutputChangeTable(); //输出中间状态转换表

dfa.table&＃61;table;

int size&＃61;0;

while(size

{

dfa.state.push_back(&＃39;A&＃39;&＃43;size);

size&＃43;&＃43;;

}

dfa.q0&＃61;&＃39;A&＃39;; //求初态

Transform tran;

vector::iterator pos;

vector::iterator p;

for(int i&＃61;0;i

{

tran.state1&＃61;&＃39;A&＃39;&＃43;i;

for(p&＃61;table.begin(),pos&＃61;changetable[i].changestate.begin();pos!&＃61;changetable[i].changestate.end();&＃43;&＃43;pos,&＃43;&＃43;p)

{

tran.letter&＃61;*p;

int index&＃61;GetIndexofChangeTable(*pos);

tran.state2&＃61;&＃39;A&＃39;&＃43;index;

if(index!&＃61;-1)

dfa.fun.push_back(tran);

}

//下面来求终态集

string mid;

string str&＃61;changetable[i].state;

for(p&＃61;Z.begin();p!&＃61;Z.end();&＃43;&＃43;p)

{

mid.erase();

mid&＃43;&＃61;*p;

}

int idx&＃61;str.find(mid);

if(idx!&＃61;string::npos)

dfa.Z.push_back(&＃39;A&＃39;&＃43;i);

}

}

void FA::output()

{

vector::iterator pos;

cout<

cout<

for(pos&＃61;state.begin();pos!&＃61;state.end()-1;&＃43;&＃43;pos)

cout<

cout<

cout<

for(pos&＃61;table.begin();pos!&＃61;table.end()-1;&＃43;&＃43;pos)

cout<

cout<

cout<

for(std::vector::iterator p&＃61;fun.begin();p!&＃61;fun.end();&＃43;&＃43;p)

cout<

cout<

cout<

for(pos&＃61;Z.begin();pos!&＃61;Z.end()-1;&＃43;&＃43;pos)

cout<

cout<

}

int main(int argc, char* argv[])

{

FA nfa,dfa;

nfa.input();

nfa.output();

nfa.Deterministic(dfa);

cout<

dfa.output();

return 0;

}

来源:http://topic.csdn.net/t/20041024/23/3486893.html

本回答由网友推荐

已赞过

已踩过<

你对这个回答的评价是&＃xff1f;

评论

收起