Regular Expressions Equivalence (Please Urgent) - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Posts: 3Member
Hi All,

Anyone knows if there is a way to check two regular expressions for equivalence?

ex. re1="[aA][bBcCdDeEfF][123]+"
re2="[Aa][B-Fb-f][321][231]*"
The above reg.exps will match the same strings.
How can I know it?

Any Help Appreciated.

• Posts: 3Member
: Hi All,
:
: Anyone knows if there is a way to check two regular expressions for equivalence?
:
: ex. re1="[aA][bBcCdDeEfF][123]+"
: re2="[Aa][B-Fb-f][321][231]*"
: The above reg.exps will match the same strings.
: How can I know it?
:
: Any Help Appreciated.
:
:
:

Yeah. This problem hit me, too. It is very hard! The only sollution I found was a recursive function which i later translated to a function that used a stack. This is your job. I'm only going to help with the 1st.

First of all: You need to check the equivalence between two characters... where a character can be a basic regular expression. (ie, [1-8] is a character, like [571] or simply X adding the option: +, . or * (depends what you understand by them, i found at least 2 books with different semnifications for them)).

OK. Used pascal expressions, closer to pseudocode... I think...

So, we have this:
* function CheckEq(a,b:string):boolean;
or replace a,b:string with whatever you want. Then check if the first characters match, and how! You need to check if the first character in A matches the first character in B or, if * is specified you need a to check for ALL occurences of the first character in A in B. When you found an equivalent of the first regular character in A in B, you need to recall the function:
* if CheckEq(X,Y) then begin CheckEq:=true; exit; end;
Where X is A, less the first regular character and Y is B, less the part starting from the first character in B to the first occurance of the first regular character of A found in B, including it!

So, you find the A[1] in B and call CheckEq(copy(A,2,length(A)-1),copy(B,Where_Found,length(B)-Where_Found+1)), where Where_Found is the current occurance of the first regular character of A in B.

Then do the same but switch: Search for the first regular character in B for regular occurances in A and when you found it, you do the same (CheckEq(copy(B,2,length(B)-1),copy(A,Where_Found,length(A)-Where_Found+1), where Where_Found is the occurance of the first regular character of B in A.

When both expressions reach a void value, you don't do this algorithm thingie, but you simply return:
* if (A='')and(B='') then begin CheckEq:=true; exit end;
If one is empty and you CAN'T find any occurance of the first character in the other in the first, then you return as false:
* if (Where_Found=0)and(B='') then CheckEq:=false; exit end;
^^ assuming that you searched for the 1st reg char in A somewhere in B and you didn't find it; result=0

------------------------------
- More help: [email protected] -
------------------------------

Yours, Cyboy.