#include <stdio.h>
#include <string.h>

int nfa_states, symbols, nfa_final_count;
int nfa_final[10];
int nfa[10][10][10];   // nfa[state][symbol][list of states]
int nfa_count[10][10];

int dfa[20][10];       // DFA transition table
int dfa_states[20][10]; // DFA states as subsets
int dfa_state_count = 0;

int is_final(int subset[]) {
    for (int i = 0; i < nfa_final_count; i++)
        if (subset[nfa_final[i]] == 1)
            return 1;
    return 0;
}

int same_subset(int a[], int b[]) {
    for (int i = 0; i < nfa_states; i++)
        if (a[i] != b[i]) return 0;
    return 1;
}

int find_subset(int subset[]) {
    for (int i = 0; i < dfa_state_count; i++)
        if (same_subset(dfa_states[i], subset))
            return i;
    return -1;
}

int main() {
    int i, j, k;

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

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

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

    printf("Enter NFA final states:\n");
    for (i = 0; i < nfa_final_count; i++)
        scanf("%d", &nfa_final[i]);

    printf("Enter NFA transition table:\n");
    for (i = 0; i < nfa_states; i++) {
        for (j = 0; j < symbols; j++) {
            printf("From state %d on symbol %d, number of transitions: ", i, j);
            scanf("%d", &nfa_count[i][j]);
            for (k = 0; k < nfa_count[i][j]; k++)
                scanf("%d", &nfa[i][j][k]);
        }
    }

    // Initial DFA state = {0}
    memset(dfa_states, 0, sizeof(dfa_states));
    dfa_states[0][0] = 1;
    dfa_state_count = 1;

    // Subset construction
    for (i = 0; i < dfa_state_count; i++) {
        for (j = 0; j < symbols; j++) {
            int new_subset[10] = {0};

            for (k = 0; k < nfa_states; k++) {
                if (dfa_states[i][k]) {
                    for (int t = 0; t < nfa_count[k][j]; t++)
                        new_subset[nfa[k][j][t]] = 1;
                }
            }

            int index = find_subset(new_subset);
            if (index == -1) {
                dfa_states[dfa_state_count][0] = 0;
                for (k = 0; k < nfa_states; k++)
                    dfa_states[dfa_state_count][k] = new_subset[k];

                dfa[i][j] = dfa_state_count;
                dfa_state_count++;
            } else {
                dfa[i][j] = index;
            }
        }
    }

    // Output DFA
    printf("\nDFA Transition Table:\n");
    for (i = 0; i < dfa_state_count; i++) {
        printf("State %d: ", i);
        for (j = 0; j < symbols; j++)
            printf("%d ", dfa[i][j]);

        if (is_final(dfa_states[i]))
            printf("(Final)");

        printf("\n");
    }

    return 0;
}