COSC5315                   Program-3
	                  Regular Expression Checker 
	                                  		Due: 4/9/2007

	Task:
	
	Write a program that checks to see if two input regular expressions are equal.
	This may involve the following:
	1. Convert each input regular expression to an equivalent
	   completely specified DFSA.
	2. Minimize the above.
	3. Compare each pair of the two resulting minimized DFSA's
	   for their equality.

	Algorithm for checking DFSA Equality:
	(* This algorithm traverses the two transition graphs of
	(* the two DFSA's in a depth-first fashion until a mismatch 
	(* between the two graphs is found until traversal is complete.  **)	

	1. Initialize:
	   Top1 <-- Top2 <- 1;
	   EQUAL <-- [(Q1=Accepting) == (P1=Accepting)]
	   Stack1[Top1].State <-- Q1; (* Initial state of DFSA1 *)
	   Stack2[Top2].State <-- P1; (* Initial state of DFSA2 *)
	   Stack1[Top1].Input <-- a;  (* First input symbol     *)
	   Stack2[Top2].Input <-- a;  (* The same first input symbol *)
	2. While Equal and (Top1 > 0) repeat
	   a. PopStack (Stack1, Top1, State1, Input);
	      PopStack (Stack2, Top2, State2, Input);
	   b. Mark two states State1 and State2 both visited.
	   c. If Input is not the last input-symbol then
	        PushStack (Stack1, Top1, State1, Input+1);
	          (* Push back the same state but the next input symbol *)
	        PushStack (Stack2, Top2, State2, Input+1);
	   d. Next1 <-- Delta (State1,Input);
	      Next2 <-- Delta (State2,Input);
	   e. If both States Next1 and Next2 are unvisited yet then
	        If one state is accepting but the other not then
	          EQUAL <-- false
	        else (* Both must be accepting or both nonaccepting *)
	          PushStack (Stack1, Top1, Next1, First-input);
	          PushStack (Stack2, Top2, Next2, First-input);
	   f. Else if  one state is visited and the other not then
	             EQUAL <-- False;
	           (* Else, both must be already visited and hence
	              they are done, and so do nothing              *)

	Inputs: Use the following seven input pairs.

	1. (a+bb)(a+bb)* + ^
	   (a+bb)*
	2. (a+bb)(a+bb)*
	   (a+bb)*(a+bb)
	3. (a*b*)*
	   (a+b)*
	4. (ab+a)*a
	   a(ba+a)*
	5. (a(a+cb*a)*b)* a (a+cb*a)*
	   (a(a+cb*a)*b)* (a + a(a+cb*a)* (a+cb*a))
	6. (ab + cd)*
	   (ab)* + (abcd)* + (cdab)* + (cd)*
	7. (a+b)*
	   a*b*(a+b)*a*b*