pract5.cpp

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

// Define structure for a state
typedef struct State {
    int state_num;
    struct State* on_a; // Transition for 'a'
    struct State* on_b; // Transition for 'b'
    struct State* epsilon1; // Epsilon transition 1
    struct State* epsilon2; // Epsilon transition 2
} State;

// Define structure for an NFA
typedef struct NFA {
    State* start_state;
    State* accept_state;
} NFA;

int state_counter = 0; // Global state counter

// Function to create a new state
State* createState() {
    State* state = (State*)malloc(sizeof(State));
    state->state_num = state_counter++;
    state->on_a = NULL;
    state->on_b = NULL;
    state->epsilon1 = NULL;
    state->epsilon2 = NULL;
    return state;
}

// Function to create an NFA for a single character
NFA* createCharNFA(char c) {
    NFA* nfa = (NFA*)malloc(sizeof(NFA));
    State* start = createState();
    State* accept = createState();
    
    if (c == 'a') {
        start->on_a = accept; // Transition on 'a'
    } else if (c == 'b') {
        start->on_b = accept; // Transition on 'b'
    }
    
    nfa->start_state = start;
    nfa->accept_state = accept;
    return nfa;
}

// Function to combine two NFAs using concatenation
NFA* concatenateNFA(NFA* nfa1, NFA* nfa2) {
    NFA* nfa = (NFA*)malloc(sizeof(NFA));
    nfa1->accept_state->epsilon1 = nfa2->start_state; // Epsilon transition from nfa1's accept to nfa2's start
    nfa->start_state = nfa1->start_state;
    nfa->accept_state = nfa2->accept_state;
    return nfa;
}

// Function to combine two NFAs using union (a | b)
NFA* unionNFA(NFA* nfa1, NFA* nfa2) {
    NFA* nfa = (NFA*)malloc(sizeof(NFA));
    State* start = createState(); // New start state
    State* accept = createState(); // New accept state
    
    // Epsilon transitions from new start state to the start states of nfa1 and nfa2
    start->epsilon1 = nfa1->start_state;
    start->epsilon2 = nfa2->start_state;
    
    // Epsilon transitions from the accept states of nfa1 and nfa2 to the new accept state
    nfa1->accept_state->epsilon1 = accept;
    nfa2->accept_state->epsilon1 = accept;
    
    nfa->start_state = start;
    nfa->accept_state = accept;
    return nfa;
}

// Function to apply Kleene star to an NFA (a*)
NFA* kleeneStarNFA(NFA* nfa) {
    NFA* new_nfa = (NFA*)malloc(sizeof(NFA));
    State* start = createState(); // New start state
    State* accept = createState(); // New accept state
    
    // Epsilon transitions
    start->epsilon1 = nfa->start_state; // From new start to old start
    start->epsilon2 = accept;           // From new start to new accept (for zero repetitions)
    nfa->accept_state->epsilon1 = nfa->start_state; // From old accept to old start (loop)
    nfa->accept_state->epsilon2 = accept;           // From old accept to new accept
    
    new_nfa->start_state = start;
    new_nfa->accept_state = accept;
    return new_nfa;
}

// Function to print the NFA transitions
void printNFA(State* state, int visited[]) {
    if (visited[state->state_num]) return;
    visited[state->state_num] = 1;
    
    if (state->on_a) {
        printf("State %d --a--> State %d\n", state->state_num, state->on_a->state_num);
        printNFA(state->on_a, visited);
    }
    
    if (state->on_b) {
        printf("State %d --b--> State %d\n", state->state_num, state->on_b->state_num);
        printNFA(state->on_b, visited);
    }
    
    if (state->epsilon1) {
        printf("State %d --ε--> State %d\n", state->state_num, state->epsilon1->state_num);
        printNFA(state->epsilon1, visited);
    }
    
    if (state->epsilon2) {
        printf("State %d --ε--> State %d\n", state->state_num, state->epsilon2->state_num);
        printNFA(state->epsilon2, visited);
    }
}

// Function to construct NFA from regular expression
NFA* constructNFA(char* regex) {
    NFA* stack[100]; // Stack for NFAs
    int top = -1;
    
    for (int i = 0; i < strlen(regex); i++) {
        if (regex[i] == 'a' || regex[i] == 'b') {
            // Create NFA for character
            stack[++top] = createCharNFA(regex[i]);
        } else if (regex[i] == '.') {
            // Concatenation
            NFA* nfa2 = stack[top--];
            NFA* nfa1 = stack[top--];
            stack[++top] = concatenateNFA(nfa1, nfa2);
        } else if (regex[i] == '|') {
            // Union
            NFA* nfa2 = stack[top--];
            NFA* nfa1 = stack[top--];
            stack[++top] = unionNFA(nfa1, nfa2);
        } else if (regex[i] == '*') {
            // Kleene star
            NFA* nfa = stack[top--];
            stack[++top] = kleeneStarNFA(nfa);
        }
    }
    
    return stack[top]; // Final NFA
}

int main() {
    char regex[100];
    
    // Input regular expression in postfix notation
    printf("Enter the regular expression in postfix notation (e.g., ab.a.): ");
    scanf("%s", regex);
    
    // Construct the NFA
    NFA* nfa = constructNFA(regex);
    
    // Print the NFA
    int visited[100] = {0};
    printf("NFA transitions:\n");
    printNFA(nfa->start_state, visited);
    
    return 0;
}