2013-03-25 14:41:16Morris

[編譯器][作業][2014Update] NFA to DFA

Input範例檔1NFA.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範例檔1DFA.txt 

(a,b)

(1,2)(*3,4,5)(0)

(*3,4,5)(*5)(*4,5)

(*5)(0)(0)

(*4,5)(*5)(*5)

 

 

Input範例檔2NFA.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範例檔2DFA.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
*/

Tony 2013-04-07 11:34:43

嘿 你好
我想請問一下你輸入的中止條件是什麼啊?

版主回應
windows using Ctrl+Z+ENTER, linux using Ctrl+D 2013-04-07 13:12:51
(悄悄話) 2013-04-01 18:03:10