/* ***************************************************************
   File    : fsm_operators.c
   Author  : Himanshu A. Sanghavi
   Advisor : Dr. Vijay K. Garg
   Date    : August 1, 1991

   This file contains functions for performing most of the
   operations on finite state machines.

   *************************************************************** */


#include "fsm.h"

/* ***************************************************************
   This file contains the definition of some data structures and
   code for some functions which are to be hidden from the user.
   Hence these data structures are defined in this file and not
   in the file "fsm.h".  Similarly the functions to be hidden are
   defined as static functions.  These functions and data 
   structures will never required by the user directly - they are
   only to be used by the top level functions.
   *************************************************************** */


  /*****   BEGINING OF STATIC FUNCTIONS AND DATA STRUCTURES   *****/

/*GREG ADDING*/

struct _statepairslist{
     char xname[MAX_LENGTH];
     char yname[MAX_LENGTH];
     int matched;
     struct _statepairslist *next;
};
typedef struct _statepairslist ST_PAIRS_LIST;

void insert_stpair(ST_PAIRS_LIST **pairin, char *xin, char *yin)
{
    ST_PAIRS_LIST *newpair = (ST_PAIRS_LIST *) malloc(sizeof(ST_PAIRS_LIST));
    
    strcpy(newpair->xname, xin);
    strcpy(newpair->yname, yin);
    newpair->matched = 0;  /*default is haven't found match*/
    
     newpair->next = *pairin;
     *pairin = newpair;
}

void free_stpair(ST_PAIRS_LIST **pairin)
{
    ST_PAIRS_LIST *tmppair, *tmppair2;
   
   tmppair = *pairin;
   while(tmppair)
    {
    tmppair2 = tmppair->next;
    free(tmppair);
    tmppair = tmppair2;
    }
*pairin = NULL;
}

int compare_stpairs(ST_PAIRS_LIST *pair1, ST_PAIRS_LIST *pair2)
{
   int this_pair_match = 0, allmatched = 1;
   ST_PAIRS_LIST *currentpair1 = pair1, *currentpair2= pair2;
   
   while(currentpair1)
   {

     while(currentpair2 && !this_pair_match)
     {
        if(strcmp(currentpair1->xname, currentpair2->xname)==0)
        {
           if(strcmp(currentpair1->yname, currentpair2->yname)==0)
           {
            this_pair_match = 1;
            /*currentpair1->matched = 1;*/
            currentpair2->matched = 1;
           }
        }
      currentpair2 = currentpair2->next;  
      }
     if(!this_pair_match)
      {
       return 0;
      }
     else
      { /*there was a match so check next state pair*/
       this_pair_match = 0;
       currentpair1 = currentpair1->next;
       currentpair2 = pair2;
      }
   }
/*all states in pair1 were matched, how about pair2?*/   

currentpair2 = pair2;
while(currentpair2 && allmatched) /*allmatched starts as 1*/
    {   
    allmatched = (currentpair2->matched) & allmatched;
    currentpair2 = currentpair2->next;
    }
if(allmatched)
 return 1;
else
 return 0;
}


void parse_stpair(char *statestring, ST_PAIRS_LIST **pair1)
{
char *ptrcomma, Z[MAX_LENGTH*2], *statenobad, *result, x[MAX_LENGTH*2], y[MAX_LENGTH*2];

ptrcomma = strstr(statestring, ","); /*x,y,Z*/
ptrcomma = strstr((ptrcomma+1), ",");/*now points to ,Z*/
strcpy(Z, ptrcomma+1);

statenobad = strtok( Z, "@");/*get rid of @$ marking for bad state*/
if(statenobad!=NULL)
 strcpy(Z, statenobad);

result = NULL;
result = strtok( Z, ",");

while(result !=NULL){
    strcpy(x,result);
    result = strtok( NULL, "," );

if(result !=NULL){
    strcpy(y, result);
    result = strtok( NULL, "," );
    insert_stpair(pair1, x, y);
}
else{ puts("there is a missing pair");}
}
}

/*GREG ABOVE*/

struct _deplist;


/* ****************************************************************
   This is a data structure to store pairs of states which
   are candidates for equivalence.  The information contained
   in its fields is:

   first - pointer to the first state of the pair
   second - pointer to the second state of the pair
   dependent - pointer to the list of state pairs dependent
               on this pair
   next - pointer to the next pair of the list
   **************************************************************** */

struct _equivlist {
        ST_LIST      		*first;
        ST_LIST                 *second;
	struct _deplist		*dependent;
	struct _equivlist	*next;
};

typedef struct _equivlist EQUIV_LIST;


/* ***************************************************************
   This is a data structure used to store the dependent list of
   of a given pair of states.  It stores pointers to all pairs
   dependent on the current pair. The information contained in
   it is:

   pair - pointer to a dependent pair
   next - pointer to the next element of the dependent list
   **************************************************************** */

struct _deplist  {
	EQUIV_LIST 	*pair;
	struct _deplist	*next;
};

typedef struct _deplist DEP_LIST;

/* ***************************************************************
   This is a data structure to store a list of state pointers.
   It is used to store the pointers to states that are reachable
   from a given state.  

   The information stored in the two fields is

   st_ptr - pointer to a reachable state
   next - pointer to the next entry in the list
   **************************************************************** */
   
struct _stptrlist {
        ST_LIST		  *st_ptr;
	struct _stptrlist *next;
};

typedef struct _stptrlist ST_PTR_LIST;



/* ****************************************************************
   Data structure for storing a linked list of transition input
   symbol names and their type (i.e controllable or uncontrollable).
   Such a linked list is used by the fsm_find_sigma function to
   store the list of all input symbols for the state machine   

   Its elements store the following information:

   input : character string which stores the input symbol
   type  : stores the type of the transition
   next  : pointer to the next element of the linked list 

   **************************************************************** */

struct _translist {
	char			input[MAX_LENGTH];
	struct _translist	*next;
};

typedef struct _translist TRANS_LIST;


/* **************************************************************
   This structure is used to store a linked list of states 
   which are the resultant states of a particular transition from a
   given set of states.

   st_list - linked list of resultant states 
   name    - name of the aggregate state formed by combining all
	     the above states
   next    - pointer to the next entry of this list
   *************************************************************** */

struct _liststlist {
	ST_PTR_LIST		*st_list;
	char			name[MAX_LENGTH];
	struct _liststlist	*next;
};

typedef struct _liststlist LIST_ST_LIST;

/* *****************************************************************
   Function : find_pair

   This function finds out if a state pair exists in the linked
   list storing such pairs.  This function is defined to be static.

   Arguments : list - pointer to the linked list of pairs
	       st1_ptr - pointer to the first state of the pair
	       st2_ptr - pointer to the second state of the pair

   Return Type : EQUIV_LIST * - returns a pointer to the entry 
		 containing the state pair if it exists.  If not, 
		 it returns a NULL pointer
 
   ****************************************************************  */

static EQUIV_LIST* find_pair(list, st1_ptr, st2_ptr)
EQUIV_LIST *list;
ST_LIST *st1_ptr, *st2_ptr;
{
   /* step through each entry of the list and check if it is
      the required entry */
   while (list) {  

      /* if this is the pair that we are looking for then stop
         the search by breaking from the loop */
      if ((list->first == st1_ptr && list->second == st2_ptr) ||
	  (list->second == st1_ptr && list->first == st2_ptr))
 	 break;  

      list = list->next; 
   }

   /* return a pointer to the entry if it was found, a NULL pointer
      otherwise */
   return(list);  
}



/* ******************************************************************
   Function : insert_pair
 
   This function inserts a pair of states into the linked list
   storing such pairs.  This function is defined to be static.

   Arguments : list_ptr - pointer to pointer to the list
               st1_ptr - pointer to the first state of the pair
               st2_ptr - pointer to the second state of the pair
   
   Return Type : EQUIV_LIST * - returns a pointer to the inserted pair

   ***************************************************************** */

static EQUIV_LIST* insert_pair(list_ptr, st1_ptr, st2_ptr)
EQUIV_LIST **list_ptr;
ST_LIST *st1_ptr, *st2_ptr;
{
   EQUIV_LIST *exists, *tmp, *current, **anchor;

   /* first check if the pair already exists */
   exists = find_pair(*list_ptr, st1_ptr, st2_ptr);

   /* if it does not exist, insert it */
   if (!exists) {

      /* allocat storage and set the various field appropriately */
      tmp = (EQUIV_LIST *) malloc(sizeof(EQUIV_LIST));
      tmp->first = st1_ptr;
      tmp->second = st2_ptr;
      tmp->dependent = NULL;
      tmp->next = NULL;

      /* anchor is used to insert the new entry in the list */
      anchor = list_ptr;

      /* step through the list till you come to the last entry */
      current = *list_ptr;
      while (current) {
	 anchor = &current->next;
	 current = current->next;
      }

      /* insert the new entry as the last entry of the list */
      *anchor = tmp;

      exists = tmp;
   }

   /* return a pointer to the required entry */
   return(exists);  
}


/* *****************************************************************
   Function : delete_pair

   This function deletes an entry from the linked list of state 
   pairs.  It also deletes all state pairs that are dependent on
   it.  This function is defined to be static.

   Arguments : list_ptr - pointer to pointer to the list
               pair_ptr - pointer to the pair to be deleted

   Return Type : void

  ****************************************************************** */

static void delete_pair(list_ptr, pair_ptr)
EQUIV_LIST **list_ptr, *pair_ptr;
{
   EQUIV_LIST *this, **anchor;
   DEP_LIST *dep, *ptr1, *ptr2;

   /* anchor is used to complete the pointer linkage after an entry
      is removed from the linked list  */
   anchor = list_ptr;

   /* start with the first entry of the list and step through
      each entry to check if this is the entry to be deleted */
   this = *list_ptr;  
   while (this) {  
    
      /* if this is the pair to be deleted, stop the search */
      if (this == pair_ptr) break;  

      /* else try the next element of the list */
      anchor = &this->next;
      this = this->next;  /* not this one, try the next one */

   }

   /* if the pair does not exist in the list, do nothing */
   if (!this) return;

   /* Remove the entry from the linked list */
   *anchor = this->next;

   /* Now check if there are any entries in the dependent list */
   dep = this->dependent;

   while (dep) { /* delete each entry in the dependent list */ 
      delete_pair(list_ptr, dep->pair);
      dep = dep->next;
   }

   /* free the space used to store the dependent list */
   ptr1 = this->dependent;
   while (ptr1) {      
      ptr2 = ptr1->next;
      free(ptr1);
      ptr1 = ptr2;
   }

   free(this);  /* free the space used to store the state pair */
}


/* ******************************************************************
   Function : insert_dep
  
   This function inserts a entry in the "dependent" list of 
   a state pair.  This function is defined to be static.

   Arguments : list  - list of state pairs
	       base_pair - pair in which the dependency is to 
                           be inserted
	       dependent_pair - the pair which is dependent on
                                the base pair

   Return Type : void

   ***************************************************************** */

static void insert_dep(list, base_pair, dependent_pair)
EQUIV_LIST *list, *base_pair, *dependent_pair;
{
   DEP_LIST *tmp;

   /* create the entry to be inserted */
   tmp = (DEP_LIST *) malloc(sizeof(DEP_LIST));
   tmp->pair = dependent_pair;

   /* insert the entry in the dependent list  */
   tmp->next = base_pair->dependent;
   base_pair->dependent = tmp;
}


/* ************************************************************
   Function : insert_stptr

   This function inserts an entry into the linked list of state
   pointers.  The entry is inserted only if it does not already 
   exist.  This function is defined to be static. 

   Argument : list_ptr - pointer to pointer to list
              state - pointer to the state to be inserted
 
   Return Type : int - returns 1 if the entry already exists 
		       0 if it did not exist and was inserted
   *************************************************************  */

static int insert_stptr(list_ptr, state)
ST_PTR_LIST **list_ptr;
ST_LIST *state;
{
   ST_PTR_LIST *current, *tmp;
   int flag;

   current = *list_ptr;

   /* first check if the entry already exists */
   while (current) {
      if (current->st_ptr == state) break;
      current = current->next;
   }

   /* if the entry exists, current will not be NULL and 
      hence return a 1 */
   if (current) return(1);

   /* The entry does not exist so insert it  */
   tmp = (ST_PTR_LIST *) malloc(sizeof(ST_PTR_LIST));
   tmp->st_ptr = state;

   /* it is inserted as the first element in the list */
   tmp->next = *list_ptr;
   *list_ptr = tmp;

   /* return 0 since the entry did not exist and was inserted */
   return(0);
}


/* ***************************************************************
   Function : insert_ord_stptr

   This function inserts an entry into an ordered list of elements
   which are pointers to the states of a fsm.  The routine is
   similar to the function "insert_stptr", the difference being
   that the former does not maintain an ordered list.  This 
   function is also static. 

   Arguments : stptr_list - pointer to pointer to the ordered list
     	       st_ptr - pointer to the state to be inserted

   Return Type : void

   *************************************************************** */

static void insert_ord_stptr(stptr_list, st_ptr)
ST_PTR_LIST **stptr_list;
ST_LIST *st_ptr;
{
   ST_PTR_LIST *ptr1, *tmp, **anchor;
   int flag;

   /* anchor is used to insert the entry when the appropriate 
      place in the ordered list is found */
   anchor = stptr_list;

   /* start with the first entry of the list and search for the 
      place where the new entry is to be inserted */
   ptr1 = *stptr_list;
   while (ptr1) {

      /* compare the name of the current state and the name of the
	 new state to be inserted */
      flag = strcmp(st_ptr->name, ptr1->st_ptr->name);

      /* if they are the same, the entry already exists so do 
	 nothing and return */
      if (flag == 0) return;

      /* if the name of the new state to be inserted is greater than
	 the name of the current state of the list, check the next
	 entry */
      else if (flag > 0) {
	 anchor = &ptr1->next;
	 ptr1 = ptr1->next;
      }

      /* if the name of the new state to be inserted is less than
	 the name of the current state of the list, this is where
	 the new entry has to be inserted */
      else break;
   }

   /* allocate space and insert the new entry into the list */
   tmp = (ST_PTR_LIST *) malloc(sizeof(ST_PTR_LIST));
   tmp->st_ptr = st_ptr;
   tmp->next = ptr1;
   *anchor = tmp;
}


/* ***************************************************************
   Function : find_trans_list

   This function checks if a particular transition exists in the
   linked list of transitions.  This function is static.

   Arguments : list - pointer to the linked list
               name - input symbol of the transition

   Return Type : int - returns 1 if the symbol exists, 0 otherwise

   **************************************************************** */

static int find_trans_list(list, name)
TRANS_LIST *list;
char *name;
{
   /* step through the linked list */
   while (list) {
      /* if the symbol is found, return 1 */
      if (strcmp(list->input, name) == 0) return(1);
      list = list->next;
   }

   /* return 0 since the symbol was not found in the list */
   return(0);
}


/* **************************************************************
   Function : insert_trans_list

   This function inserts an entry in the linked list of 
   transitions. This function is static.

   Arguments :  list_ptr - pointer to pointer to the list
                name - name of the input symbol to be inserted
                type - type of the transition

   Return Type : void

   *************************************************************** */

static void insert_trans_list(list_ptr, name)
TRANS_LIST **list_ptr;
char *name;
{
   TRANS_LIST *tmp;

   /* first check if the entry already exists in the list */
   tmp = *list_ptr;
   while (tmp) {
      if(strcmp(tmp->input, name) == 0) break;
      tmp = tmp->next;
   }
   
   /* you need to insert only if the entry does not exist */
   if (!tmp) {

      /* allocate space for new entry and assign the appropriate
         values to its fields */
      tmp = (TRANS_LIST *) malloc(sizeof(TRANS_LIST));
      strcpy(tmp->input, name);

      /* insert the entry into the linked list as the first
         element of the list */
      tmp->next = *list_ptr;
      *list_ptr = tmp;
   }
}


/* **************************************************************
   Function : fsm_find_sigma

   This function finds out the input alphabet (i.e. sigma) for
   a given state machine. This function is static.

   Arguments : fsm_ptr - pointer to the state machine
	       list - linked list in which the input alphabet is
		      returned

   Return Type : void

   ************************************************************** */

static void fsm_find_sigma(fsm_ptr, list)
FSM *fsm_ptr;
TRANS_LIST **list;
{
   ST_LIST *current;
   TR_LIST *this;

   *list = NULL;

   /* start with the initial state */
   current = fsm_ptr->states;
   while (current) {        /* step through each state */
      this = current->trans;
      while (this) {        /* step through each transition */
         /* maintain a list of all input symbols encountered so far */
	 insert_trans_list(list, this->input);
	 this = this->next;
      }
      current = current->next;
   }
}


  /******    END OF STATIC FUNCTIONS AND DATA STRUCTURES   *****/


/*VC new printing routine for files     */
	 
	  
/* ***********************************************************
Function : list_print
		  
This function prints the list information of a fsm
to an output file
Arguments : fsm_ptr - pointer to the state machine
list - linked list in which the input alphabet is
returned
Return Type : void
************************************************************ */
								   
void list_print(fp, fsm_ptr)
FILE *fp;
FSM *fsm_ptr;
{
   	TRANS_LIST *list = NULL, *list_ptr;
	
	int sigma_count = 0;
   /* first find out the input alphabet i.e sigma of this machine */
	fsm_find_sigma(fsm_ptr, &list);

	list_ptr = list;

	while (list_ptr != NULL){
	/*		fprintf(fp, "%d\n", list_ptr->type);		*/
		fprintf(fp, "%s\n", list_ptr->input);
		list_ptr = list_ptr->next;
		++sigma_count;
	}

	fprintf(fp, "\n\nThe fsm has %d number of events\n", sigma_count);
}


/*VC new printing routine for files     */
	 
	  
/* ***********************************************************
Function : exclusive_events 
		  
This function prints the list information of a fsm
to an output file
Arguments : fsm_ptr - pointer to the state machine
list - linked list in which the input alphabet is
returned
Return Type : void
************************************************************ */
								   
void exclusive_events(fsm_ptr1,  fsm_ptr2, fp3)
FSM *fsm_ptr1, *fsm_ptr2;
FILE *fp3;
{
   	TRANS_LIST *list2 = NULL, *list_ptr2;
   	TRANS_LIST *list1 = NULL, *list_ptr1;
	
	
	fsm_find_sigma(fsm_ptr1, &list1);
	list_ptr1 = list1;
	
	fsm_find_sigma(fsm_ptr2, &list2);
	list_ptr2 = list2;


	while (list_ptr1 != NULL){
		list_ptr2 = list2;
		while (list_ptr2 != NULL){
			if( ( strcmp(list_ptr1->input, list_ptr2->input)) != 0){
				list_ptr2 = list_ptr2->next;	
			    if (list_ptr2 == NULL){
					fprintf(fp3, "%s\n", list_ptr1->input);
				}
				else	
					;
			}
			else
				break;

		}	
	list_ptr1 = list_ptr1->next;	
	}
}


/* ****************************************************************
   Function : fsm_reachability

   This function finds out all the states that, through a particular
   transition,  are reachable from a given initial state.  The names 
   of all the reachable states are returned in the form of a linked 
   list of names.  If the states which can be reached through a
   particular transition only are to be computed, the argument
   "trans_name" contains the name of this transition.  If the 
   states which are reachable through ANY transition are to be
   computed, this argumet is the reserved word "ALL".

   Arguments : fsm_ptr - pointer to the state machine
               state_name - name of the state whose reach is to
			    be computed
	       trans_name - name of the input transition
	       name_list - pointer to name list in which the names
			   of the reachable states are returned

   Return Type : int - number of states that are reachable
                       from the starting state 

   *************************************************************** */

int fsm_reachability(fsm_ptr, state_name, trans_name, name_list)
FSM *fsm_ptr;
char *state_name, *trans_name;
NAME_LIST **name_list;
{
   ST_LIST *st_ptr, *agg_st1, *agg_st2;
   TR_LIST *this, *tmp, *tr1, *tr2, **anchor;
   ST_PTR_LIST *lst_ptr, *list = NULL;
   NAME_LIST **name_ptr;
   int i, exists, count = 0;

   /* first check the arguments for NULL pointers */
   if (!fsm_ptr) 
      prog_abort("fsm_reachability : NULL pointer passed as argument for (FSM *)");

   if (!name_list) 
      prog_abort("fsm_reachability : NULL pointer passed as argument for (NAME_LIST **)"); 


   st_ptr = find_state(fsm_ptr, state_name);
   if (!st_ptr)
      prog_abort("fsm_reachability : state whose reach is to be computed does not exist in the machine");
   
   /* a state is always reachable from itself so insert its
      name as the first entry in the reachability list     */
   insert_stptr(&list, st_ptr);
   ++count;  /* count keeps track of the number of reachable states */

   /* Allocate space for two "aggregate states". agg_st1 is used
      to store all the transitions comming out of the current
      aggregate state while agg_st2 is used to build the new
      aggregate state for the next iteration.  The aggregate state
      for the next iteration is a state which is a combination of all 
      states reachable via a single transition from the current 
      aggregate state */
   agg_st1 = alloc_state;
   agg_st2 = alloc_state;
   agg_st1->trans = agg_st2->trans = NULL;

   /* to begin with, the starting state whose reach is to be
      computed is the first aggregate state so copy the transition
      information of the starting state into agg_st1            */
   this = st_ptr->trans;
   anchor = &agg_st1->trans;
   while (this) {
      if (strcmp(trans_name, "ALL") == 0 || 
			strcmp(trans_name, this->input) == 0) {
         /* self loops are to be avoided so transitions that 
            lead back to the initial state are omitted       */
         if (this->next_state != st_ptr) {
            tmp = alloc_trans; 
	        /*tmp->input = (char *) malloc(strlen(this->input) + 4);/*now static memory*/
            strcpy(tmp->input, this->input);
            tmp->next_state = this->next_state;
            tmp->next = NULL;
            *anchor = tmp;
            anchor = &tmp->next;
         }
      }
      this = this->next;
   }
   /* anchor is used to insert transitions in the new aggregate
      state under construction */
   anchor = &agg_st2->trans;
   do {
      this = agg_st1->trans;
      while (this) {
         /* the state to which this transition leads to is reachable
            from the start state so insert its name in the list of
            reachable states */
	 exists = insert_stptr(&list, this->next_state);
        
         /* if the state already existed in the list, it has been
            processed before so it need not be processed again */
         if (!exists) {
            /* process only those states which did not already exist
               in the list of reachable states */
            ++count;
	    st_ptr = this->next_state;
            tr1 = st_ptr->trans;
            /* all the transitions of the state are inserted as
               transitions of the new aggregate state under
               construction */
	    while (tr1) {
		if (strcmp(trans_name, "ALL") == 0  ||
				strcmp(trans_name, tr1->input) == 0) {
   	           tmp = alloc_trans; /*now static memory*/
		       /*tmp->input = (char *) malloc(strlen(tr1->input) + 4);/*now static memory*/
	           strcpy(tmp->input, tr1->input);
	           tmp->next_state = tr1->next_state;
	           tmp->next = NULL;
	           *anchor = tmp;
	           anchor = &tmp->next;
		}
	        tr1 = tr1->next;
	    }
         }

	 this = this->next;
      }

      /* all the transitions of the current aggregate state have
         been processed so release the memory reserved for its use */
      tr1 = agg_st1->trans;
      while (tr1) {
         tr2 = tr1->next;
	 /*free(tr1->input);/*now static memory*/
	 free(tr1);
	 tr1 = tr2;
      }

      /* At this point the new aggregate state is complete in the
         sense that it contains all the transitions going out of
         the various states that were inserted in the reachability
         list in this iteration. Hence make this new aggregate state
         as the current aggregregate state for the next iteration 
         and set the new aggregate state for the next iteration to
         have zero transitions */
      agg_st1->trans = agg_st2->trans;
      agg_st2->trans = NULL;

     /* If agg_st1 has no transitions it means that no new states
        can be reached from the current aggregate state. Thus all
        reachable states have been covered */
   } while (agg_st1->trans);
   /* form a list of the names of all the reachable states
      free the storage used for storing the list of pointers to
      these states */
   name_ptr = name_list;
   while (list) {

      /* remember pointer to the next entry of the list of
         state pointers since this entry will be deleted */
      lst_ptr = list->next;

      /* allocate storage for next element of the name list and
         assign appropriate values to its fields */
      *name_ptr = (NAME_LIST *) malloc(sizeof(NAME_LIST));
      strcpy((*name_ptr)->name, list->st_ptr->name);
      (*name_ptr)->next = NULL;

      /* insert the new element as the last element of the name list */
      name_ptr = &((*name_ptr)->next);   

      /* free the storage used for storing the current entry of the
         list of state pointers */

      free(list);/*???*/

      list = lst_ptr;
   }
#ifdef X
   /* This is Sudhir's change to the library  */
   free(*name_ptr);
   free(agg_st1);
   free(agg_st2);
   /* End of change */
#endif
   return(count);
}


/* ******************************************************************
   Function : fsm_minimize

   This function minimizes a given state machine.  If the given
   machine is not minimal, the equivalent states are combined 
   together to produce a minimal state machine.

   Arguments : fsm_ptr - pointer to the state machine to be 
                         minimized

   Return Type : int - returns 1 if the the machine is minimal, 
		       0 if it is not

   ***************************************************************** */

int fsm_minimize(fsm_ptr)
FSM *fsm_ptr;
{
   int match1, match2, match3, match4;
   char name[MAX_LENGTH];
   BOOLEAN remove_flag, exists_flag;
   ST_LIST *st_ptr, *current, *st1, *st2;
   TR_LIST *tr1, *tr2;
   EQUIV_LIST *st_pair, *nxt_pair, *pair_ptr, *exists, *base_pair,
              *list = NULL;
   NAME_LIST *name_list = NULL, *name_ptr;

   if (!fsm_ptr)
	prog_abort("fsm_minimize : NULL pointer passed as argument for (FSM *)");

   /* First create pairs of states that can be equivalent - pairs 
      with both states marked or both states unmarked.  These 
      pairs are stored in a linked list. */

   st_ptr = fsm_ptr->states;  /* start with the first state */
   while (st_ptr) {   /* check for each pair */
      /* compare this state with every other state which follows it */
      current = st_ptr->next;
      while (current) {
            /* check if the current state and the base state form
               a pair which is a candidate for equivalence */
            if (st_ptr->marked == current->marked && 
			get_NTrans(st_ptr) == get_NTrans(current)) 
	       insert_pair(&list, st_ptr, current);
         current = current->next;
      }
      st_ptr = st_ptr->next;
   }

   /* For each pair of states which are possible candidates for
      equivalent states, see if they can be distinguished between
      by a particular transition */
   st_pair = list;
   while (st_pair) {  /* check each pair of the list */
      nxt_pair = st_pair->next;
      remove_flag = FALSE;
      tr1 = st_pair->first->trans; tr2 = st_pair->second->trans;
      while (tr1) {
	 exists_flag = FALSE;
         while (tr2) {
            /* see if the current transitions of both the states are
               triggered by the same input */
            if (strcmp(tr1->input, tr2->input) == 0) {
		exists_flag = TRUE;
                /* if the same transition occurs in both states, see
                   if the pair of new states (on occurance of the
                   transition) is a candidate for equivalence */
		exists = find_pair(list, tr1->next_state,
					 	tr2->next_state);
                if (!exists) {
                   /* if not then check if both the transitions lead
                      to the same state */
                   if (tr1->next_state != tr2->next_state) {
                      /* if not, then delete the current pair from 
                         the list of pairs which hold possibly
                         equivalent states */
		      delete_pair(&list, st_pair); 
                  
                      /* since one transition can distinguish between 
                      the two states under consideration, we need not 
                      check for the other transitions of the same 
		      states */
		      remove_flag = TRUE;
                      break;
		  }   
                }
            }
            if (exists_flag) break;  
            tr2 = tr2->next;
         }

	 /* the current pair has to be removed either if remove flag
	    is set to TRUE or exists flag is FALSE */
	 if (!exists_flag) {
	    delete_pair(&list, st_pair);
	    remove_flag = TRUE;
	 }
         if (remove_flag) break;
         tr1 = tr1->next; tr2 = st_pair->second->trans;
      }

      /* if it was not possible to distinguish between the states
         under consideration then check for dependencies to be
         considered */ 
      if (!remove_flag) {
	 tr1 = st_pair->first->trans; tr2 = st_pair->second->trans;

	 while (tr1) {
	    while (tr2) {

                /* dependency arises if a common transition exists for
                   the two states and the transition leads to different
                   states for the two cases */
		if (strcmp(tr1->input, tr2->input) == 0 && 
				tr1->next_state != tr2->next_state) {
		   base_pair = find_pair(list, tr1->next_state, 
						   tr2->next_state);
		   insert_dep(list, base_pair, st_pair);
                }
                tr2 = tr2->next;

            }

            /* check for the next transition of st1 */
	    tr1 = tr1->next;
            /* tr2 reset to first state of st2 */
	    tr2 = st_pair->second->trans;
         }
      }

      /* the next pair to be considered is stored in the pointer
         nxt_pair */
      st_pair = nxt_pair;
   }
   
   /* if the list of equivalent pairs is empty, the state machine
      as given is minimal */
   if (!list) return(1);

   
   /* if the list of equivalent pairs is not empty, scan the list
      of state machines and combine all two equivalent states 
      into one  so as to minimize the state machine */
   st_pair = list;
   while (st_pair) {

      /* name of the equivalent state is the concatenation of the
         names of the two individual states */
      strcpy(name, st_pair->first->name);

      /* before concatenating the strings ensure that its length
         does not exceed the maximum limit */
      if (strlen(name) + strlen(st_pair->second->name) >= MAX_LENGTH)
         prog_abort("fsm_minimize : length of a string exceeds MAX_LENGTH");
	
      strcat(name, st_pair->second->name);
      /*free(st_pair->first->name);
      st_pair->first->name = (char *) malloc(strlen(name) + 1);/*now static memory*/
      strcpy(st_pair->first->name, name); 

      /* scan all the remaining entries in the list and if any
         of the pointers point to the second state of the current
         pair, make the pointer point to the first state of the
         current pair */
      pair_ptr = st_pair->next;
      while (pair_ptr) {

         nxt_pair = pair_ptr->next;

         match1 = (pair_ptr->first == st_pair->first);
         match2 = (pair_ptr->second == st_pair->first);
         match3 = (pair_ptr->first == st_pair->second);
         match4 = (pair_ptr->second == st_pair->second);

         if ((match1 && match4) || (match2 && match3))
	    delete_pair(&list, pair_ptr);
         else if (match3)
	    pair_ptr->first = st_pair->first;
         else if (match4)
	    pair_ptr->second = st_pair->first;

         pair_ptr = nxt_pair;
      }


      /* scan the state machine and if any transition leads to the
         second state of the equivalent pair, make the transition lead
         to the new equivalent state so that the second state can be
         deleted from the state machine */
      current = fsm_ptr->states;
      while (current) {
	 tr1 = current->trans;
         while (tr1) {
	    if (tr1->next_state == st_pair->second)
                /* this transition points to the state to be deleted
                   so make it point to the new aggregate state */ 
		tr1->next_state = st_pair->first;
	    tr1 = tr1->next;
         }
         current = current->next;
      }
   	 
      /* remove the state which was second in the pair of 
         equivalent states from the pointer linkage of the 
         states of the machine */
      delete_state(fsm_ptr, st_pair->second);

      /* process the next pair of equivalent states */
      st_pair = st_pair->next;
   }

   /* free the storage used for storing the list of state pairs */
   while (list) {
      st_pair = list->next;
      free(list);
      list = st_pair;
   }

   /* now find out if there are any states that are unreachable
      from the initial state */
   fsm_reachability(fsm_ptr, fsm_ptr->states->name, "ALL", &name_list);

   /* step through the states of the state machine and if any
      unreachable state is encountered, delete it */
   current = fsm_ptr->states;
   while (current) {
      st_ptr = current->next;
      if (!find_name(name_list, current->name))
 	 delete_state(fsm_ptr, current);
      current = st_ptr;
   }

   /* now free the storage used for the linked list of names */
   delete_name(&name_list);

   /* return zero since the original machine was not minimal */
   return(0);
}


/* ***************************************************************
   Function : fsm_remove_epsilon

   This function converts a machine with epsilon transitions to
   a machine without epsilon transitions.  The resultant machine
   is likely to be non-deterministic.

   Arguments : fsm1_ptr - the input machine with epsilon transitions
               fsm2_ptr - the output machine without epsilon
			  transitions

   Return Type : void

   *************************************************************** */

void fsm_remove_epsilon(fsm1_ptr, fsm2_ptr)
FSM *fsm1_ptr, *fsm2_ptr;
{
   ST_LIST *current1, *current2, *st_ptr;
   TR_LIST *this, *tr1;
   TRANS_LIST *sigma = NULL, *sigma_ptr, **anchor;
   NAME_LIST *epsilon_closure = NULL, *state_names = NULL, *name_ptr;
   ST_PTR_LIST *state_set = NULL, *list_ptr, *next_ptr;


   if (!fsm1_ptr || !fsm2_ptr)
	prog_abort("fsm_remove_epsilon : NULL pointer passed as argument for (FSM *)");

   /* first find out the input alphabet i.e sigma of this machine */
   fsm_find_sigma(fsm1_ptr, &sigma);

   /* remove the epsilon transition from this alphabet 
      anchor is used to complete the pointer linkage after
      the entry corresponding to "*" is removed from the list */
   anchor = &sigma;    
   sigma_ptr = sigma;
   while (sigma_ptr) {
      if (strcmp(sigma_ptr->input, "*") == 0) {
         /* the epsilon transition has been detected */
	 *anchor = sigma_ptr->next;
	 free(sigma_ptr);
	 break;
      }
      anchor = &sigma_ptr->next;
      sigma_ptr = sigma_ptr->next;
   }

   /* ensure that fsm2 is empty, start from the first state of fsm1
      and step through all its states one by one */
   fsm2_ptr->states = NULL;
   current1 = fsm1_ptr->states;
   
   while (current1) {

      /* insert the current state of fsm1 in fsm2 */
      current2 = insert_state(fsm2_ptr, current1->name);
      current2->marked = current1->marked;

      /* compute the epsilon closure of the current state of fsm1 */
      fsm_reachability(fsm1_ptr, current1->name, "*", &epsilon_closure);

      /* if the current state of fsm1 is unmarked but its epsilon
         closure includes at least one state which is marked, then
         the current state of fsm2 is to be marked  */
      if (!current1->marked) {
         /* step through the list of states belonging to the
            epsilon closure of state current1 */
	 name_ptr = epsilon_closure;
         while (name_ptr) {
	    st_ptr = find_state(fsm1_ptr, name_ptr->name);
	    if (st_ptr->marked) {
                /* a marked state is detected so mark state current2 */
 		current2->marked = MKD;
                /* no need to check the remaining states of the
                   epsilon closure of current1 */
		break;
	    }
	    name_ptr = name_ptr->next;
	 }
      }

      /* Next, for each element "a" of the input alphabet, compute
         the set of states reachable through a sigle transition 
         labelled "a" from any of the states belonging to the 
         epsilon closure of current1 */

      /* start with the first element of the input alphabet and
         check each element one by one */
      sigma_ptr = sigma;
      while (sigma_ptr) {
         /* check each state of the set of states belonging to the
            epsilon closure of current1 to see if the transition
            under consideration is allowed in that state */
	 name_ptr = epsilon_closure;
	 while (name_ptr) {
	    /* check each transition of this state */
	    st_ptr = find_state(fsm1_ptr, name_ptr->name);
	    tr1 = st_ptr->trans;
	    while (tr1) {
		if (strcmp(tr1->input, sigma_ptr->input) == 0) 
		   /* transition is allowed so insert the next state
                      of this transition i.e. the state that this
		      transition leads to in the list "state_set" */
		   insert_stptr(&state_set, tr1->next_state);
		tr1 = tr1->next;
	    }
	    name_ptr = name_ptr->next;
	 }

	 st_ptr = insert_state(fsm1_ptr, "dead");
	 list_ptr = state_set;
	 while (list_ptr) {
	    next_ptr = list_ptr->next;
	    insert_trans(fsm1_ptr, st_ptr, "*", 
						list_ptr->st_ptr->name);
	    this = list_ptr->st_ptr->trans;
	    while (this) {
		insert_trans(fsm1_ptr, st_ptr, this->input,
						this->next_state->name);
		this = this->next;
	    }

	    free(list_ptr);
	    list_ptr = next_ptr;
	 }
	 state_set = NULL;

	 fsm_reachability(fsm1_ptr, "dead", "*", &state_names);
	 delete_state(fsm1_ptr, st_ptr);
	
	 /* The list target_state contains all the state that are
            reachable through transition "a" or epsilon from the
            current1 in fsm1 - this corresponds to all the states
            reachable on transition "a" from current2 in fsm2 hence
            insert the corresponding transitions in fsm2 
	    also free the space used to store the list target_set
            since it is no longer required  */

	 while (state_names) {
	    name_ptr = state_names->next;
	    if (strcmp(state_names->name, "dead") != 0)
	       insert_trans(fsm2_ptr, current2, sigma_ptr->input,
			       state_names->name);
	    free(state_names);/*instead of deleting entire list, just one at a time*/
	    state_names = name_ptr;
	 }

         /* now process the next element of the list containing the
            input alphabet of the given state machine */
         sigma_ptr = sigma_ptr->next;
      }

      /* since current1 has been completely processed, the list
         containing its epsilon closure is no longer required so
         free the corresponding space */
      while (epsilon_closure) {
	 name_ptr = epsilon_closure->next;
	 free(epsilon_closure);
	 epsilon_closure = name_ptr;
      }
      epsilon_closure = NULL;

      /* now process the next state of fsm1 */
      current1 = current1->next;
   }
   
   /* all the states of fsm1 have been processd so the list 
      containing the input alphabet of fsm1 is no longer required
      do free the corresponding storage */
   while (sigma) {
      sigma_ptr = sigma->next;
      free(sigma);
      sigma = sigma_ptr;
   }
}



/* ***************************************************************
   Function : fsm_deterministic

   This function converts a non-deterministic state machine into
   an equivalent deterministic state machine

   Arguments : fsm1_ptr - the non-deterministic state machine
	       fsm2_ptr - the equivalent deterministic state machine

   Return Type : void

   **************************************************************** */

void fsm_deterministic(fsm1_ptr, fsm2_ptr)
FSM *fsm1_ptr, *fsm2_ptr;
{
   ST_LIST *current1, *current2, *exists;
   TR_LIST *this, *tr1, *tr2;
   LIST_ST_LIST *state_set_list, *stlist_ptr, **anchor, *tmp; 
   ST_PTR_LIST  *stptr_list = NULL, *ptr1, *ptr2, *ptr3;
   char nxt_st[MAX_LENGTH];

   if (!fsm1_ptr || !fsm2_ptr)
	prog_abort("fsm_deterministic : NULL pointer passed as argument for (FSM *)");

   /* ensure that fsm2 is empty */
   fsm2_ptr->states = NULL;

   /* anchor is used to insert entries into the list state_set_list
      this list keeps track of the new aggregrate states inserted
      in fsm2 */
   anchor = &state_set_list;

   /* insert the initial state of fsm1 as the first entry of 
      state_set_list as this will also be the initial state of fsm2 */

   /* allocat space for element of state_set_list */
   tmp = (LIST_ST_LIST *) malloc(sizeof(LIST_ST_LIST));
   tmp->next = NULL;

   /* allocate space for element of state list which is one of 
      the fields of state_set_list */
   tmp->st_list = (ST_PTR_LIST *) malloc(sizeof(ST_PTR_LIST));
   tmp->st_list->next = NULL;
   
   /* copy the name of the initial state state of fsm1 into the
      appropriate field of state list and make the pointer point
      the this initial state */
   strcpy(tmp->name, fsm1_ptr->states->name);
   tmp->st_list->st_ptr = fsm1_ptr->states;

   /* insert the entry in state_set_list */
   *anchor = tmp;
   anchor = &tmp->next;

   /* we insert the initial state of fsm2, which as mentioned
      earlier, is the same as the initial state of fsm1 */
   insert_state(fsm2_ptr, fsm1_ptr->states->name);

   /* Now step through all the entries of state_set_list - the 
      list which contains all the states that exist in fsm2. 
      Note that new states keep getting added as we traverse 
      through the list but since all new states are added at  the
      end of the list, they will all be eventually processed. 
      Many of the states inserted in fsm2 are "aggregrate" states
      of some of the states of fsm1.  We need to computed the 
      transitions allowed from each of these states inserted in fsm2.
      A transition that is allowed in any of the states of fsm1
      that combine to form an aggregate state of fsm2 is allowed in 
      the aggregate state.  The next state that this transition 
      leads to in the aggregate state is the union of all the states 
      that this transition leads to from all the states that combine 
      to form this aggregrate state */
      
   /* start with the first entry of the aggregate state list */
   stlist_ptr = state_set_list;
   while (stlist_ptr) {

      /* get a pointer to the corresponding state in fsm2 */
      current2 = find_state(fsm2_ptr, stlist_ptr->name);

      /* initially assume that this state is unmarked */
      current2->marked = UNMKD;

      /* start with the first state and process all states combining
         together to form this aggregrate state */
      ptr1 = stlist_ptr->st_list;
      while (ptr1) {

	 /* current2 is marked if any of its component states
            in fsm1 is marked */
	 current2->marked = current2->marked || ptr1->st_ptr->marked;

	 /* process all the transitions allowed in ptr1 */
	 this = ptr1->st_ptr->trans;
	 while (this) {

	    /* first check if this transition has already been
	       inserted in the current state of fsm2 */
	    tr2 = current2->trans;
	    while (tr2) {
		if (strcmp(tr2->input, this->input) == 0) break;
		tr2 = tr2->next;
	    }

	    /* process the transition only if it has not already
	       been inserted */
	    if (!tr2) {
		/* we need to identify all the states that can be
		   reached through this transition from any of the
	 	   states that combine together to form the current
		   aggregate state */

		/* first insert the next state of this transition
		   in the list to store all reachable states */
		insert_ord_stptr(&stptr_list, this->next_state);

		/* now check if there are any other transitions 
		   labelled with the same input either in this
		   state or in the other states which combine to
		   form the current aggregate state */
	 	ptr2 = ptr1;
		while (ptr2) {

		   if (ptr2 == ptr1)
			/* if processing the transitions of ptr1, we
			   need to check only those transitions that
			   have not yet been processed */
			tr2 = this->next;
		   else
			/* if processing the transitions of another
			   state, all the transitions need to be
			   checked because none of them have been
			   processed as yet */
			tr2 = ptr2->st_ptr->trans;

		   while (tr2) {
			if (strcmp(tr2->input, this->input) == 0) 
			   /* there is another transition with
			      the same input symbol so insert the state
                              that it leads to in the list used to 
                              store the reachable states */
			   insert_ord_stptr(&stptr_list, 
						tr2->next_state);
	 	        tr2 = tr2->next;
		   }

		   /* process the next state of the set of states 
		      which combine to form the aggregrate state */
		   ptr2 = ptr2->next;
		}

		/* Now determine the name of the next state that
  		   this transition leads to from the current state
		   of fsm2.  This name is determined as the 
		   concatenation of all the states that are stored in 
		   the list "stptr_list" */
		strcpy(nxt_st, stptr_list->st_ptr->name);
		ptr3 = stptr_list->next;
		while (ptr3) {
	
		   /* first check if the length of the string will
		      exceed the maximum allowed */
		   if (strlen(nxt_st) + strlen(ptr3->st_ptr->name) +1
							>= MAX_LENGTH)
			prog_abort("fsm_deterministic : length of string exceeds MAX_LENGTH");

		   strcat(nxt_st, ","); /*GREG changed*/
		   strcat(nxt_st, ptr3->st_ptr->name);
		   ptr3 = ptr3->next;
	        }

		/* check if the next state already exists in fsm2 */
 	        exists = find_state(fsm2_ptr, nxt_st);

		/* if it does not then a new aggregate state is
		   being added to fsm2 hence add a corresponding
		   entry in the list "state_set_list" used to
		   keep track of such newly added states */
	        if (!exists) {
	   	   tmp = (LIST_ST_LIST *) malloc(sizeof(LIST_ST_LIST));	
		   tmp->st_list = stptr_list;
		   stptr_list = NULL;
		   strcpy(tmp->name, nxt_st);
		   tmp->next = NULL;
		   *anchor = tmp;
		   anchor = &tmp->next;
		}

		/* if the state already exists in fsm2, it need not
		   be added to "state_set_list" and the storage
		   used of the list of states can be freed */
		else {
		   while (stptr_list) {
		      ptr2 = stptr_list->next;
		      free(stptr_list);
		      stptr_list = ptr2;
		   }
		   stptr_list = NULL;
		}

		/* now insert the transition in fsm2 */
	 	insert_trans(fsm2_ptr, current2, this->input,
					 nxt_st);
	   }
	   /* process the next transition  of the current state */
	   this = this->next;
	 }
	 /* process the next state of the current list of states */
	 ptr1 = ptr1->next;
      }
      /* process the next entry of the list of list of states */
      stlist_ptr = stlist_ptr->next;
   }

   /* now that state_set_list is no longer required, free the
      storage reserved for it */
   while (state_set_list) {

      /* first free the storage used by the linked list of states */
      ptr1 = state_set_list->st_list;
      while (ptr1) {
	 ptr2 = ptr1->next;
	 free(ptr1);
	 ptr1 = ptr2;
      }

      /* now delete this entry of state_set_list */
      stlist_ptr = state_set_list->next;
      free(state_set_list);
      state_set_list = stlist_ptr;
   }
}


/* **************************************************************
   Function : fsm_complement

   This function complements a given state machine.  This means
   that the language accepted by the new state machine will be
   the complement of the language accepted by the original state
   machine.

   Arguments: fsm_ptr - pointer to the original state machine

   Return Type : void 

   ************************************************************** */

void fsm_complement(fsm_ptr)
FSM *fsm_ptr;
{
   ST_LIST *current, *exists;
   TR_LIST *this;
   TRANS_LIST *list = NULL, *list_ptr;
   char new_name[4];
   BOOLEAN name_found;

   if (!fsm_ptr)
	prog_abort("fsm_complement : NULL pointer passed as argument for (FSM *)");

   /* first determine the input alphabet (sigma) of the given
      state machine */
   fsm_find_sigma(fsm_ptr, &list);

   /* Now step through each state and see if it allows all the 
      transitions in the input alphabet sigma.  If not, then insert 
      transitions which were previously not allowed in this state.
      All these transitions lead to the "dead" state */

   /* first generate a unique name for the dead state */
   strcpy(new_name, "a00");
   name_found = FALSE;

   while (!name_found) {
      exists = find_state(fsm_ptr, new_name);

      /* if a state with this name already exists, generate another
         name - upto a maximum of 2600 names */
      if (exists) {

         /* first increment the units digit, if it is not 9 */
         if (new_name[2] != '9') 
             ++new_name[2];
      
            /* if the units digit is 9, but the tens digit is not, set
               the units digit to 0 and increment the tens digit */
            else if (new_name[1] != '9') {
	       new_name[2] = '0';
	       ++new_name[1];
            }

            /* if both the units and tens digit are 9s, but the 
               hundreds digit (alphabet) is not z, set the units and 
               tens digits to zeros and set the hundreds digit to the 
               next alphabet */
            else if (new_name[0] != 'z') {
	       new_name[2] = new_name[1] = '0'; 
	       ++new_name[0];
            }

            /* if reached "z99", you cannot go any further */
            else
	       prog_abort("fsm_complement: cannot generate unique name for state");
      }

      else 
	 name_found = TRUE;
   }

   current = fsm_ptr->states;
   while (current) {        /* step through each state */
      list_ptr = list;
      /* step through each entry of the linked list of input 
         symbols to check if this transition is allowed in the
         current state */
      while (list_ptr) {
	 this = current->trans;
         while (this) {
            /* if the transition exists, no need to step further */
	    if (strcmp(this->input, list_ptr->input) == 0) break;
	    this = this->next;
         }
         
         /* if the transition does not exist, insert it and make
            it lead to the "dead" state */
	 if (!this)
	    insert_trans(fsm_ptr, current, list_ptr->input, 
			          new_name);
	 list_ptr = list_ptr->next;
      }

      /* if the current state is marked, it becomes unmarked in the
         complement macnine and vice-versa */
      current->marked = !current->marked;
      current = current->next;
   }

   /* check if the "dead" state was inserted - the only case in 
      which it would not have been inserted is when every state of
      the original state machine allowed all the transitions */
   current = find_state(fsm_ptr, new_name);

   /* if the dead state has been inserted, check if all the
      transitions have been inserted in this state */
   if (current) {

      /* the dead state is always marked */
      current->marked = MKD;

      if (!current->trans) {

         /* transitions have not been inserted in the "dead" state
            so insert all transitions */
	 list_ptr = list;
	 while (list_ptr) {
	    insert_trans(fsm_ptr, current, list_ptr->input, 
				  new_name);
	    list_ptr = list_ptr->next;
         }
      }
   }
}


/* **************************************************************
   Function : multiplefile_complete_fsm_sync_comp
   
   This function constructs a state machine which is the 
   synchronous composition of two given state machines.
   The resultant state machine accepts the language which is
   the intersection of the languages accepted by the two input  
   state machines.

   Arguments : 
		fp1 - file pointer to the file containing the input 
			 names files for the  sync comp operation 
		
		fsm_ptr3 - file pointer to the file containing the
		   	 resultant fsm after the  sync comp operation 
   
   Return Type : void

   ************************************************************** */

void multiplefile_complete_fsm_sync_comp( fp1, fsm_ptr3 )

FILE *fp1 ;
FSM  *fsm_ptr3 ;

{

	FSM fsm_ptr1,  fsm_ptr2 ;
	FILE *f1, *f2 ; 
	char file_line_string[100] ;
	char input_file_scrolling[200] ;
	char input_file[200] ;

	while(1){
	    /*Read in first file name after removing leading blank lines or space*/
		if( fgets(file_line_string, sizeof(file_line_string), fp1) != NULL ){  
			file_line_string[strlen(file_line_string) - 1]  = '\0';
	    	/*check for blank line being */
			if( strcmp(file_line_string, "") == 0) {
				continue;
			}
			else{
				/*leading blank space before the %s handles any white space*/
				sscanf(file_line_string," %s", input_file_scrolling) ;
				strcpy(input_file, input_file_scrolling) ;
				/*this array now houses the first file name being opened */
				f1 = fopen( input_file ,"r");  
				fsm_read(f1, &fsm_ptr1) ;
				break;	
			}
		}
		else
			prog_abort("Multiple synch. operation: No data in file list");	
	}
	
	while(1){	
	    /*Read in second file name after removing leading blank lines or space*/
		if(fgets(file_line_string, sizeof(file_line_string), fp1) != NULL){ 
			file_line_string[strlen(file_line_string) - 1]  = '\0';
			if( strcmp(file_line_string, "") == 0) {
				continue;
			}
			else{
				sscanf(file_line_string," %s", input_file_scrolling) ;
				strcpy(input_file, input_file_scrolling) ;
				/*the array houses the second file name being opened now*/
				f1 = fopen( input_file ,"r");  
				fsm_read(f1, &fsm_ptr2) ;
				break;
			}
		}
		else
			prog_abort("Multiple synch. operation: Only 1 file in file list");	

	}


	/*	Perform the complete sync operation 		*/
	complete_fsm_sync_comp(&fsm_ptr1, &fsm_ptr2, fsm_ptr3) ;
	f2 = fopen( "output_file.temp" ,"w+");  
	/*writing the temporary / final result to file*/
	fsm_print(f2, fsm_ptr3) ;
	/*read-writes on same file should alternate with rewind or flush operation*/
	rewind(f2);
	fsm_read(f2, &fsm_ptr2) ;

	/*	Reading in additonal files from list until end of list encountered*/
	while (fgets(file_line_string, sizeof(file_line_string), fp1) != NULL){ 
		file_line_string[strlen(file_line_string) - 1]  = '\0';
		if( strcmp(file_line_string, "") == 0) {
			continue;
		}
		else{
			sscanf(file_line_string," %s", input_file_scrolling) ;
			strcpy(input_file, input_file_scrolling) ;
			f1 = fopen( input_file ,"r");  
			fsm_read(f1, &fsm_ptr1) ;
		}	
		complete_fsm_sync_comp(&fsm_ptr1, &fsm_ptr2, fsm_ptr3) ;
		f2 = fopen( "output_file.temp" ,"w+");  
		fsm_print(f2, fsm_ptr3) ;
		rewind(f2);
		fsm_read(f2, &fsm_ptr2) ;
	
	}
	

	fclose(f1);
	fclose(f2); 
	unlink("output_file.temp"); /*Greg ADDED delete temp file*/
	fsm_delete(&fsm_ptr1);
	fsm_delete(&fsm_ptr2);

}


/* **************************************************************
   Function : complete_fsm_sync_comp
	VC
   This function constructs a state machine which is the 
   non-strict synchronous composition of two given state machines.
   The resultant state machine accepts the language which is
   the intersection of the languages accepted by the two input  
   state machines.


   Arguments : fsm1_ptr - pointer to the first state machine
               fsm2_ptr - pointer to the second state machine
               fsm3_ptr - pointer to the resultant state machine


   Return Type : void

   ************************************************************** */

void complete_fsm_sync_comp(fsm1_ptr, fsm2_ptr, fsm3_ptr)
FSM *fsm1_ptr, *fsm2_ptr, *fsm3_ptr;
{
	FILE *f3, *f4, *f5, *f6;
	f3 = fopen("alpha_I-II.temp", "w+");
	f4 = fopen("alpha_II-I.temp", "w+");
	f5 = fopen("scc1_pad.temp", "w+");
	f6 = fopen("scc2_pad.temp", "w+");

	exclusive_events(fsm1_ptr, fsm2_ptr, f3);
	exclusive_events(fsm2_ptr, fsm1_ptr, f4);
	
	rewind(f3);
	rewind(f4) ;

	/* Events in only second mc augmented on first fsm              */
	 
	AugmentFsm(f4, fsm1_ptr);
	fsm_print(f5, fsm1_ptr);
			
			 
	/* Events in only first mc augmented on second fsm              */
				  
	AugmentFsm(f3, fsm2_ptr);
	fsm_print(f6, fsm2_ptr);
						 
	rewind(f5);
	rewind(f6) ;
								
	fsm_sync_comp(fsm1_ptr, fsm2_ptr, fsm3_ptr); 

	fclose(f3);
	fclose(f4);
	fclose(f5);
	fclose(f6);
	unlink("alpha_I-II.temp"); /*Greg ADDED del temp files*/
	unlink("alpha_II-I.temp");
	unlink("scc1_pad.temp");
	unlink("scc2_pad.temp");

}


/* **************************************************************
   Function : fsm_sync_comp

   This function constructs a state machine which is the 
   synchronous composition of two given state machines.
   The resultant state machine accepts the language which is
   the intersection of the languages accepted by the two input  
   state machines.

   Arguments : fsm1_ptr - pointer to the first state machine
               fsm2_ptr - pointer to the second state machine
               fsm3_ptr - pointer to the resultant state machine

   Return Type : void

   ************************************************************** */

void fsm_sync_comp(fsm1_ptr, fsm2_ptr, fsm3_ptr)
FSM *fsm1_ptr, *fsm2_ptr, *fsm3_ptr;
{
   char name[MAX_LENGTH];
   ST_LIST *st1, *st2, *st3, *tmp;
   TR_LIST *tr1, *tr2, *tmptr1,*tmptr2;
   EQUIV_LIST *list = NULL, *current_pair;
	int epstran1 = 0, epstran2 = 0; /*keep track of epsilon transitions*/	

   if (!fsm1_ptr || !fsm2_ptr || !fsm3_ptr)
	prog_abort("fsm_sync_comp : NULL pointer passed as argument for (FSM *)");

   /* initialize pointers to point to the first state of each
      of the two input state machines */
   st1 = fsm1_ptr->states;  st2 = fsm2_ptr->states;

   /* insert the initial state of the resultant state machine
      which is a concatenation of the initial states of the
      two input state machines */
   strcpy(name, st1->name);
   strcat(name, ","); /*add comma between state names*/

   /* check if the concatenation will result in a string which is
      of length greater than the maximum allowed */
   if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
      prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

   strcat(name, st2->name);
   fsm3_ptr->states = alloc_state;
   /*fsm3_ptr->states->name = (char *) malloc(strlen(name) + 1);/*now static memory*/
   strcpy(fsm3_ptr->states->name, name);
   fsm3_ptr->states->marked = st1->marked && st2->marked;
   
   /* no other states in this machine as yet */
   fsm3_ptr->states->next = NULL;
 
   /* no transitions in this state as yet */
   fsm3_ptr->states->trans = NULL;

   /* keep a list of the states inserted in the resultant
      state machine */
   insert_pair(&list, st1, st2);

   /* Start from this initial state of the resultant state 
      machine and see if any other states need to be inserted
      in the synchronous composition state machine.  If such states 
      are found, they are also inserted in the resultant state 
      machine and then checked to see if they lead to other states 
      which need to be included.  The routine ends when all the 
      candidate states have been processed and at that time, the 
      machine fsm3 contains the synchronous composition of fsm1 
      and fsm2 */

   current_pair = list;
   while (current_pair) {
      st1 = current_pair->first;   
      st2 = current_pair->second;  /* the two states of the pair */
      tr1 = st1->trans;
      tr2 = st2->trans;    /* transitions allowed from these states */
      st3 = NULL;

      while (tr1) {
         while (tr2) {


            /* Handle epsilon transitions in the first state machine*/
	    
			 if (*(tr1->input) == '*')
			 {
				
				 /* first get a pointer to the current state in fsm3 */
	       
				if (!st3) 
				{
					strcpy(name, st1->name);
					strcat(name, ",");
					/* first check if the length of the string exceeds the
						maximum allowed */
					if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
						prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

					strcat(name, st2->name);
	 				st3 = find_state(fsm3_ptr, name);
				}

					/* Determine the name of the state which is the 
						resultant state for this transition in fsm3. 
						It is the concatenation of the names of the 
						resultant states in fsm1 and fsm2 */
				strcpy(name, tr1->next_state->name);
				strcat(name, ",");
				/* check length of string */
				if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
					prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

				strcat(name, st2->name);

				/* insert this state in fsm3 */
				tmp = insert_state(fsm3_ptr, name);
				tmp->marked = tr1->next_state->marked && st2->marked;

				/* insert the transition from the current state to the new state */
				insert_trans(fsm3_ptr, st3, tr1->input, name);

				/* since a new state has been inserted in the resultant
					state machine, insert the corresponding pair in the
					linked list used to keep track of the various states
					of the resultant state machine */
				insert_pair(&list, tr1->next_state, st2);
				 
	       /*break;*/
	    }


   
   
   /* Handle epsilon transitions in the second state machine*/
	    
			 if (*(tr2->input) == '*')
			 {
				 
				 /* first get a pointer to the current state in fsm3 */
	       
				if (!st3) 
				{
					strcpy(name, st1->name);
					strcat(name, ",");
					/* first check if the length of the string exceeds the
						maximum allowed */
					if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
						prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

					strcat(name, st2->name);
	 				st3 = find_state(fsm3_ptr, name);
				}

					/* Determine the name of the state which is the 
						resultant state for this transition in fsm3. 
						It is the concatenation of the names of the 
						resultant states in fsm1 and fsm2 */
				strcpy(name, st1->name);
				strcat(name, ",");
				/* check length of string */
				if (strlen(name) + strlen(tr2->next_state->name) >= MAX_LENGTH)
					prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

				strcat(name, tr2->next_state->name);

				/* insert this state in fsm3 */
				tmp = insert_state(fsm3_ptr, name);
				tmp->marked = st1->marked && tr2->next_state->marked;

				/* insert the transition from the current state to the new state */
				insert_trans(fsm3_ptr, st3, tr2->input, name);

				/* since a new state has been inserted in the resultant
					state machine, insert the corresponding pair in the
					linked list used to keep track of the various states
					of the resultant state machine */
				insert_pair(&list, st1, tr2->next_state);

				

	       /*break;*/
	    }

		/*add transition when both states have the same transition*/

	    if ((strcmp(tr1->input, tr2->input) == 0) && *(tr1->input) !='*' && *(tr2->input) !='*') {
		epstran1 = epstran2 = 0;
               /* first get a pointer to the current state in fsm3 */
	       if (!st3) {
		 strcpy(name, st1->name);
		 strcat(name, ",");
		 /* first check if the length of the string exceeds the
		    maximum allowed */
		 if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
		    prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

		 strcat(name, st2->name);
	 	 st3 = find_state(fsm3_ptr, name);
	       }

               /* Determine the name of the state which is the 
                  resultant state for this transition in fsm3. 
                  It is the concatenation of the names of the 
		  resultant states in fsm1 and fsm2 */
	       strcpy(name, tr1->next_state->name);
		   strcat(name, ",");
	       /* check length of string */
	       if (strlen(name) + strlen(tr2->next_state->name) 
							>= MAX_LENGTH)
		  prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

	       strcat(name, tr2->next_state->name);

               /* insert this state in fsm3 */
	       tmp = insert_state(fsm3_ptr, name);
	       tmp->marked = tr1->next_state->marked &&
					tr2->next_state->marked;

               /* insert the transition from the current state to
                  the new state */
	       insert_trans(fsm3_ptr, st3, tr1->input, name);

               /* since a new state has been inserted in the resultant
                  state machine, insert the corresponding pair in the
                  linked list used to keep track of the various states
                  of the resultant state machine */
	       insert_pair(&list, tr1->next_state, tr2->next_state);

	       /*break;*/
	    }

            /* compare current transition of st1 with all 
               transitions of st2*/ 
			tr2 = tr2->next;
		}           	
         /* check all transitions of the current pair of states  */

		tr1 = tr1->next;
		tr2 = st2->trans;
      }

      /* check all the pairs of states */ 
      current_pair = current_pair->next;
   }
    	


/*repeat1*/
current_pair = list;
   while (current_pair) {
      st1 = current_pair->first;   
      st2 = current_pair->second;  /* the two states of the pair */
      tr1 = st1->trans;
      tr2 = st2->trans;    /* transitions allowed from these states */
      st3 = NULL;


	  while(tr1){

            /* Handle epsilon transitions in the first state machine*/
	    
			 if (*(tr1->input) == '*')
			 {
				
				 /* first get a pointer to the current state in fsm3 */
	       
				if (!st3) 
				{
					strcpy(name, st1->name);
					strcat(name, ",");
					/* first check if the length of the string exceeds the
						maximum allowed */
					if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
						prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

					strcat(name, st2->name);
	 				st3 = find_state(fsm3_ptr, name);
				}

					/* Determine the name of the state which is the 
						resultant state for this transition in fsm3. 
						It is the concatenation of the names of the 
						resultant states in fsm1 and fsm2 */
				strcpy(name, tr1->next_state->name);
				strcat(name, ",");
				/* check length of string */
				if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
					prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

				strcat(name, st2->name);

				/* insert this state in fsm3 */
				tmp = insert_state(fsm3_ptr, name);
				tmp->marked = tr1->next_state->marked && st2->marked;

				/* insert the transition from the current state to the new state */
				insert_trans(fsm3_ptr, st3, tr1->input, name);

				/* since a new state has been inserted in the resultant
					state machine, insert the corresponding pair in the
					linked list used to keep track of the various states
					of the resultant state machine */
				insert_pair(&list, tr1->next_state, st2);
				 
	       /*break;*/
	    }

			tr1 = tr1->next;

}

current_pair = current_pair->next;
}


/*repeat2*/
current_pair = list;
   while (current_pair) {
      st1 = current_pair->first;   
      st2 = current_pair->second;  /* the two states of the pair */
      tr1 = st1->trans;
      tr2 = st2->trans;    /* transitions allowed from these states */
      st3 = NULL;


	  while(tr2){

   /* Handle epsilon transitions in the second state machine*/
	    
			 if (*(tr2->input) == '*')
			 {
				 
				 /* first get a pointer to the current state in fsm3 */
	       
				if (!st3) 
				{
					strcpy(name, st1->name);
					strcat(name, ",");
					/* first check if the length of the string exceeds the
						maximum allowed */
					if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
						prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

					strcat(name, st2->name);
	 				st3 = find_state(fsm3_ptr, name);
				}

					/* Determine the name of the state which is the 
						resultant state for this transition in fsm3. 
						It is the concatenation of the names of the 
						resultant states in fsm1 and fsm2 */
				strcpy(name, st1->name);
				strcat(name, ",");
				/* check length of string */
				if (strlen(name) + strlen(tr2->next_state->name) >= MAX_LENGTH)
					prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

				strcat(name, tr2->next_state->name);

				/* insert this state in fsm3 */
				tmp = insert_state(fsm3_ptr, name);
				tmp->marked = st1->marked && tr2->next_state->marked;

				/* insert the transition from the current state to the new state */
				insert_trans(fsm3_ptr, st3, tr2->input, name);

				/* since a new state has been inserted in the resultant
					state machine, insert the corresponding pair in the
					linked list used to keep track of the various states
					of the resultant state machine */
				insert_pair(&list, st1, tr2->next_state);

				

	       /*break;*/
	    }

			tr2 = tr2->next;

}

current_pair = current_pair->next;
}

   /* free the storage used to store the linked list of pairs 
      of states */
   while (list) {
      current_pair = list->next;
      free (list);
      list = current_pair;
   }
}


/* *************************************************************
   Function : fsm_union

   This function generates a state machine which accepts the
   union of the languages accepted by the two input state
   machines

   Arguments : fsm1_ptr - pointer to first input state machine
	       fsm2_ptr - pointer to second input state machine
	       fsm3_ptr - pointer to the resultant machine

   Return Type : void

   ************************************************************* */

void fsm_union(fsm1_ptr, fsm2_ptr, fsm3_ptr)
FSM *fsm1_ptr, *fsm2_ptr, *fsm3_ptr;
{
   ST_LIST *current, *st_ptr, *tmp, *exists;
   TR_LIST *this;
   FSM fsm_tmp;
   BOOLEAN found, name_found;
   char new_name[4];

   if (!fsm1_ptr || !fsm2_ptr || !fsm3_ptr)
	prog_abort("fsm_union : NULL pointer passed as argument for (FSM *)");

   /* first copy fsm1 into fsm3 */
   fsm_copy(fsm1_ptr, fsm3_ptr);

   /* Now copy fsm2 into fsm3 - note that after this all the states of
      both fsm1 and fsm2 will be present in fsm3. The function fsm_copy
      cannot be used because that will result in only the states of 
      fsm2 being copied into fsm3  */
   current = fsm2_ptr->states;
   while (current) {
    
      /* insert current state of fsm2 in fsm3 */
      st_ptr = insert_state(fsm3_ptr, current->name);
      st_ptr->marked = current->marked;

      /* insert all the transitions of the current state of fsm2 in
         the corresponding state of fsm3 */
      this = current->trans;
      while (this) {
	 insert_trans(fsm3_ptr, st_ptr, this->input,
					      this->next_state->name);
	 this = this->next;
      }
      current = current->next;
   }

   /* now insert a new initial state for fsm3 */
   tmp = alloc_state;

   /* generate a unique name for this new state */
   strcpy(new_name, "a00");
   name_found = FALSE;

   while (!name_found) {
      exists = find_state(fsm3_ptr, new_name);

      /* if a state with this name already exists, generate another
         name - upto a maximum of 2600 names */
      if (exists) {

         /* first increment the units digit, if it is not 9 */
         if (new_name[2] != '9') 
             ++new_name[2];
      
            /* if the units digit is 9, but the tens digit is not, set
               the units digit to 0 and increment the tens digit */
            else if (new_name[1] != '9') {
	       new_name[2] = '0';
	       ++new_name[1];
            }

            /* if both the units and tens digit are 9s, but the 
               hundreds digit (alphabet) is not z, set the units and 
               tens digits to zeros and set the hundreds digit to the 
               next alphabet */
            else if (new_name[0] != 'z') {
	       new_name[2] = new_name[1] = '0'; 
	       ++new_name[0];
            }

            /* if reached "z99", you cannot go any further */
            else
	       prog_abort("fsm_rename : cannot generate unique name for state");
      }

      else {
         /*tmp->name = (char *) malloc(4);/*now static memory*/
	 strcpy(tmp->name, new_name); 
	 name_found = TRUE;
      }
   }

   /* now set the other fields of the new state */
   tmp->marked = UNMKD;
   tmp->trans = NULL;
   tmp->next = fsm3_ptr->states;
   fsm3_ptr->states = tmp;

   /* insert two epsilon transition is this initial state, one
      each leading to the initial states of fsm1 and fsm2
      respectively */
   insert_trans(fsm3_ptr, tmp, "*", fsm1_ptr->states->name);
   insert_trans(fsm3_ptr, tmp, "*", fsm2_ptr->states->name);

   /* now convert the existing fsm3 into an equivalent machine
      which does not have any epsilon transitions and is 
      deterministic */
   fsm_remove_epsilon(fsm3_ptr, &fsm_tmp);
   fsm_delete(fsm3_ptr);
   fsm_deterministic(&fsm_tmp, fsm3_ptr);
   fsm_delete(&fsm_tmp);
}


/* *************************************************************
   Function : fsm_concatenate

   This function generates a state machine which accepts a
   language which is the concatenation of the languages accepted
   by the two input state machines.

   Arguments : fsm1_ptr - pointer to the first input state machine
	       fsm2_ptr - pointer to the second input machine
	       fsm3_ptr - pointer to the resultant output machine

   Return Type : void
 
   ************************************************************** */

void fsm_concatenate(fsm1_ptr, fsm2_ptr, fsm3_ptr)
FSM *fsm1_ptr, *fsm2_ptr, *fsm3_ptr;
{
   ST_LIST *tmp, *current;
   TR_LIST *this;
   FSM fsm_tmp;

   if (!fsm1_ptr || !fsm2_ptr || !fsm3_ptr)
	prog_abort("fsm_concatenate : NULL pointer passed as argument of (FSM *)");

   /* first coppy fsm2 into fsm3 */
   fsm_copy(fsm2_ptr, fsm3_ptr);

   /* now insert the initial state of fsm1 as the initial state
      of fsm3 */
   tmp = alloc_state;
   /*tmp->name = (char *) malloc(strlen(fsm1_ptr->states->name) + 1);/*now static memory*/
   strcpy(tmp->name, fsm1_ptr->states->name);
   tmp->marked = UNMKD;
   tmp->trans = NULL;
   tmp->next = fsm3_ptr->states;
   fsm3_ptr->states = tmp;

   /* insert all the transitions of the initial state of fsm1 into
      this newly inserted state of fsm3 */
   this = fsm1_ptr->states->trans;
   while (this) {
      insert_trans(fsm3_ptr, tmp, this->input, 
						this->next_state->name);
      this = this->next;
   }

   /* if this state of fsm1 is marked, insert an epsilon transition
      from the corresponding state of fsm3 to the initial state 
      of fsm2 */
   if (fsm1_ptr->states->marked)
      insert_trans(fsm3_ptr, tmp, "*", fsm2_ptr->states->name);

   /* now insert the remaining states of fsm1 into fsm3 in a similar
      fashion
      the first state was treated separately because it was to be
      added as the initial state of fsm3 */
   current = fsm1_ptr->states->next;
   while (current) {
      tmp = insert_state(fsm3_ptr, current->name);
      tmp->marked = UNMKD;
      this = current->trans;
      while (this) {
	 insert_trans(fsm3_ptr, tmp, this->input,
						this->next_state->name);
	 this = this->next;
      }

      if (current->marked)
	 insert_trans(fsm3_ptr, tmp, "*", fsm2_ptr->states->name);
      
      current = current->next;
   }

   /* now convert fsm3 into an equivalent machine which does not
      have epsilon transitions and is deterministic */
   fsm_remove_epsilon(fsm3_ptr, &fsm_tmp);
   fsm_delete(fsm3_ptr);
   fsm_deterministic(&fsm_tmp, fsm3_ptr);
   fsm_delete(&fsm_tmp);
}


/* ************************************************************
   Function : fsm_shuffle

   This function finds the shuffle product/asynchronous
   composition of two finite state machines

   Arguments : fsm1_ptr - pointer to first state machine
               fsm2_ptr - pointer to second state machine
               fsm3_ptr - pointer to the resultant state
                          machine

   Return Type : void

   ************************************************************ */

void fsm_shuffle(fsm1_ptr, fsm2_ptr, fsm3_ptr)
FSM *fsm1_ptr, *fsm2_ptr, *fsm3_ptr;
{
   char name[MAX_LENGTH], nxt_st[MAX_LENGTH];
   ST_LIST *st1, *st2, *st3;
   TR_LIST *tr1, *tr2;

   if (!fsm1_ptr || !fsm2_ptr || !fsm3_ptr)
      prog_abort("fsm_shuffle : NULL pointer passed as argument for (FSM *)");

   /* ensure that fsm3 is empty */
   fsm3_ptr->states = NULL;

   /* initialize pointers to the first states of the two
      input state machines */
   st1 = fsm1_ptr->states; st2 = fsm2_ptr->states;

   /* step through the states of fsm1 and fsm2 and insert states
      in fsm3 which correspond to the concatenation of all the 
      states of fsm1 with all the states of fsm2 */
   while (st1) {  /* for each state of machine 1 */
      while (st2) {  /* for each state of machine 2 */

         /* add a state to state machine 3 with name
            st1->name concatenated with st2->name */
	 strcpy(name, st1->name);

	 /* check length of the string */
	 if (strlen(name) + strlen(st2->name) >= MAX_LENGTH)
	    prog_abort("fsm_shuffle : length of string exceeds MAX_LENGTH");

         strcat(name, st2->name);
	 st3 = insert_state(fsm3_ptr, name);

	 /* the new state is marked if either one of the component
	    states is marked */
	 st3->marked = st1->marked || st2->marked;

         /* initialize pointers to the first transitions of
	    the states of st1 and st2 */
	 tr1 = st1->trans; tr2 = st2->trans;
	 while (tr2) {  /* for each transition of st2 */

            /* Insert a transition in st3 with the same name as the 
               transition of st2.  The resultant state of this 
               transition is a state with name st1->name concatenated 
               with tr2->next_state->name */
            strcpy(nxt_st, st1->name);

	    /* check length of string */
	    if (strlen(nxt_st) + strlen(tr2->next_state->name) 
							>= MAX_LENGTH)
		prog_abort("fsm_shuffle : length of string exceeds MAX_LENGTH");

	    strcat(nxt_st, tr2->next_state->name);
	    insert_trans(fsm3_ptr, st3, tr2->input, nxt_st);
	    tr2 = tr2->next;
         }

         while (tr1) {  /* for each transition of of st1 */

            /* Insert a transition in st3 with the same name as the 
               transition of st1.  The resultant state of this 
               transition is a state with name tr1->next_state->name 
               concatenated with st2->name */
	    strcpy(nxt_st, tr1->next_state->name);

	    /* check for length of the string */
	    if (strlen(nxt_st) + strlen(st2->name) >= MAX_LENGTH)
		prog_abort("fsm_shuffle : length of string exceeds MAX_LENGTH");

	    strcat(nxt_st, st2->name);
	    insert_trans(fsm3_ptr, st3, tr1->input, nxt_st);
	    tr1 = tr1->next;
	 }

         /* repeat for all the states of fsm2 */
	 st2 = st2->next;
      }

      /* repeat for all the states of fsm1 */
      st1 = st1->next;
      st2 = fsm2_ptr->states;
   }
}


/* ***************************************************************
   Function : fsm_quotient

   This function computes the quotient of the two input state 
   machines i.e. it generates a state machine which accepts the
   language which is the quotient of the languages accepted by the
   two input state machines.

   Arguments : fsm1_ptr - pointer to first input state machine
	       fsm2_ptr - pointer to second input state machine
	       fsm3_ptr - pointer to the output state machine

   Return Type : void

   *************************************************************** */

void fsm_quotient(fsm1_ptr, fsm2_ptr, fsm3_ptr)
FSM *fsm1_ptr, *fsm2_ptr, *fsm3_ptr;
{
   ST_LIST *current, *st_ptr, *st1, *st2, *st3, *tmp;
   TR_LIST *this, *tr1, *tr2;
   char name[MAX_LENGTH];
   EQUIV_LIST *list = NULL, *current_pair, *next_pair;
   NAME_LIST *name_list = NULL, *name_ptr;
   FSM fsm_tmp, fsm_tmp_inverse;
   int exists;

   if (!fsm1_ptr || !fsm2_ptr || !fsm3_ptr)
	prog_abort("fsm_quotient : NULL pointer passed as argument for (FSM *)");

   /* first ensure that the temporary fsm's defined in this function
      are empty */
   fsm_tmp.states = fsm_tmp_inverse.states = fsm3_ptr->states = NULL;
 
   /* The quotient of fsm1 and fsm2 is a machine similar to fsm1 but 
      with a different marking.  Hence, first copy fsm1 into fsm3 and
      make all states of fsm3 as unmarked. */
   fsm_copy(fsm1_ptr, fsm3_ptr);

   current = fsm3_ptr->states;
   while (current) {
      current->marked = UNMKD;  /* all states of fsm3 unmarked */
      current = current->next;
   }

   /* We want to take the synchronous composition of fsm1 with fsm2, but 
      a slightly modified manner.  Instead of starting with the initial
      state of fsm1 and fsm2, we would like to start with all states of
      fsm1 combined with the initial states of fsm2.  This gives us one
      big synchronous composition machine.  Starting with this is more
      optimal than taking `n' different synchronous compositions, one 
      with each of the initial states of fsm1. To do this, combine the
      initial state of fsm2 with each of the initial states of fsm1 */

   current = fsm1_ptr->states;
   while (current) {
      strcpy(name, current->name);
      if (strlen(name) + strlen(fsm2_ptr->states->name) >= MAX_LENGTH)
	 prog_abort("fsm_quotient : length of string exceeds MAX_LENGTH");

      strcat(name, fsm2_ptr->states->name);

      /* concatenation of the current state of fsm1 and the initial state
         of fsm2 is inserted as a state of fsm_tmp */
      st_ptr = insert_state(&fsm_tmp, name);
      st_ptr->marked = current->marked && fsm2_ptr->states->marked;

      /* This state is stored in the list of states of fsm_tmp.  The
         list is used to check if al the states of fsm_tmp have been
         processed and its function is similar to the list used in the
         fsm_sync_comp routine.  */
      insert_pair(&list, current, fsm2_ptr->states);

      current = current->next;
   }

   /* Now that all the "initial" states have been identified, we step 
      through the list of these states to see if any new states have
      to be added to the synchronous composition states machine.  This
      part of the code is again similar to the fsm_sync_comp routine.  */
   current_pair = list;
   while (current_pair) {
      st1 = current_pair->first;   
      st2 = current_pair->second;  /* the two states of the pair */
      tr1 = st1->trans;
      tr2 = st2->trans;    /* transitions allowed from these states */
      st3 = NULL;

      while (tr1) {
         while (tr2) {

            /* if the a particular transition is allowed in the 
               corresponding states of both fsm1 and fsm2 then the
               transition is allowed in the composite state of 
	       fsm_tmp */

	    if (strcmp(tr1->input, tr2->input) == 0) {

               /* first get a pointer to the current state in fsm_tmp */
	       if (!st3) {
		 strcpy(name, st1->name);
		 strcat(name, st2->name);
	 	 st3 = find_state(&fsm_tmp, name);
	       }

               /* Determine the name of the state which is the 
                  resultant state for this transition in fsm_tmp  
                  It is the concatenation of the names of the resultant
		  states in fsm1 and fsm2 */
	       strcpy(name, tr1->next_state->name);

	       /* check length of string */
	       if (strlen(name) + strlen(tr2->next_state->name) 
							>= MAX_LENGTH)
		  prog_abort("fsm_sync_comp : length of string exceeds MAX_LENGTH");

	       strcat(name, tr2->next_state->name);

               /* insert this state in fsm3 */
	       tmp = insert_state(&fsm_tmp, name);
	       tmp->marked = tr1->next_state->marked &&
					tr2->next_state->marked;

               /* insert the transition from the current state to
                  the new state */
	       insert_trans(&fsm_tmp, st3, tr1->input, name);

               /* since a new state has been inserted in the resultant
                  state machine, insert the corresponding pair in the
                  linked list used to keep track of the various states
                  of the resultant state machine */
	       insert_pair(&list, tr1->next_state, tr2->next_state);

	       break;
	    }

            /* compare current transition of st1 with all 
               transitions of st2 */ 
	    tr2 = tr2->next;
         }           	

         /* check all transitions of the current pair of states  */
	 tr1 = tr1->next;
	 tr2 = st2->trans;
      }

      /* check all the pairs of states */ 
      current_pair = current_pair->next;
   }

   /* Generate the inverse of fsm_tmp.  If there is a transition 
      labeled `a' in fsm_tmp from state `q' to state `p', then there 
      is a transition labeled `a' from state `p' to state `q' in 
      its inverse */

   /* step through all the states of fsm_tmp */
   current = fsm_tmp.states;
   while (current) {

      /* insert the current state in fsm_tmp_inverse */
      st1 = insert_state(&fsm_tmp_inverse, current->name);
      st1->marked = current->marked;

      /* step through the transitions of the current state of fsm_tmp */
      this = current->trans;
      while (this) {

	 /* insert the inverse transition in fsm1_inverse */
	 st1 = insert_state(&fsm_tmp_inverse, this->next_state->name);
 	 insert_trans(&fsm_tmp_inverse, st1, this->input,
							current->name);
	 this = this->next;
      }

      current = current->next;
   }

   /* insert a new states called "dead" in the inverse machine */
   st_ptr = insert_state(&fsm_tmp_inverse, "dead");

   /* insert a epsilon transition from the "dead" state to every marked 
      state of fsm_tmp_inverse */
   current = fsm_tmp_inverse.states;
   while (current) {
      if (current->marked) 
	 insert_trans(&fsm_tmp_inverse, st_ptr, "*", 
							current->name);
      current = current->next;
   }

   /* now compute the set of states reachable from the "dead" state */
   fsm_reachability(&fsm_tmp_inverse, "dead", "ALL", &name_list);

   /* step through the list of states in the synchronous composition
      of fsm1 and fsm2 */
   while (list) { 

      /* remember pointer to the next entry of the list */
      next_pair = list->next;

      /* Check if this pair corresponds to one of the "initial" states 
         of the synchronous composition.  If the second state of the 
         pair is the initial state of fsm2, then this pair corresponds 
         to an initial state */
      if (list->second == fsm2_ptr->states) {

	 /* Determine the name of the corresponding initial state as
            the concatenation of the names of the two states forming
            this pair */
         strcpy(name, list->first->name);
         strcat(name, list->second->name);

         /* check if this initial state is in the list of states 
            reachable from the dead states */
         exists = find_name(name_list, name);

	 /* if it is, then the first state of the pair (which is a 
            state in fsm1 and fsm3) is marked in fsm3 */
         if (exists) {
	    st_ptr = find_state(fsm3_ptr, list->first->name);
	    st_ptr->marked = MKD;
         }
      }

      /* free the storage used to store this entry of the list */
      free(list);
      list = next_pair;
   }

   /* free the storage used to store the name list */
   delete_name(&name_list);

   /* free the storage used to store the temporary state machines */
   fsm_delete(&fsm_tmp);
   fsm_delete(&fsm_tmp_inverse);

   /* trim the resultant machine before returning it */
   fsm_trim(fsm3_ptr);
}


 /* **************************************************************
	Function : fsm_trim_sup_cont_sublang
		VC
	This function generates the supremal controllable sublanguage
	of a given language L with respect to a desired language K.
	The languages K and L are given as input in the form of state
	machines and the sup(K) language is also output in the form
	of a state machine.  It is required that both the languages
	L and K be closed.
				
	Arguments : fsm_L - pointer to state machine corresponding to L
	fsm_K - pointer to state machine corresponding to K
	fsm_LK - pointer to state machine in which the
	resultant state machine is output
	Return Type : void
 **************************************************************** */
void fsm_trim_sup_cont_sublang(fsm1_ptr, fsm2_ptr, fsm3_ptr, fpuncevents)
FSM *fsm1_ptr, *fsm2_ptr, *fsm3_ptr;
FILE *fpuncevents;
{

	fsm_sup_cont_sublang(fsm1_ptr, fsm2_ptr, fsm3_ptr, fpuncevents);
   
   /* trim the resultant machine before returning it */
   if(fsm3_ptr->states)
   fsm_trim(fsm3_ptr);

}


/* *****************************************************************
   Function : fsm_sup_cont_sublang
   This function generates the supremal controllable sublanguage
   of a given language L with respect to a desired language K.
   The languages K and L are given as input in the form of state
   machines and the sup(K) language is also output in the form
   of a state machine.  It is required that both the languages
   L and K be closed.

   Arguments : fsm_L - pointer to state machine corresponding to L
               fsm_K - pointer to state machine corresponding to K
               fsm_LK - pointer to state machine in which the 
                        resultant state machine is output

   Return Type : void

   **************************************************************** */

void fsm_sup_cont_sublang(fsmL, fsmK, fsmLK, fpuncevents)
FSM *fsmL, *fsmK, *fsmLK;
FILE *fpuncevents;
{
	FSM fsmKC, fsmLKC, fsmLKCcopy;
	ST_LIST *stateL, *st_ptr, *st_tomark, *stateLnext;
	TR_LIST *transitionL;
	char transnames[MAX_LENGTH];
	int	 transtypes[MAX_LENGTH], i, reachgood, num_states1, num_states2;
   	TRANS_LIST *listL = NULL;
	FILE *fpeventset, *fptmp2;
	NAME_LIST *name_list, *ptrname_list;

	/* generate a list of events from the plant */
	fpeventset = fopen("tmplist.out", "w+");

	fsm_find_sigma(fsmL, &listL); /*extract set of events from fsmL*/

	while(listL) /*create file to store event set*/
	{
		fprintf(fpeventset, "%s\n", listL->input); /* write events and controllable information */
		listL = listL->next;
	}
	
	fclose(fpeventset);

	fpeventset = fopen("tmplist.out", "r");

	fptmp2 = fopen("tmpfsm.out", "w+");
	
	/* complete spec with list of events */
	CompleteGraph(fpeventset, fsmK, &fsmKC);

	/* fsmLKC = sync. comp. of plant and completed specification */
	fsm_sync_comp(fsmL, &fsmKC, &fsmLKC);
	
      do{
	num_states1 = BadStates(&fsmLKC); /*looks for marked or dump*/
      
	/* do controllability check, mark bad states including dump state with "@$" */
	ControlCheck(&fsmLKC, fpuncevents);
      /*should split out some functionality, do not need to remark dump states*/
	
      /*count number of marked bad states*/
      /*num_states1 = 0;

	stateL = fsmLKC.states;
	while(stateL)
	{	
		if(strstr(stateL->name, "@$") != NULL)
			num_states1++;
	
		stateL = stateL->next;
	}
	num_states2 = num_states1;
      */

	/*stateL = fsmLKC.states;*/
      /*reduce state space to remaining good states*/
	fsm_copy(&fsmLKC, &fsmLKCcopy);
      stateL = fsmLKCcopy.states;
	while(stateL)
	{	
		if(strstr(stateL->name, "@$") != NULL)
			{
                 stateLnext = stateL->next; /*in case need to delete*/
                 delete_state(&fsmLKCcopy, stateL);
	           stateL = stateLnext;
                   }
		else
             stateL = stateL->next;
	}
	stateL = fsmLKCcopy.states;

	while(stateL)
	{	
		reachgood = 0;

			i = fsm_reachability(&fsmLKCcopy, stateL->name, "ALL", &name_list); /*reachability returns self too*/
					
			/* find if one of the states reached is marked*/
			ptrname_list = name_list;
			while(ptrname_list && !reachgood)
			{
                       st_ptr = find_state(&fsmLKCcopy, ptrname_list->name);
			     if(st_ptr->marked == MKD)
			          reachgood = 1;

				ptrname_list = ptrname_list->next;
			}
			if(!reachgood){	/* doesn't reach a good marked state, therefore mark state as bad */
				st_tomark = find_state(&fsmLKC, stateL->name);
                        MarkBadState(&fsmLKC, st_tomark);
                        /*num_states2++;*/ } /*marked another state as bad*/

            delete_name(&name_list);
		stateL = stateL->next;
	}
	fsm_delete(&fsmLKCcopy);
	num_states2 = BadStates(&fsmLKC);
	}while(num_states1 != num_states2); /* Continue until no more states are removed */

      /*remove states marked as bad*/
	stateL = fsmLKC.states;
	
	while(stateL)
	{	
		if(strstr(stateL->name, "@$") != NULL)
			{
                stateLnext = stateL->next; /*in case need to delete*/
                delete_state(&fsmLKC, stateL);
	          stateL = stateLnext;
                   }
            else
		stateL = stateL->next;
	}


	fsm_print(fptmp2, &fsmLKC);
	fclose(fptmp2);

	fptmp2 = fopen("tmpfsm.out", "r"); /*use fsm copy instead of temp file?*/
	fsm_read(fptmp2, fsmLK); /* result is stored to fsmLK (passed in function arg.) */
	
	fclose(fpeventset);
	/*fclose(fpuncevents); shouldn't close file being passed as argument, maybe closed later*/
	rewind(fpuncevents);
	fclose(fptmp2);

	/* remove generated temporary files*/
	unlink("tmplist.out");
	unlink("tmpfsm.out");

	/*delete fsm's, free lists...*/
	fsm_delete(&fsmKC);
      fsm_delete(&fsmLKC);
}


/* ***************************************************************
   Function : fsm_sup_norm_sublang

   This functions generates the supremal normal sublanguage of
   the language K with respect to another language L and mask M.

   Arguments - fp - file pointer containing information about
		    the mask M
	       fsmL - pointer to the state machine which is a
		      generator for L
	       fsmK - pointer to the state machine which is a
		      generator for K
	       fsmN - pointer to the resultant state machine

   Return Type : void

   ************************************************************** */

void fsm_sup_norm_sublang(fp, fsmL, fsmK, fsmN)
FILE *fp;
FSM *fsmL, *fsmK, *fsmN;
{
   FSM fsmK_comp, fsmLK, fsmLK_masked, fsmLK_tmp, fsmLK_det;
   char st1[MAX_LENGTH], st2[MAX_LENGTH];

   if (!fsmL || !fsmK || !fsmN)
	prog_abort("fsm_sup_norm_sublang : NULL pointer passed as argument for (FSM *)");

   /* Construct a generator for L - K.  This is done by taking the 
      synchronous composition of L with K complement */
   fsm_copy(fsmK, &fsmK_comp);
   fsm_complement(&fsmK_comp);
   fsm_sync_comp(fsmL, &fsmK_comp, &fsmLK);

   /* Now mask the FSM representing L - K */
   fsm_mask(fp, &fsmLK, &fsmLK_masked);
   fsm_delete(&fsmLK);

   /* Remove the epsilon transitions from the above machine and
      make it deterministic */
   fsm_remove_epsilon(&fsmLK_masked, &fsmLK_tmp);
   fsm_deterministic(&fsmLK_tmp, &fsmLK_det);

   /* Now unmask the machine */
   fsm_unmask(fp, &fsmLK_det, &fsmLK);

   /* Now construct the generator for K - LK */
   fsm_complement(&fsmLK);
   fsm_sync_comp(fsmK, &fsmLK, fsmN);

   /* free the storage used for storing the temporary state machines */
   fsm_delete(&fsmK_comp);
   fsm_delete(&fsmLK);
   fsm_delete(&fsmLK_masked);
   fsm_delete(&fsmLK_tmp);
   fsm_delete(&fsmLK_det);
}

/* ***************************************************************
   Function : fsm_sup_cont_norm_sublang

   This functions generates the supremal controllable and normal 
   sublanguage of the language G with respect to another 
   language H , mask M, controllability info C.

   Arguments - 
			fpmaskinfo - file pointer containing information 
				about the mask M  
			fpuncevents - file pointer containing information 
				about the controllability info C
			fsmG - pointer to the state machine which is a
				generator for G
			fsmH - pointer to the state machine which is a
		      generator for H
			fsmResult - pointer to the resultant state machine

   Return Type : void

   ************************************************************** */
void fsm_sup_cont_norm_sublang(fpmaskinfo, fpuncevents, fsmG, fsmH, fsmResult)
FILE *fpmaskinfo, *fpuncevents;
FSM *fsmG, *fsmH, *fsmResult;
{
	ST_LIST *st_ptr;
	int	 i, reachgood, num_states1, num_states2;
	NAME_LIST *name_list, *ptrname_list;

	FSM fsmH_bar, fsmP, fsmPmasked, fsmPmaskedun, fsmPmaskedunnoep, fsmQ, fsmR, fsmRtmp;
	TRANS_LIST *tr_ptr = NULL;
	FILE *fptmpeventset;
	char *uncontlist[MAX_LENGTH];
	char x[MAX_LENGTH], y[MAX_LENGTH], Z[MAX_LENGTH], Z2[MAX_LENGTH];
	size_t strlen1, strlen2;
	char *ptrcomma, *ptrcommasecond, *ptrcommathird;
	ST_LIST *current_state, *search_state, *foundstate, *next_state;
	TR_LIST *curr_trans;
	ST_PAIRS_LIST *searchpair=NULL, *searchpair2 = NULL;

	fptmpeventset = fopen("trlist.tmp","w+");

	fsm_find_sigma(fsmG, &tr_ptr); /*get list of events*/

	while(tr_ptr) /*write event set to file*/
	{
		fprintf(fptmpeventset, "%s\n", tr_ptr->input);
		tr_ptr = tr_ptr->next;
	}
	fclose(fptmpeventset);
	fptmpeventset = fopen("trlist.tmp","r");
	CompleteGraph(fptmpeventset, fsmH, &fsmH_bar);
	fsm_sync_comp(fsmG, &fsmH_bar, &fsmP); /*P = G||Hbar*/	
	fsm_mask(fpmaskinfo, &fsmP, &fsmPmasked); /*file is mlist0.tmp see demo "n"*/
	fsm_unmask(fpmaskinfo, &fsmPmasked, &fsmPmaskedun);
	fsm_remove_epsilon(&fsmPmaskedun, &fsmPmaskedunnoep);
      fsm_deterministic(&fsmPmaskedunnoep, &fsmQ);
	fsm_sync_comp(&fsmP, &fsmQ, &fsmR); /*R = P||Q*/

	/*a state (x,y,Z) is marked if x & y are marked (Z is multiple states)*/
	/*taken care of by sync comp*/
	
	po_read_cont_file2(fpuncevents, uncontlist);
	current_state = fsmR.states;
	/*state (x,y,Z) is bad if y = dump*/
	while(current_state)
	{
	strlen1 = strlen(current_state->name);
	ptrcomma = strstr(current_state->name, ","); /*states listed as x,y,Z*/
	strncpy(x, current_state->name, strlen1-strlen(ptrcomma)); /*x = first state*/
	
	ptrcommasecond = strstr((ptrcomma+1), ","); /*point to 2nd comma*/
	/*strncpy(y, (ptrcomma+1), strlen(ptrcomma+1)-strlen(ptrcommasecond)); /*y = second state*/
	/*y not being padded with '/0'?*/
	strcpy(y, ptrcomma+1);
	*(y + strlen(ptrcomma+1)-strlen(ptrcommasecond)) = '\0';

	if(strstr(y, "dump")!=NULL) /*strstr nec.?, bad iff y = dump*/
		MarkBadState(&fsmR, current_state);

	current_state = current_state->next;
	}

	do{

	num_states1 = get_NBadStates(&fsmR); /* calculate numbers of states in FSM */

	/*state is bad if there is an uncontrollable transition to a bad state*/
	current_state = fsmR.states;
	while(current_state)
	{
		curr_trans=current_state->trans;
		if(strstr(current_state->name, "@$")==NULL) { /*if not already marked bad*/
			while(curr_trans) {
				if(FindLabel(uncontlist, curr_trans->input)){ /*check uncontrollable transitions*/
					if(strstr(curr_trans->next_state->name,"@$")!=NULL) {
					/* this is a bad transition as it leads to a bad
					state..so mark it bad */
					MarkBadState(&fsmR,current_state);
					}
				} /* if strcmp ends */
				curr_trans = curr_trans->next;		
			} /* while curr_trans ends */
		} /* if strstr ends */
		current_state = current_state->next;
	}

	/*find matched states, mark if bad*/
	current_state = fsmR.states;
	while(current_state)
	{
		if(strstr(current_state->name, "@$")==NULL) { /*if not already marked bad*/
			search_state = fsmR.states; 
			while(search_state)
			{
				/*don't compare a state to itself
				looking if a matching BAD state @$*/
				if((search_state != current_state) && (strstr(search_state->name, "@$")!=NULL))
				{  
					strcpy(Z, current_state->name);
					strcpy(Z2, search_state->name);

					parse_stpair(Z, &searchpair);
                    parse_stpair(Z2, &searchpair2);
                    
                    if(compare_stpairs(searchpair, searchpair2))
                    { /*matched a bad state so mark!*/
						MarkBadState(&fsmR,current_state);
                    }
                    
                    free_stpair(&searchpair);
                    free_stpair(&searchpair2);  
				}
			search_state = search_state->next;
			}
		} /* if strstr ends */
		current_state = current_state->next;
	}

	fsm_copy(&fsmR, &fsmRtmp); /*temporarily remove bad states for next step*/
	/*remove bad states*/
	current_state = fsmRtmp.states;
	while(current_state)
	{
		if(strstr(current_state->name, "@$")!=NULL){
		    next_state = current_state->next; /*in case need to delete*/
                delete_state(&fsmRtmp, current_state);
		    current_state = next_state;
		    }
		else
		current_state = current_state->next;
	}

	/*mark bad if can't reach marked state*/
	current_state = fsmRtmp.states;
	while(current_state)
	{	
		reachgood = 0;
		
		i = fsm_reachability(&fsmRtmp, current_state->name, "ALL", &name_list); /*ever dealloc namelist?*/
					
			/* find if one of the states reached is marked and good */
			ptrname_list = name_list;
			while(ptrname_list && !reachgood)
			{
					/* determine if state is marked, if so reachgood = 1 */
					st_ptr = find_state(&fsmRtmp, ptrname_list->name); /*find in fsmR, use ptr for below?*/
					
					if(st_ptr->marked == MKD)
						reachgood = 1;
			
			ptrname_list = ptrname_list->next;
			}
			if(!reachgood)	/* doesn't reach a good marked state, therefore mark state as bad */
			{
				foundstate = find_state(&fsmR, current_state->name);
				MarkBadState(&fsmR, foundstate);/*mark bad state in complete fsm*/
/*				delete_state(&fsmRtmp, current_state); /*delete state since it is bad*/
				
				MarkBadState(&fsmRtmp, current_state);/*mark bad state in temp fsm*/
				
			}
		current_state = current_state->next;
        delete_name(&name_list);
	}

	fsm_delete(&fsmRtmp); /*delete fsm created for above step*/
	num_states2 = get_NBadStates(&fsmR); /* Find new number of bad states in FSM */
	
	/*
		Stop if no new good state converted to bad state, or no good
		states remaining. Output automata restricted to good states.
	*/
	}while(num_states2 != num_states1);
	
	
	
	/**************************************/
	/*remove bad states*/
	current_state = fsmR.states;
	while(current_state)
	{
		if(strstr(current_state->name, "@$")!=NULL){
                next_state = current_state->next; /*in case need to delete*/
                delete_state(&fsmR, current_state);
		    current_state = next_state;
		    }
		else
		current_state = current_state->next;
	}

	/*trim?*/

      if(fsmR.states)
      fsm_trim(&fsmR);
	
	fsm_copy(&fsmR, fsmResult);
	fclose(fptmpeventset);
	unlink("trlist.tmp");

	fsm_delete(&fsmH_bar);
	fsm_delete(&fsmP);
	fsm_delete(&fsmPmasked);
	fsm_delete(&fsmPmaskedun);
	fsm_delete(&fsmQ);
	fsm_delete(&fsmR);
	/*po_del_uncontlist(uncontlist);*/
}
/*******************CONTROL TEST******************/
int ControlTest(FILE *f1, FILE *f2, FILE *f3)
{
        FILE *f4, *fpeventset;
        FSM fsm1, fsm2, fsm3, fsm4;
        TRANS_LIST *listL = NULL;
        int flag;

        po_extract_events(f3); /*get cont. info from cont/mask info, creates clist.tmp*/
        fsm_read(f1, &fsm1);
        fsm_read(f2, &fsm2);
        f4 = fopen("clist0.tmp", "r"); /*info in clist.tmp*/

	/* generate a list of events from the plant */
	fpeventset = fopen("tmplist.out", "w+");

	fsm_find_sigma(&fsm1, &listL); /*extract set of events from plant fsm*/

	while(listL) /*create file to store event set*/
	{
		fprintf(fpeventset, "%s\n", listL->input); /* write events and controllable information */
		listL = listL->next;
	}
	
	fclose(fpeventset);

	fpeventset = fopen("tmplist.out", "r");

	
	/* complete spec with list of events */
	CompleteGraph(fpeventset, &fsm2, &fsm3);

	/* fsm4 = sync. comp. of plant and completed specification */
	fsm_sync_comp(&fsm1, &fsm3, &fsm4);        

	fclose(fpeventset);
	unlink("tmplist.out");

	flag = ControlCheck(&fsm4, f4);
	
      fclose(f4);
      
      fsm_delete(&fsm1);
      fsm_delete(&fsm2);
      fsm_delete(&fsm3);
      fsm_delete(&fsm4);
      po_remove_event_temp_files();
      return(flag);
}

