Unnamed

/*
* Program to convert a regular expression to NFA *
* Author:
*	 Venkateswaran S<wenkat.s@gmail.com>
*
*/

#include "re2nfa.h"
/* Function Declaration */

int createAutomata (struct automata **);
// Just initializes default values of the struct Automata

int createNewState (struct state **);
// The same as create Automata but this initializes struct state

struct automata * find_Nfa();
// Recursive Fn that finds the equivalent automata to the given regular expression

struct automata * nfa_To_Dfa(struct automata *);
// Convert the obtained nfa into dfa.

struct automata * applyStar (struct automata *);
// Note: The tranistions that are not named are epsilon transitions.
//                          ________
//                         |        |
// converts (R)* to   3--> 1 --R--> 2 --> 4
//                    |___________________|

struct automata * applyOr (struct automata *,struct automata *);
//
//                     ____1 --R--> 2 ____
//                    |                   |
// converts R | S to  5                   6
//                    |____3 --S--> 4_____|

struct automata * applyAnd (struct automata *, struct automata *);
//
// converts R . S to  1--R-->2 --> 3--S-->4

void add_to_inputsymbols(char);
// This function is used to build the set of all input symbols.

void find_Epsilon_Closure(struct state *);
// This function finds the epsilon closure of a nfa state.

char * del_cap(struct state *,char);
// This is to compute del_cap(A,a) where A is a nfa state and x is an input character.

struct state * get_state(char *, struct state *);
// It returns the ptr to the state that has the respective state number.

/* Functions are defined below this. */

struct automata * find_Nfa () {

	struct automata * nfa;
	if(!createAutomata(&nfa)) {
		printf("\nUnable to create automata called nfa");
		exit(1);
	}
	while(current_char != '$' || current_char != '\n' || current_char != '\r') {
		if(flag == 0)
			scanf("%c",&current_char);
		if( current_char >= 'a' && current_char <= 'z') {

			add_to_inputsymbols(current_char);
			if(last_char == ALPHABET) {
				struct state *tmp1;
				if(createNewState(&tmp1)) {
					tmp1->state_number = (char *) malloc(MAX);
					itoa(count++,tmp1->state_number,10);
					nfa->final->transition1 = tmp1;
					nfa->final->value_on_edge1 = current_char;

					important_states[important_states_count] = atoi(nfa->final->state_number);;
					important_states_count++;
					printf("\n State : %s -- '%c' --> %s",nfa->final->state_number,nfa->final->value_on_edge1,nfa->final->transition1->state_number);
					nfa->final = tmp1;
				}
			}
			else if (last_char == NON_ALPHABET) {
				struct state *tmp1,*tmp2;
				if(createNewState(&tmp1) && createNewState(&tmp2)) {
					tmp1->state_number = (char *) malloc(MAX);
					itoa(count++,tmp1->state_number,10);
					tmp2->state_number = (char *) malloc(16);
					itoa(count++,tmp2->state_number,10);
					tmp1->transition1 = tmp2;
					tmp1->value_on_edge1=current_char;

					important_states[important_states_count] = atoi(tmp1->state_number);
					important_states_count++;
					printf("\n State : %s -- '%c' --> %s",tmp1->state_number,tmp1->value_on_edge1,tmp1->transition1->state_number);
					nfa->start = tmp1;
					nfa->final = tmp2;
				}
				last_char = ALPHABET;
			}
			else {
				printf("Unable to create 2 new states");
				exit(1);
			}
		}
		else if ( current_char == '(') {
			last_char = NON_ALPHABET;
			nfa = find_Nfa();
		}
		else if ( current_char == ')' ) {
			last_char = NON_ALPHABET;
			return (nfa);
		}
		else if (current_char == '*') {
			last_char = NON_ALPHABET;
			nfa = applyStar(nfa);
		}
		else if (current_char == '|') {
			last_char = NON_ALPHABET;
			struct automata * temp2;
			if(!createAutomata(&temp2)) {
				printf("\nUnable to create automata called temp2");
				exit(1);
			}
			temp2 = find_Nfa();
			nfa = applyOr(nfa,temp2);
		}
		else if (current_char == '.') {
			last_char = NON_ALPHABET;
			struct automata * temp3 = (struct automata *)NULL;
			if(!createAutomata(&temp3)) {
				printf("\nUnable to create automata called nfa");
				exit(1);
			}
			temp3 = find_Nfa();
			nfa = applyAnd(nfa,temp3);
		}
		else {
			if(current_char =='\n' || current_char == '$' || current_char == '\r') {
				flag = 1;
				return (nfa);
			}
			else {
				printf("\nInvalid Input Character(s): %c\n",current_char);
				exit(1);
			}
		}
	}
}

struct automata * nfa_To_Dfa (struct automata * nfa) {

	 struct automata * dfa;
	 if(!createAutomata(&dfa)) {
		printf("\nUnable to create automata called dfa");
		exit(1);
	 }

	 if(createNewState(&dfa->start)) {

        struct df_state *temp_dfa;
        int loop_count=0;
		char *temp;
		strcpy(dfa->start->state_number,find_Epsilon_Closure(nfa->start));
		temp_dfa = dfa->start;
        while (!pop(&temp_dfa)) {
            temp_dfa->mark = 1;
            for(loop_count = 0;set_of_input_symbols[loop_count] != '\0';loop_count++) {
                strcpy(temp_dfa->state_number,del_cap(dfa->start,set_of_input_symbols[loop_count]));
                if(!push(temp_dfa)) {
                    printf("Problem in pushing the dfa state into the stack");
                    exit (1);
                }
            }
        }
        printf("\n The starting state of dfa is :[%s]",dfa->start->state_number);
	 }
	 else {

		 printf("\n Unable to create the start state for dfa");
		 exit(1);
	 }
	 return dfa;
}

int main () {

	int for_loop_count=0;
	char *temp;
	set_of_input_symbols = (char *) malloc(MAX);
	strcpy(set_of_input_symbols,"");
	temp = (char *) malloc(MAX);
    strcpy(temp,"");
	important_states_str = (char *) malloc(MAX);
	strcpy(important_states_str,"`");

	nfa = find_Nfa();

	printf("\n\n State : %s is the Starting state",nfa->start->state_number);
	printf("\n State : %s is the Final state",nfa->final->state_number);
	printf("\n Set of input variable(s) are :%s",set_of_input_symbols);

	for(for_loop_count = 0;for_loop_count < important_states_count; for_loop_count++) {
        itoa(important_states[for_loop_count],temp,10);
		strcat(important_states_str,temp);
		strcat(important_states_str,"`");
	}

    printf("\n The important state(s) in the above nfa are : %s",important_states_str);

	dfa = nfa_To_Dfa (nfa);
    return 0;
}