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

Regular Expressions Equivalence (Please Urgent)

theotyflostheotyflos 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.


Comments

  • CyboyCyboy 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.

Sign In or Register to comment.