Howdy, Stranger!

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

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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: Cyboy@drdptm.ro -
    ------------------------------


    Yours, Cyboy.

Sign In or Register to comment.