===== enfa_to_nfa.c =====

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

#define MAX_STATES 20
#define MAX_SYMBOLS 10

int n_states, n_symbols;
char symbols[MAX_SYMBOLS];

int epsilon[MAX_STATES][MAX_STATES];              // ε-transitions
int enfa[MAX_STATES][MAX_SYMBOLS][MAX_STATES];    // ε-NFA transitions
int nfa[MAX_STATES][MAX_SYMBOLS][MAX_STATES];     // NFA transitions

int epsilon_closure[MAX_STATES][MAX_STATES];
int closure_size[MAX_STATES];

// Add state to a set (if not already present)
void add_state(int *set, int *size, int state) {
    for (int i = 0; i < *size; i++) {
        if (set[i] == state)
            return;
    }
    set[(*size)++] = state;
}

// Compute ε-closure for a given state
void compute_epsilon_closure(int state) {
    int stack[MAX_STATES];
    int top = -1;
    int visited[MAX_STATES] = {0};

    closure_size[state] = 0;
    add_state(epsilon_closure[state], &closure_size[state], state);
    stack[++top] = state;
    visited[state] = 1;

    while (top >= 0) {
        int s = stack[top--];
        for (int i = 0; i < n_states; i++) {
            if (epsilon[s][i] && !visited[i]) {
                add_state(epsilon_closure[state], &closure_size[state], i);
                stack[++top] = i;
                visited[i] = 1;
            }
        }
    }
}

// Convert ε-NFA to NFA
void convert_to_nfa() {
    // First compute epsilon closure for all states
    for (int state = 0; state < n_states; state++) {
        compute_epsilon_closure(state);
    }

    // Now build NFA transitions
    for (int state = 0; state < n_states; state++) {
        for (int sym = 0; sym < n_symbols; sym++) {
            int reachable[MAX_STATES];
            int reachable_size = 0;

            // For each state in ε-closure of 'state'
            for (int i = 0; i < closure_size[state]; i++) {
                int s = epsilon_closure[state][i];

                // Follow transitions by symbol
                for (int t = 0; t < n_states; t++) {
                    if (enfa[s][sym][t]) {
                        // Add ε-closure of target
                        for (int j = 0; j < closure_size[t]; j++) {
                            add_state(reachable, &reachable_size, epsilon_closure[t][j]);
                        }
                    }
                }
            }

            // Store result into NFA table
            for (int i = 0; i < reachable_size; i++) {
                nfa[state][sym][reachable[i]] = 1;
            }
        }
    }
}

// Print NFA transitions
void print_nfa() {
    printf("\nNFA Transitions:\n");
    for (int i = 0; i < n_states; i++) {
        for (int sym = 0; sym < n_symbols; sym++) {
            printf("From state %d on '%c' -> ", i, symbols[sym]);
            for (int j = 0; j < n_states; j++) {
                if (nfa[i][sym][j]) {
                    printf("%d ", j);
                }
            }
            printf("\n");
        }
    }
}

int get_symbol_index(char c) {
    for (int i = 0; i < n_symbols; i++) {
        if (symbols[i] == c)
            return i;
    }
    return -1;
}

int main() {
    int n_transitions;

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

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

    printf("Enter the input symbols: ");
    for (int i = 0; i < n_symbols; i++) {
        scanf(" %c", &symbols[i]);
    }

    printf("Enter number of transitions: ");
    scanf("%d", &n_transitions);

    printf("Enter transitions in the form: from_state symbol to_state\n");
    printf("(Use 'e' for epsilon transitions)\n");

    for (int i = 0; i < n_transitions; i++) {
        int from, to;
        char ch;
        scanf("%d %c %d", &from, &ch, &to);
        if (ch == 'e') {
            epsilon[from][to] = 1;
        } else {
            int index = get_symbol_index(ch);
            if (index != -1) {
                enfa[from][index][to] = 1;
            } else {
                printf("Invalid symbol: %c\n", ch);
                i--;
            }
        }
    }

    convert_to_nfa();
    print_nfa();

    return 0;
}


===== run =====
nano enfa_to_nfa.c
gcc enfa_to_nfa.c -o enfa_to_nfa
./enfa_to_nfa