1

I have two regexps. I need to determine if it is possible to build string of given length that matches these two regexps simultaneously. I need algorithm to do that.

String's length wouldn't exceed 20 characters.

frp
  • 1,119
  • 1
  • 10
  • 30
  • 6
    Don't be shy. Show us the 2 regexps – Déjà vu Feb 10 '13 at 12:59
  • It is program, so these two regexps would be different in every run of this program. – frp Feb 10 '13 at 13:02
  • 1
    If you want to *build* a string, you can do the following if you have the two DFAs for the RegExes: use the cartesian product of the automata and search a path from the initial state to the accepting state via a graph search algorithm. – phant0m Feb 10 '13 at 13:10
  • @frp, your assignment must have regexp constraints otherwise the solution - while possible - will be pretty complex (and the way you ask the question suggests you are not looking for a fully [PCRE](http://www.pcre.org/) compliant algorithm) – Déjà vu Feb 10 '13 at 13:11
  • The first one is usual regexp (without backreferences and "hard features" of PCRE). The second one can be simplified to comprise of only dots and letters. – frp Feb 10 '13 at 13:19

1 Answers1

5

It depends. For perl compatible regular expressions (pcre), this is not generally possible, as they are turing complete: you cannot even be sure that matching always terminates.

For the original, "clean" form of reguler languages as defined in the Chomsky-hierarchy, it is known that they are closed under intersection, this is already discussed in this thread.

As soon as you have the NFA for the intersection, it is easy to check whether any string matches it - if thera is a path from the start to the end of your NFA, then the string for this path is the string you are searching for, for DFAs, an algorithm is given here, it should be simple to adapt it to NFAs.

Community
  • 1
  • 1
schoppenhauer
  • 411
  • 3
  • 11