Assignment1.cpp

#include <bits/stdc++.h>
using namespace std;

static inline string trim(const string &s) {
    size_t l = s.find_first_not_of(" \t\r\n");
    if (l == string::npos) return "";
    size_t r = s.find_last_not_of(" \t\r\n");
    return s.substr(l, r - l + 1);
}

static bool isValidId(const string &s) {
    if (s.empty()) return false;
    for (char c : s) {
        if (!(isalnum(c) || c == '_')) return false;
    }
    return true;
}

struct Trans { int u, v; string sym; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    map<string, vector<string>> lists;
    string fsaType;
    set<string> seen;
    string line;

    const vector<string> expectedOrder = {
        "type", "states", "alphabet", "initial", "accepting", "transitions"
    };
    int nextExpected = 0;
    const set<string> reqSet(expectedOrder.begin(), expectedOrder.end());

    while (getline(cin, line)) {
        line = trim(line);
        if (line.empty()) continue;

        auto pos = line.find('=');
        if (pos == string::npos) {
            cout << "Input is malformed.\n";
            return 0;
        }

        string key = trim(line.substr(0, pos));
        string val = trim(line.substr(pos + 1));

        if (nextExpected >= (int)expectedOrder.size() || key != expectedOrder[nextExpected]) {
            cout << "Input is malformed.\n";
            return 0;
        }
        nextExpected++;

        if (seen.count(key)) {
            cout << "Input is malformed.\n";
            return 0;
        }
        seen.insert(key);

        if (key == "type") {
            if (val.size() < 2 || val.front() != '[' || val.back() != ']') {
                cout << "Input is malformed.\n";
                return 0;
            }
            string t = val.substr(1, val.size() - 2);
            if (t != "deterministic" && t != "non-deterministic") {
                cout << "Input is malformed.\n";
                return 0;
            }
            fsaType = t;

        } else {
            if (val.size() < 2 || val.front() != '[' || val.back() != ']') {
                cout << "Input is malformed.\n";
                return 0;
            }
            string body = val.substr(1, val.size() - 2);
            if (key == "transitions" && (body.empty() || body.back() == ',')) {
                cout << "Input is malformed.\n";
                return 0;
            }

            vector<string> elems;
            if (!body.empty()) {
                stringstream ss(body);
                string item;
                while (getline(ss, item, ',')) {
                    elems.push_back(trim(item));
                }
            }

            if (key == "states") {
                if (elems.empty()) {
                    cout << "Input is malformed.\n";
                    return 0;
                }
                for (auto &s : elems) {
                    if (!isValidId(s)) {
                        cout << "Input is malformed.\n";
                        return 0;
                    }
                }
                // remove duplicates
                vector<string> uniq;
                unordered_set<string> used;
                for (auto &s : elems) {
                    if (used.insert(s).second) uniq.push_back(s);
                }
                elems.swap(uniq);
            }

            lists[key] = elems;

            if (key == "alphabet") {
                if (elems.empty()) {
                    cout << "Input is malformed.\n";
                    return 0;
                }
                for (auto &s : elems) {
                    if (!isValidId(s) && s != "eps") {
                        cout << "Input is malformed.\n";
                        return 0;
                    }
                    if (s == "eps" && fsaType == "deterministic") {
                        cout << "FSA is non-deterministic.\n";
                        return 0;
                    }
                }

            } else if (key == "initial") {
                if (elems.empty()) {
                    cout << "Initial state is not defined.\n";
                    return 0;
                }
                if (elems.size() != 1 || !isValidId(elems[0])) {
                    cout << "Input is malformed.\n";
                    return 0;
                }
                auto &st = lists["states"];
                if (find(st.begin(), st.end(), elems[0]) == st.end()) {
                    cout << "A state '" << elems[0] << "' is not in the set of states.\n";
                    return 0;
                }

            } else if (key == "accepting") {
                if (elems.empty()) {
                    cout << "Set of accepting states is empty.\n";
                    return 0;
                }
                auto &st = lists["states"];
                for (auto &s : elems) {
                    if (!isValidId(s)) {
                        cout << "Input is malformed.\n";
                        return 0;
                    }
                    if (find(st.begin(), st.end(), s) == st.end()) {
                        cout << "A state '" << s << "' is not in the set of states.\n";
                        return 0;
                    }
                }
                auto &acc = lists["accepting"];
                sort(acc.begin(), acc.end());
                acc.erase(unique(acc.begin(), acc.end()), acc.end());

            } else if (key == "transitions") {
                auto &st   = lists["states"];
                auto &alph = lists["alphabet"];
                set<tuple<string,string,string>> seenT;

                for (auto &t : elems) {
                    vector<string> parts;
                    string tmp;
                    stringstream ss2(t);
                    while (getline(ss2, tmp, '>')) {
                        parts.push_back(trim(tmp));
                    }
                    if (parts.size() != 3 || parts[0].empty() || parts[1].empty() || parts[2].empty()) {
                        cout << "Input is malformed.\n";
                        return 0;
                    }
                    auto &su = parts[0], &sym = parts[1], &sv = parts[2];

                    // 1) symbol must be syntactically valid
                    if (sym != "eps" && !isValidId(sym)) {
                        cout << "Input is malformed.\n";
                        return 0;
                    }
                    // 2) symbol must be in alphabet (unless eps)
                    if (sym == "eps") {
                        if (find(alph.begin(), alph.end(), "eps") == alph.end()) {
                            cout << "A transition symbol 'eps' is not in the alphabet.\n";
                            return 0;
                        }
                        if (fsaType == "deterministic") {
                            cout << "FSA is non-deterministic.\n";
                            return 0;
                        }
                    } else {
                        if (find(alph.begin(), alph.end(), sym) == alph.end()) {
                            cout << "A transition symbol '" << sym << "' is not in the alphabet.\n";
                            return 0;
                        }
                    }

                    // 3) now states must exist
                    if (find(st.begin(), st.end(), su) == st.end() ||
                        find(st.begin(), st.end(), sv) == st.end()) {
                        cout << "A state '"
                             << (find(st.begin(), st.end(), su) == st.end() ? su : sv)
                             << "' is not in the set of states.\n";
                        return 0;
                    }

                    // 4) no duplicate transitions
                    if (!seenT.insert({su, sym, sv}).second) {
                        cout << "Input is malformed.\n";
                        return 0;
                    }
                }
            }
        }

        if (nextExpected == (int)expectedOrder.size()) break;
    }

    if (seen != reqSet) {
        cout << "Input is malformed.\n";
        return 0;
    }

    // ==== now convert to regex via Kleene's algorithm ====

    auto &states    = lists["states"];
    auto &alphabet  = lists["alphabet"];
    auto &initial   = lists["initial"];
    auto &accepting = lists["accepting"];
    auto &transStrs = lists["transitions"];

    sort(accepting.begin(), accepting.end());
    int n = states.size();
    unordered_map<string,int> idx;
    for (int i = 0; i < n; ++i) idx[states[i]] = i;
    int initIdx = idx[initial[0]];
    vector<int> accIdx;
    for (auto &s : accepting) accIdx.push_back(idx[s]);

    vector<Trans> transList;
    for (auto &t : transStrs) {
        vector<string> p;
        string tmp; stringstream ss(t);
        while (getline(ss, tmp, '>')) p.push_back(trim(tmp));
        transList.push_back({ idx[p[0]], idx[p[2]], p[1] });
    }

    if (fsaType == "deterministic") {
        map<pair<int,string>,int> cnt;
        for (auto &tr : transList) {
            if (tr.sym == "eps") continue;
            if (++cnt[{tr.u, tr.sym}] > 1) {
                cout << "FSA is non-deterministic.\n";
                return 0;
            }
        }
    }

    vector<vector<int>> adj(n);
    for (auto &tr : transList) adj[tr.u].push_back(tr.v);
    vector<char> vis(n);
    queue<int> q; vis[initIdx] = 1; q.push(initIdx);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; q.push(v); }
    }
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            cout << "Some states are disjoint.\n";
            return 0;
        }
    }

    vector<vector<string>> R(n, vector<string>(n));
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
        vector<string> parts;
        for (auto &tr : transList) {
            if (tr.u == i && tr.v == j && tr.sym != "eps")
                parts.push_back(tr.sym);
        }
        if (i == j) parts.push_back("eps");
        string expr = parts.empty() ? "{}" : parts[0];
        for (int p = 1; p < (int)parts.size(); ++p) expr += "|" + parts[p];
        R[i][j] = "(" + expr + ")";
    }

    for (int k = 0; k < n; ++k) {
        auto old = R;
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            string left = old[i][k] + old[k][k] + "*" + old[k][j];
            R[i][j] = "(" + left + "|" + old[i][j] + ")";
        }
    }

    vector<string> finals;
    for (int a : accIdx) finals.push_back(R[initIdx][a]);
    string result;
    if (finals.empty()) {
        result = "({})";
    } else if (finals.size() == 1) {
        result = finals[0];
    } else {
        result = finals[0];
        for (size_t i = 1; i < finals.size(); ++i)
            result += "|" + finals[i];
    }

    cout << result << '\n';
    return 0;
}