Results 1 to 13 of 13
  1. #1
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default How to create regular expressions in Java

    Hi,

    i need to represent a String in the form of a regular expression in java. I need to somehow analyse the letters of the string and produce the expression representing that string.

    For example if i have the string: abababab , i need to output (ab)*

    another example if i have the string: aaaaab, i need to output (a)*b

    Could anyone please advise.

    Thanks

  2. #2
    Steve11235's Avatar
    Steve11235 is offline Senior Member
    Join Date
    Dec 2008
    Posts
    1,046
    Rep Power
    7

    Default

    You want to reduce the input String to an equivalent String that represents repeating characters or groups with special characters. That sounds *very* complicated.
    The Java Tutorial. Read it.

  3. #3
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,193
    Rep Power
    19

    Default

    You'd have to write a parser, and a rather complicated one at that.

    Why do you need this? There may be some easier way to achieve your goal.

    db

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,438
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by maz09 View Post
    Hi,
    For example if i have the string: abababab , i need to output (ab)*
    You can't find such a regular expression uniquely; e.g. for the first example the regexes (abab)*, (abab)+ and abababab are also valid. I'd say that only the last regex is 'completely' valid because the other two can generate/accept other strings as well, but so does .* and is that considered a valid regex as well?

    kind regards,

    Jos
    Last edited by JosAH; 04-02-2010 at 08:46 AM.

  5. #5
    wangwei is offline Member
    Join Date
    Apr 2010
    Posts
    10
    Rep Power
    0

    Default

    Hi, glad to c your question.
    According to your description, I think it very hard to implement it. Like JosAH says, there is no unique expression with string "abababab", but dozens of.

  6. #6
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default

    maybe i am approaching this incorrectly...

    my goal is to convert a DFA to a regular expression, by traversing the transitions for every state..collecting the symbols along the way according to a specific algorithm, called Convert(G).

    i have made my DFA in Java using Hashmaps, now all i need to do is somehow implement that Convert(G) algorithm on that DFA.

    The goal of this algorithm is to end up with two states, and a regular expression representing the language the DFA accepts.
    Last edited by maz09; 04-02-2010 at 07:27 PM.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,438
    Blog Entries
    7
    Rep Power
    20

    Default

    Are you studying this lecture? The algorithm is in there.

    kind regards,

    Jos

  8. #8
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default

    yes, thats the lecture, i need to implement this conversion in Java. my DFA is all set up, with transitions symbols as type String. However , this GNFA uses Regular expressions as transitions :S

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,438
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by maz09 View Post
    yes, thats the lecture, i need to implement this conversion in Java. my DFA is all set up, with transitions symbols as type String. However , this GNFA uses Regular expressions as transitions :S
    But the entire algorithm (plus examples) is described in that paper in pseudo code; what do you want us to do? Implement it for you?

    kind regards,

    Jos

  10. #10
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default

    well i was just hoping for some guidance really, as my DFA at the moment has symbols on the transitions, i dont know how i would go about representing these symbols as regular expressions from a String ...

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,438
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by maz09 View Post
    well i was just hoping for some guidance really, as my DFA at the moment has symbols on the transitions, i dont know how i would go about representing these symbols as regular expressions from a String ...
    It's all String fiddling; e.g. if you have the transitions S -> R1 -> E and S -> R2 -> E you have to combine those two regular expressions R1 and R2 (their String forms) to S -> (R1|R2) -> E.

    kind regards,

    Jos

  12. #12
    maz09 is offline Member
    Join Date
    Jan 2010
    Posts
    13
    Rep Power
    0

    Default

    thanks, i understand that, however, in terms of java... how would that combination take place?

    If R1 were equal to ab.
    and R2 were equal to ba for example, then i would just hardcode to remove these transitions and replace it by a string: "ab " + "|" + " ba" . But i know thats wrong

    I dont see how to put them in some sort of Set form so that the union, concatenation can be done to facilitate the [(R1)(R2)∗(R3)] U (R4) for instance.

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,438
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by maz09 View Post
    thanks, i understand that, however, in terms of java... how would that combination take place?

    If R1 were equal to ab.
    and R2 were equal to ba for example, then i would just hardcode to remove these transitions and replace it by a string: "ab " + "|" + " ba" . But i know thats wrong

    I dont see how to put them in some sort of Set form so that the union, concatenation can be done to facilitate the [(R1)(R2)∗(R3)] U (R4) for instance.
    There is nothing wrong about that transformation; you could add parentheses if you're not sure about the precedence of the operators, i.e. (ab)|(ba) but all transformations can be done in String form. You want to end up with a final regular expression in String form don't you? Maybe because it's Friday but I don't see a problem with that approach.

    kind regards,

    Jos

Similar Threads

  1. Using regular expressions for search
    By carderne in forum New To Java
    Replies: 9
    Last Post: 05-24-2009, 04:58 AM
  2. Regular Expressions in java
    By blue404 in forum Advanced Java
    Replies: 2
    Last Post: 09-26-2008, 03:43 AM
  3. Regular expressions from command prompt
    By GenkiSudo in forum New To Java
    Replies: 2
    Last Post: 09-21-2008, 02:40 PM
  4. Using Quantifiers in regular expressions
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 01-10-2008, 10:43 AM
  5. Regular expressions quantifiers
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 12-25-2007, 11:18 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •