#include <stdio.h>

#define MAX_STATES 10
#define MAX_SYMBOLS 5

int nfa[MAX_STATES][MAX_SYMBOLS][MAX_STATES];
int nfa_state_count, symbol_count;

/* Check if a subset already exists */
int subset_exists(int dfa_states[], int count, int subset) {
    for (int i = 0; i < count; i++) {
        if (dfa_states[i] == subset)
            return 1;
    }
    return 0;
}

int main() {
    int dfa_states[100];
    int dfa_transitions[100][MAX_SYMBOLS];
    int dfa_count = 0;

    printf("Enter number of NFA states: ");
    scanf("%d", &nfa_state_count);

    printf("Enter number of input symbols: ");
    scanf("%d", &symbol_count);

    printf("Enter NFA transitions (1 if transition exists, else 0)\n");

    for (int i = 0; i < nfa_state_count; i++) {
        for (int j = 0; j < symbol_count; j++) {
            for (int k = 0; k < nfa_state_count; k++) {
                printf("From state %d on symbol %d to state %d: ", i, j, k);
                scanf("%d", &nfa[i][j][k]);
            }
        }
    }

    /* Start state of DFA = {0} */
    dfa_states[dfa_count++] = 1;  // bitmask: 0001

    for (int i = 0; i < dfa_count; i++) {
        for (int sym = 0; sym < symbol_count; sym++) {
            int new_subset = 0;

            for (int state = 0; state < nfa_state_count; state++) {
                if (dfa_states[i] & (1 << state)) {
                    for (int k = 0; k < nfa_state_count; k++) {
                        if (nfa[state][sym][k])
                            new_subset |= (1 << k);
                    }
                }
            }

            dfa_transitions[i][sym] = new_subset;

            if (!subset_exists(dfa_states, dfa_count, new_subset)) {
                dfa_states[dfa_count++] = new_subset;
            }
        }
    }

    printf("\nDFA Transition Table:\n");
    for (int i = 0; i < dfa_count; i++) {
        printf("DFA State %d (", i);
        for (int b = 0; b < nfa_state_count; b++) {
            if (dfa_states[i] & (1 << b))
                printf("%d ", b);
        }
        printf("): ");

        for (int j = 0; j < symbol_count; j++) {
            printf("%d ", dfa_transitions[i][j]);
        }
        printf("\n");
    }

    return 0;
}