#include<set>
#include<stack>
#include<iostream>
using namespace std;
struct Triad {
char start;
char edge;
char end;
};
set<char> e_closure(set<char>, Triad[], int);
set<char> move(set<char>, char, Triad[], int);
void determined(Triad[], int, char*, int);
const int MAX_NODES = 20;set<char> Edge;
int main()
{
int N;
cout << " 请输入边数 :" << endl;
cin >> N;
Triad* G = new Triad[N];
cout << " 请输入正规文法 (* 代表 ε,#代表终态 ,约定输入时先输入以始态开始的三元组 ):" << endl;
for (int i = 0; i < N; i++) {
cin >> G[i].start >> G[i].edge >> G[i].end;
}
set<char> Edge;
for (int j = 0; j < N; j++) set<char> Edge;{
Edge.insert(G[j].edge);
}
int n = Edge.size();
char* input = new char[n];
set<char>::iterator it;
int j = 0;
for (it = Edge.begin(); it != Edge.end(); it++) {
input[j] = *it;
j++;
}
determined(G, N, input, n);
return 0;
}
set<char> e_closure(set<char> T, Triad G[], int N) //求闭包
{
set<char> U = T;
stack<char> S;
set<char>::iterator it;
for (it = U.begin(); it != U.end(); it++)
S.push(*it);
char t;
while (!S.empty())
{
t = S.top();
S.pop();
for (int i = 0; i < N; i++)
{
if (G[i].start == t && G[i].edge == '*')
{
U.insert(G[i].end);
S.push(G[i].end);
}
}
}
return U;
}
set<char> move(set<char> I, char a, Triad G[], int N) {
set<char> U;
set<char>::iterator it;
for (it = I.begin(); it != I.end(); it++)
for (int i = 0; i < N; i++) {
if (G[i].start == *it && G[i].edge == a)
U.insert(G[i].end);
}
return U;
}
void determined(Triad G[], int N, char* input, int n) {
cout << endl << " 确定后的 DFA:" << endl;
bool marked[MAX_NODES];
for (int i = 0; i < MAX_NODES; i++)
marked[i] = false;
set<char> C[MAX_NODES];
char s0 = G[0].start;
set<char> T0, T1;
T0.insert(s0);set<char> Edge;
T1 = e_closure(T0, G, N);
C[0] = T1;
int i = 0;
while (!C[i].empty() && marked[i] == false && i < MAX_NODES) {
marked[i] = true;
//输出图中求出来的集合
for (int j = 0; j < n; j++) {
if (input[j] != '*') {
set<char> U = e_closure(move(C[i], input[j], G, N), G, N);
if (!U.empty()) {
bool inC = false;
int k = 0;
while (!C[k].empty() && k < MAX_NODES) {
if (U == C[k]) {
inC = true;
break;
}
k++;
}
if (!inC) {
k = 0;
while (!C[k].empty() && k < MAX_NODES) {
k++;
}
C[k] = U;
}
cout << i << " → " << input[j] << " " << k << endl;
}
}
}
i++;
}
//下面求出确定化后的终态
cout << " 终态 :";
i = 0;
while (!C[i].empty()) {
bool is_final_state = false;
set<char>::iterator it;
for (it = C[i].begin(); it != C[i].end(); it++) {
if (*it == '#') {
is_final_state = true;
break;
}
}
if (is_final_state) cout << i << ",";
i++;
}
cout << endl;
}
近期评论