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,*)(*,*)
*/