24h購物| | PChome| 登入
2013-03-25 14:41:16| 人氣9,599| 回應2 | 上一篇 | 下一篇

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

推薦 0 收藏 0 轉貼0 訂閱站台 

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
*/

  

                                                        

                                                        
                                
                                                        

                                
                                    
                                    

                                
                                                    

                                                        
                                                        我要檢舉
                                                        
                                                        
#NFA#DFA#編譯器
                                                        

                                                        

                                                            
                                                        

                                                    

                                                        
                                                    

                                                        台長：
                                        Morris
                                                    

                                
                                    
                                    
                                    
                                                    

                                                        
您可能對以下文章有興趣

                                    
                                                        
                                                        
                                                        
                                                        
                                                    

                                    
                                                
                                                
                                                
                                                
                                
人氣(9,599) | 回應(2)| 推薦 (0)| 收藏 (0)| 轉寄

                                      全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: 其他題目 |
此分類下一篇:[編譯器][作業] Run DFA
此分類上一篇:[資料結構][作業] dijkstra、矩陣乘法、eigenvalue                                        

                                    

                                    
                                

                                
                                
                                
                                
                                
                                                                
                                
                                
                                

                                
                                

                                    

                                    

                                    

                                        
                                                

                                                    我要回應
                                                

                                                                                        

                                        
                
                            

                               
(悄悄話)

                               
2013-04-01 18:03:10

                            

                            
                            

                                

                                  
                                  
                                  Tony
                                  
                                  
                                  
                                  
                                


                                

                                    嘿 你好

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

                              
                            
2013-04-07 11:34:43

                                

                                    
版主回應

                                    
 windows using Ctrl+Z+ENTER, linux using Ctrl+D

                                    
2013-04-07 13:12:51

                                

                            
            
                                                        
                

                        
                        

                        
                        

                        
                        
                        


                        


                        

                          

                            

                            

                          


                          

                            

                            

                          

                          
                          

                            


                            

                              否
                              是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
                            

                          

                          
                          

                            

                            

                              
                            

                          


                          

                            
* 請輸入識別碼：


                            

                              








請輸入圖片中算式的結果(可能為0) 
















                              

                            

                          


                          

                            
(有*為必填)

                            

                          


                          

                            
                            
                            
                          

                        

                        
                                                                
                                    


                                                                        

                                                                        

                                

                                

                            

                            
                        

                        


                    

                    
                

                

                
                
            
                


                

            
        

        
    

    













      
      TOP
      

    






    













    

        

            

        

        

    

    

        

            

                

                

                    

                    
                    
                    詳全文