Input範例檔1：NFA.txt
(l,a,b,2) ----> l (英文字母)表示lambda, 2表示只有兩種input
(2,0)(3,0)(0,0)
(0,0)(4,5)(0,0)
(0,0)(0,0)(4,0)
(0,0)(5,0)(5,0)
(*,*)(*,*)(*,*)
Output範例檔1：DFA.txt
(a,b)
(1,2)(*3,4,5)(0)
(*3,4,5)(*5)(*4,5)
(*5)(0)(0)
(*4,5)(*5)(*5)
Input範例檔2：NFA.txt
(l,a,b,2) ----> l(英文字母)表示lambda, 2表示只有兩種input
(3,0)(4,0)(0,0)
(0,0)(3,1)(2,0)
(2,0)(0,0)(4,0)
(3,*)(4,*)(*,*)
Output範例檔2：DFA.txt
(a,b)
(1,2,3)(*1,2,3,4)(*2,3,4)
(*1,2,3,4)(*1,2,3,4)(*2,3,4)
(*2,3,4)(*1,2,3,4)(*2,3,4)
範例輸入的 NFA 如上。
輸入只會有一筆 NFA 描述，輸入以 EOF(end-of-file) 為結尾。
輸入第一行為字母集(set of input symbols Σ)，表示方法為 "(c1, c2, … cn, size)"。其中 ci 為 ASCII [32, 127] 的可視字符，其中特別以 'l' 字符表示 lambda。size(size = n-1)則為字母集的大小。
接下來會有數行表示每一個狀態的轉移，每一行上會有 n 個集合以 ‘(’ 和 ‘)’ 做為區隔，每個集合中會用逗號(‘,’)區隔每一個狀態編號。對於第 i 行的第 j 個集合 s(i, j)，表示 statei 可以藉由 cj 轉移到 s(i, j) 中任意狀態。
若第 i 行上的集合出現 ‘*’，表示 statei 是一個 accepting state Fi。特別以 state1 作為 start state。
(1 <= i <= m, 1 <= j <= n < size)
Output format:
輸出一組 DFA，格式如下。
輸出第一行為字母集 CDFA (按照字典順序輸出)。
接下來會有輸出 m 行，每行上表示每一個狀態的轉移，第一個集合為對應原本 NFA 的元素集合，接下來會有 CDFA.size() 個狀態，每個狀態皆以集合的方式呈現。對於第 i 行的第 j+1 個狀態 statej，表示 statei 可以藉由 CDFA[j] 轉移到 statej。
並且對應 NFA 的元素集合，採用最小字典順序的方式輸出(即排序後輸出)，若該狀態可以被 accepted，則使用一個 ‘*’ 放到狀態最前面輸出。
請參考範例輸入輸出。
#include <stdio.h>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;
string sigma[50]; // default 50 kinds
vector<int> g[50][50]; // g[i][j], i : state, j : alpha
bool expandState(set<int> &s, int m, bool acceptTable[]) { // add all state by lembda
int i, idx;
bool accept = false;
for(i = 0; i < m; i++)
if(sigma[i] == "l") // find lembda index in sigma
idx = i;
do {
bool flag = false;
for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
for(vector<int>::iterator jt = g[*it][idx].begin();
jt != g[*it][idx].end(); jt++) {
if(s.find(*jt) == s.end()) {
flag = true; // update flag;
s.insert(*jt);
}
}
accept |= acceptTable[*it];
}
if(flag == false) // expandState end
return accept;
} while(true);
return accept;
}
void printState(set<int> &s, bool accept) {
putchar('(');
if(accept)
putchar('*');
bool firstflag = true;
for(set<int>::iterator it = s.begin();
it != s.end(); it++) {
if(!firstflag) putchar(',');
firstflag = false;
printf("%d", *it);
}
putchar(')');
}
int main() {
string sigmaLine, line;
getline(cin, sigmaLine);
//<parse sigma>
int sigmaSize = 0;
for(int i = 1, j = sigmaLine.length(); i < j; i++) {
char buf[50], *p = buf;
while(sigmaLine[i] != ',' && sigmaLine[i] != ')')
*p = sigmaLine[i], p++, i++;
if(sigmaLine[i] == ')')
break; // don't process last number
*p = '\0';
sigma[sigmaSize++] = buf;
}
//</parse sigma>
//debug
//for(int i = 0; i < sigmaSize; i++)
// cout << sigma[i] << endl;
//debug
int statei = 1;
bool acceptTable[50] = {};
//<parse state link>
while(getline(cin, line)) {
int sigmai = -1, num = 0;
bool accept = false;
for(int i = 0, j = line.length(); i < j; i++) {
if(line[i] == '(')
sigmai++;
else if(line[i] == '*')
accept = true; // state (i) acceptable
else {
if(line[i] == ',' || line[i] == ')') {
if(num) {
//debug
//printf("%d %s -> %d\n", statei, sigma[sigmai].c_str(), num);
//debug
g[statei][sigmai].push_back(num);
}
num = 0;
} else
num = num*10 + line[i]-'0';
}
}
acceptTable[statei] = accept;
statei++;
}
int stateSize = statei;
//</parse state link> windows using Ctrl+Z, linux using Ctrl+D (EOF)
set<int> newState[50]; // default newState max 50
bool newacceptTable[50] = {};
vector<int> newg[50][50]; // new table to transtate
int newStateSize = 1;
newState[0].insert(1); // start state = 1
newacceptTable[0] = expandState(newState[0], sigmaSize, acceptTable);
putchar('(');
for(int i = 0, j = 1; i < sigmaSize; i++) {
if(sigma[i] == "l")
continue;
if(!j) putchar(',');
j = 0;
printf("%s", sigma[i].c_str());
}
putchar(')');
puts("");
for(int i = 0; i < newStateSize; i++) {
printState(newState[i], newacceptTable[i]);
for(int j = 0; j < sigmaSize; j++) {
if(sigma[j] == "l")
continue;
set<int> trans;
for(set<int>::iterator it = newState[i].begin();
it != newState[i].end(); it++) {
for(vector<int>::iterator jt = g[*it][j].begin();
jt != g[*it][j].end(); jt++)
trans.insert(*jt);
}
bool accept = expandState(trans, sigmaSize, acceptTable);
if(trans.size() == 0) {
printf("(0)"); // NULL
continue;
}
int node = -1; // find new state exists in newState?
for(int p = 0; p < newStateSize; p++) {
if(newState[p].size() != trans.size())
continue;
bool same = true;
for(set<int>::iterator it = newState[p].begin(), jt = trans.begin();
it != newState[p].end(); it++, jt++) {
if(*it != *jt) {
same = false;
break;
}
}
if(same == true) {
node = p;
continue;
}
}
if(node < 0) {
newState[newStateSize] = trans; // copy set
newacceptTable[newStateSize] = accept;
node = newStateSize++;
}
printState(newState[node], newacceptTable[node]);
}
puts("");
}
return 0;
}
/*
(l,a,b,2)
(2,0)(3,0)(0,0)
(0,0)(4,5)(0,0)
(0,0)(0,0)(4,0)
(0,0)(5,0)(5,0)
(*,*)(*,*)(*,*)
(l,a,b,2)
(3,0)(4,0)(0,0)
(0,0)(3,1)(2,0)
(2,0)(0,0)(4,0)
(3,*)(4,*)(*,*)
*/
[2014/04/08] 版本
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
class State {
public:
State(int ac=0) {
accepted = ac;
}
bool accepted;
int nameLabel;
map<char, vector<State*> > trans;
};
class DFA {
public:
State* Q0;
vector<State*> Q, F;
};
class NFA {
public:
static char lambda;
State* Q0;
vector<State*> Q, F;
vector< vector<State*> > make_deterministic(DFA &M, vector<char> alpha);
private:
vector<State*> getSetOf(vector<State*> set_of_states, char c);
vector<State*> getClose(vector<State*> set_of_states);
};
char NFA::lambda = 0;
/*
* @return delta(S, c)
*/
vector<State*> NFA::getSetOf(vector<State*> set_of_states, char c) {
set<State*> h;
vector<State*> ret;
queue<State*> q;
State* index;
for(int i = 0; i < set_of_states.size(); i++) {
index = set_of_states[i];
q.push(index);
}
while(!q.empty()) {
index = q.front(), q.pop();
vector<State*> state_trans = index->trans[c];
for(int i = 0; i < state_trans.size(); i++) {
if(h.find(state_trans[i]) == h.end()) {
h.insert(state_trans[i]);
ret.push_back(state_trans[i]);
}
}
}
return ret;
}
/*
* Add to S all states reachable from it
* using only lembda transitions of N
* @return S union delta(S, lambda)
*/
vector<State*> NFA::getClose(vector<State*> set_of_states) {
set<State*> h;
vector<State*> ret;
queue<State*> q;
State* index;
for(int i = 0; i < set_of_states.size(); i++) {
index = set_of_states[i];
q.push(index), h.insert(index);
}
while(!q.empty()) {
index = q.front(), q.pop();
ret.push_back(index);
vector<State*> state_trans = index->trans[NFA::lambda];
for(int i = 0; i < state_trans.size(); i++) {
if(h.find(state_trans[i]) == h.end()) {
h.insert(state_trans[i]);
q.push(state_trans[i]);
}
}
}
sort(ret.begin(), ret.end());
return ret;
}
/*
* @return NFA to DFA
*/
vector< vector<State*> > NFA::make_deterministic(DFA &M, vector<char> alpha) {
vector< vector<State*> > T;
vector<State*> stateSet;
stateSet.push_back(Q0);
vector<State*> init_state = getClose(stateSet);
T.push_back(init_state);
M.Q.push_back(new State());
for(int i = 0; i < T.size(); i++) {
State* state = M.Q[i];
for(int j = 0; j < T[i].size(); j++)
if(T[i][j]->accepted)
state->accepted = 1;
state->nameLabel = i;
if(state->accepted) M.F.push_back(state);
for(int j = 0; j < alpha.size(); j++) {
if(alpha[j] == NFA::lambda)
continue;
vector<State*> next_state = getSetOf(T[i], alpha[j]);
next_state = getClose(next_state);
int existIdx = -1;
for(int k = 0; k < T.size(); k++) {
if(T[k] == next_state) {
existIdx = k;
break;
}
}
if(existIdx < 0) {
T.push_back(next_state);
M.Q.push_back(new State());
existIdx = T.size()-1;
}
M.Q[i]->trans[alpha[j]].push_back(M.Q[existIdx]);
}
}
M.Q0 = M.Q[0];
return T;
}
vector<char> parsingAlphabetSet(char s[]) {
#define isValidAlpha(x) ((x) != ',' && (x) != '(' && (x) != ')' && !((x) >= '0' && (x) <= '9'))
for(int i = 0; s[i]; i++) {
if(!isValidAlpha(s[i]))
s[i] = ' ';
}
vector<char> ret;
stringstream sin(s);
string token;
while(sin >> token) {
if(token == "l")
ret.push_back(NFA::lambda);
else
ret.push_back(token[0]);
}
return ret;
}
int parsingStateTrans(char s[], int column, vector< vector< vector<int> > > &table) {
for(int i = 0; s[i]; i++) {
if(s[i] == '(' || s[i] == ')')
s[i] = ' ';
}
stringstream sin(s);
int ac = 0;
vector< vector<int> > R;
for(int i = 0; i < column; i++) {
string token, state_index;
sin >> token;
for(int j = 0; j < token.length(); j++)
if(token[j] == ',')
token[j] = ' ';
stringstream sin2(token);
vector<int> S;
while(sin2 >> state_index) {
if(state_index == "*") {
ac = 1;
} else {
int numeric_idx;
numeric_idx = atoi(state_index.c_str());
if(numeric_idx > 0) { // ignore zero.
S.push_back(numeric_idx-1);
}
}
}
R.push_back(S);
}
table.push_back(R);
return ac;
}
bool cmp(const State* a, const State* b) {
return a->nameLabel < b->nameLabel;
}
void printfState(int accepted, vector<State*> mask) {
printf("(");
if(accepted)
printf("*");
sort(mask.begin(), mask.end(), cmp);
for(int j = 0; j < mask.size(); j++) {
printf("%d", mask[j]->nameLabel + 1);
printf("%c", j == mask.size()-1 ? ')' : ',');
}
if(mask.size() == 0)
printf("0)");
}
int main() {
//freopen("NFA.txt", "r+t", stdin);
//freopen("DFA.txt", "w+t", stdout);
NFA nfa;
DFA dfa;
char s[1024];
int state_count = 0;
vector< vector< vector<int> > > table;
vector<int> hasStar; // integer state label
vector<char> alpha;
// read alpha set
gets(s);
alpha = parsingAlphabetSet(s);
// read table
while(gets(s)) {
int ac = parsingStateTrans(s, alpha.size(), table);
hasStar.push_back(ac);
state_count++;
}
// build basic NFA states
for(int i = 0; i < state_count; i++) {
nfa.Q.push_back(new State(hasStar[i]));
nfa.Q[i]->nameLabel = i;
if(hasStar[i]) nfa.F.push_back(nfa.Q[i]);
}
// init start state
nfa.Q0 = nfa.Q[0];
// build translate table.
int i = 0;
for(vector< vector< vector<int> > >::iterator it = table.begin();
it != table.end(); it++, i++) {
int j = 0;
for(vector< vector<int> >::iterator jt = it->begin();
jt != it->end(); jt++, j++) {
for(vector<int>::iterator kt = jt->begin();
kt != jt->end(); kt++) {
nfa.Q[i]->trans[alpha[j]].push_back(nfa.Q[*kt]);
}
}
}
// start process NFA to DFA
vector< vector<State*> > mask = nfa.make_deterministic(dfa, alpha);
// output result
for(map<char, vector<State*> >::iterator it = dfa.Q[0]->trans.begin();
it != dfa.Q[0]->trans.end(); it++) {
printf("%c%c", it == dfa.Q[0]->trans.begin() ? '(' : ',', it->first);
}
puts(")");
for(int i = 0; i < dfa.Q.size(); i++) {
if(mask[dfa.Q[i]->nameLabel].size() == 0)
continue;
printfState(dfa.Q[i]->accepted, mask[dfa.Q[i]->nameLabel]);
for(map<char, vector<State*> >::iterator it = dfa.Q[i]->trans.begin();
it != dfa.Q[i]->trans.end(); it++) {
State *ptr = it->second[0];
printfState(ptr->accepted, mask[ptr->nameLabel]);
}
puts("");
}
return 0;
}
/*
void print() {
printf("start[%p]\n", Q0);
for(int i = 0; i < Q.size(); i++) {
printf("Q[%p][%d] : ", Q[i], Q[i]->nameLabel);
for(map<char, vector<State*> >::iterator it = Q[i]->trans.begin();
it != Q[i]->trans.end(); it++) {
printf("[%c,", it->first == 0 ? '~' : it->first);
for(vector<State*>::iterator jt = it->second.begin();
jt != it->second.end(); jt++) {
printf(" %d", (*jt)->nameLabel);
}
printf("]");
}
puts("");
}
}*/
/*
(l,a,b,2)
(2,0)(3,0)(0,0)
(0,0)(4,5)(0,0)
(0,0)(0,0)(4,0)
(0,0)(5,0)(5,0)
(*,*)(*,*)(*,*)
(l,a,b,2)
(3,0)(4,0)(0,0)
(0,0)(3,1)(2,0)
(2,0)(0,0)(4,0)
(3,*)(4,*)(*,*)
(l,a,b,2)
(2,4,6)(0)(0)
(0)(3)(0)
(6)(0)(0)
(0)(0)(5)
(6)(0)(0)
(1)(7)(0)
(*)(*)(*)
(l,a,b,2)
(0)(1,2)(1)
(0)(0)(3)
(*)(0,0)(0,0)
(l,a,b,2)
(*,0)(2)(0)
(0)(0)(3)
(0)(1,4,5)(0)
(0)(5)(0)
(0)(1)(0)
*/
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
class State {
public:
State(int ac=0) {
accepted = ac;
}
bool accepted;
int nameLabel;
map<char, vector<State*> > trans;
};
class DFA {
public:
State* Q0;
vector<State*> Q, F;
int runDFA(const char s[]);
};
int DFA::runDFA(const char s[]) {
State *p;
p = Q0;
for(int i = 0; s[i]; i++) {
if(p->trans.find(s[i]) == p->trans.end())
return 0;
p = p->trans[s[i]][0];
}
return p->accepted;
}
vector<char> parsingAlphabetSet(char s[]) {
#define isValidAlpha(x) ((x) != ',' && (x) != '(' && (x) != ')' && !((x) >= '0' && (x) <= '9'))
for(int i = 0; s[i]; i++) {
if(!isValidAlpha(s[i]))
s[i] = ' ';
}
vector<char> ret;
stringstream sin(s);
string token;
while(sin >> token)
ret.push_back(token[0]);
return ret;
}
int parsingStateTrans(char s[], int column, vector< vector< string > > &table) {
for(int i = 0; s[i]; i++) {
if(s[i] == '(' || s[i] == ')')
s[i] = ' ';
}
stringstream sin(s);
vector< string > R;
for(int i = 0; i < column + 1; i++) {
string token;
sin >> token;
R.push_back(token);
}
table.push_back(R);
int ac = 0;
for(int i = 0; i < R[0].length(); i++)
if(R[0][i] == '*')
ac = 1;
return ac;
}
int main() {
freopen("DFAjudge.txt", "r+t", stdin);
freopen("DFAresult.txt", "w+t", stdout);
DFA dfa;
char s[1024];
gets(s);
vector<char> alpha = parsingAlphabetSet(s);
int state_count = 0;
vector< vector< string > > table;
vector<int> hasStar;
while(gets(s)) {
if(s[0] != '(') break;
int ac = parsingStateTrans(s, alpha.size(), table);
hasStar.push_back(ac);
state_count++;
}
for(int i = 0; i < state_count; i++) {
dfa.Q.push_back(new State(hasStar[i]));
dfa.Q[i]->nameLabel = i;
if(hasStar[i]) dfa.F.push_back(dfa.Q[i]);
}
dfa.Q0 = dfa.Q[0];
int i = 0;
for(vector< vector< string > >::iterator it = table.begin();
it != table.end(); it++, i++) {
string start = table[i][0];
for(int j = 1; j <= alpha.size(); j++) {
string end = table[i][j];
for(int k = 0; k < table.size(); k++) {
if(table[k][0] == end)
dfa.Q[i]->trans[alpha[j-1]].push_back(dfa.Q[k]);
}
}
}
puts(dfa.runDFA(s) ? "valid" : "error");
return 0;
}
/*
Sample Input:
(a,b)
(1,2)(*3,4,5)(0)
(*3,4,5)(*5)(*4,5)
(*5)(0)(0)
(*4,5)(*5)(*5)
abbbb
(a,b)
(1,2)(*3,4,5)(0)
(*3,4,5)(*5)(*4,5)
(*5)(0)(0)
(*4,5)(*5)(*5)
ab
(a,b)
(1,2,3)(*1,2,3,4)(*2,3,4)
(*1,2,3,4)(*1,2,3,4)(*2,3,4)
(*2,3,4)(*1,2,3,4)(*2,3,4)
a
------------------
Sample Output:
error
valid
valid
*/
文章定位：
