rendered paste body#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ALPHABET 1
#define NON_ALPHABET 0
#define INSIDE 1
#define OUTSIDE 0
#define MAX 48
/*Global variable declarations */
int count = 1,flag = 0,important_states[MAX],important_states_count=0,last_char = NON_ALPHABET;
char current_char='0',epsilon_states[MAX];
char * important_states_str, * set_of_input_symbols;
struct automata * nfa, * dfa;
/* Functions are defined below this. */
struct state {
char *state_number;
struct state *transition1;
char value_on_edge1;
struct state *transition2;
char value_on_edge2;
};
struct automata {
struct state *start;
struct state *final;
};
int createNewState (struct state **ptr) {
struct state *tmp_st;
tmp_st =(struct state *) malloc(sizeof(struct state));
if(tmp_st != (struct state *)NULL) {
tmp_st->state_number = (char *)NULL;
tmp_st->transition1 = (struct state *)NULL;
tmp_st->value_on_edge1='$';
tmp_st->transition2 = (struct state *)NULL;
tmp_st->value_on_edge2='$';
*ptr = tmp_st;
return TRUE;
}
else {
printf("Unable to create a state");
return FALSE;
}
}
int createAutomata (struct automata **ptr) {
struct automata *tmp_automata;
tmp_automata = (struct automata *)malloc(sizeof(struct automata));
if(tmp_automata != (struct automata *)NULL) {
tmp_automata->start = (struct state *)NULL;
tmp_automata->final = (struct state *)NULL;
*ptr = tmp_automata;
return TRUE;
}
else {
printf("Unable to allocate memory for automata");
return FALSE;
}
}
struct automata * applyAnd (struct automata * nfa, struct automata * nfa1) {
if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa1->start->state_number);
nfa->final->transition1 = nfa1->start;
nfa->final->value_on_edge1 = '#';
nfa->final = nfa1->final;
return (nfa);
}
else {
printf("\nUnable to Apply the 'and' operation on the nfa");
exit(1);
}
}
struct automata * applyOr (struct automata * nfa, struct automata * nfa1) {
if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {
struct state *tmp1 = (struct state *)NULL;
struct state *tmp2 = (struct state *)NULL;
if(createNewState(&tmp1) && createNewState(&tmp2)) {
tmp1->state_number = (char *) malloc(MAX);
itoa(count++,tmp1->state_number,10);
tmp2->state_number = (char *) malloc(MAX);
itoa(count++,tmp2->state_number,10);
tmp1->transition1 = nfa->start;
tmp1->value_on_edge1 = '#';
tmp1->transition2 = nfa1->start;
tmp1->value_on_edge2 = '#';
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition1->state_number);
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition2->state_number);
nfa->final->transition1 = tmp2;
nfa->final->value_on_edge1 = '#';
nfa1->final->transition1 = tmp2;
nfa1->final->value_on_edge1 = '#';
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
printf("\n State : %s -- epsilon --> %s",nfa1->final->state_number,nfa1->final->transition1->state_number);
nfa->start = tmp1;
nfa->final = tmp2;
nfa->final->transition1 = (struct state *)NULL;
nfa->final->transition2 = (struct state *)NULL;
return (nfa);
}
else {
printf("\nProbs in creating new states");
exit(1);
}
}
else {
printf("\nUnable to Apply the Or operation on the nfa");
exit(1);
}
}
struct automata * applyStar (struct automata * nfa) {
struct state *tmp1 = (struct state *)NULL;
struct state *tmp2 = (struct state *)NULL;
if(createNewState(&tmp1) && createNewState(&tmp2)) {
tmp1->state_number = (char *) malloc(MAX);
itoa(count++,tmp1->state_number,10);
tmp1->transition1 = nfa->start;
tmp1->value_on_edge1 = '#';
tmp1->transition2 = tmp2;
tmp1->value_on_edge2 = '#';
tmp2->state_number = (char *) malloc(MAX);
itoa(count++,tmp2->state_number,10);
nfa->final->transition1 = nfa->start;
nfa->final->value_on_edge1 = '#';
nfa->final->transition2 = tmp2;
nfa->final->value_on_edge2 = '#';
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition2->state_number);
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,nfa->start->state_number);
printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp2->state_number);
nfa->start = tmp1;
nfa->final = tmp2;
nfa->final->transition1 = (struct state *)NULL;
nfa->final->transition2 = (struct state *)NULL;
return (nfa);
}
else {
printf("\nUnable to Apply the star operation on the nfa");
exit(1);
}
}
void add_to_inputsymbols (char input) {
char *temp;
temp = (char *)malloc(8);
*temp = input;
*(temp+1) = '\0';
if(strchr(set_of_input_symbols,input) == (char *)NULL) {
strcat(set_of_input_symbols,temp);
}
}
char * find_Epsilon_Closure (struct state * nfa_start) {
epsilon_states[count_of_states] = nfa_start->state_number;
if (nfa_start->value_on_edge1 == '#') {
find_Epsilon_Closure(nfa_start->transition1);
}
if (nfa_start->value_on_edge2 == '#') {
find_Epsilon_Closure(nfa_start->transition2);
}
return epsilon_states;
}
struct state * get_state (char *state_number, struct state * temp_head) {
int loop_count = 0;
if (temp_head == (struct state *)NULL) {
return (struct state *)NULL;
}
else if (strcmp(temp_head->state_number,state_number) == 0) {
return temp_head;
}
else {
temp_head = get_state(state_number,temp_head->transition1);
if (temp_head == (struct state *)NULL) {
temp_head = get_state(state_number,temp_head->transition2);
if (temp_head == (struct state *)NULL)
return (struct state *)NULL;
else {
return temp_head;
}
}
else {
return temp_head;
}
}
}
char * del_cap (struct state * dfa_state, char input) {
char *output_states,*temp,*states;
int loop_count =0,flag=OUTSIDE;
struct state * state, * head = nfa->start;
char temp_state_number[2];
temp = (char *) malloc(MAX);
output_states = (char *)malloc(MAX);
strcpy(output_states,"`");
strcpy(states,"");
for (loop_count = 0; dfa_state->state_number[loop_count] != '\0';loop_count++) {
if (dfa_state->state_number[loop_count] != '`') {
if (flag == INSIDE) {
temp_state_number[0] = dfa_state->state_number[loop_count-1];
temp_state_number[1] = dfa_state->state_number[loop_count];
state = get_state(temp_state_number,head);
strcat(states,delta(state,input));
}
else if(dfa_state->state_number[loop_count+1] == '`') {
temp_state_number[0] = dfa_state->state_number[loop_count];
temp_state_number[1] = '\0';
state = get_state(temp_state_number,head);
strcat(states = delta(state,input));
}
flag = INSIDE;
}
else
flag = OUTSIDE;
}
for(loop_count = 0; states[loop_count] != '\0';loop_count++) {
state = get_state(states[loop_count],head);
strcat(output_states, find_Epsilon_Closure(state));
}
printf("\n[%s] -- %c --> [%s]\n ",dfa_state->state_number,input,output_states);
return output_states;
}