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

#define MAX_STATES 100
#define MAX_STRING_LENGTH 10

typedef struct {
    char name[MAX_STRING_LENGTH];
    int index;
} State;

typedef struct {
    State states[MAX_STATES];
    int count;
} StateList;

State state_list[MAX_STATES];
int state_count = 0;
int epsilon_map[MAX_STATES][MAX_STATES];
int epsilon_map_size[MAX_STATES];

int find_state_index(const char *state_name) {
    for (int i = 0; i < state_count; ++i) {
        if (strcmp(state_list[i].name, state_name) == 0) {
            return state_list[i].index;
        }
    }
    return -1;
}

void add_to_closure(StateList *closure, int state_index) {
    int visited[MAX_STATES] = {0};
    StateList queue;
    queue.count = 0;

    queue.states[queue.count++] = state_list[state_index];
    visited[state_index] = 1;

    while (queue.count > 0) {
        State current = queue.states[--queue.count];
        int current_index = current.index;

        for (int i = 0; i < epsilon_map_size[current_index]; ++i) {
            int next_index = epsilon_map[current_index][i];
            if (!visited[next_index]) {
                visited[next_index] = 1;
                queue.states[queue.count++] = state_list[next_index];
                closure->states[closure->count++] = state_list[next_index];
            }
        }
    }
}

void read_transitions(const char *filename) {
    FILE *file = fopen(filename, "r");
    if (!file) {
        perror("Error opening file");
        exit(EXIT_FAILURE);
    }

    char state1[MAX_STRING_LENGTH], state2[MAX_STRING_LENGTH], symbol[MAX_STRING_LENGTH];
    while (fscanf(file, "%s %s %s", state1, symbol, state2) == 3) {
        int index1 = find_state_index(state1);
        int index2 = find_state_index(state2);

        if (strcmp(symbol, "e") == 0) {
            epsilon_map[index1][epsilon_map_size[index1]++] = index2;
        }
    }
    fclose(file);
}

void compute_epsilon_closures() {
    for (int i = 0; i < state_count; ++i) {
        StateList closure;
        closure.count = 0;

        add_to_closure(&closure, i);
        printf("Epsilon closure of %s = {", state_list[i].name);
        for (int j = 0; j < closure.count; ++j) {
            printf("%s", closure.states[j].name);
            if (j < closure.count - 1) {
                printf(" ");
            }
        }
        printf("}\n");
    }
}

int main() {
    read_transitions("input.dat");

    printf("Enter the no. of states: %d\n", state_count);
    printf("Enter the states: ");
    for (int i = 0; i < state_count; ++i) {
        printf("%s ", state_list[i].name);
    }
    printf("\n");

    compute_epsilon_closures();

    return 0;
}