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
    10

    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 Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    12,029
    Rep Power
    23

    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
    14,395
    Blog Entries
    7
    Rep Power
    25

    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
    14,395
    Blog Entries
    7
    Rep Power
    25

    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
    14,395
    Blog Entries
    7
    Rep Power
    25

    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
    14,395
    Blog Entries
    7
    Rep Power
    25

    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
    14,395
    Blog Entries
    7
    Rep Power
    25

    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, 11:43 AM
  5. Regular expressions quantifiers
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 12-25-2007, 12:18 PM

Posting Permissions

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