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*