Regex: Determine if two regular expressions could match for the same input?

by

There’s no halting problem involved here. All you need is to compute if the intersection of ^xy1\d and [^\d]\d2$ in non-empty.

I can’t give you an algorithm here, but here are two discussions of a method to generate the intersection without resorting the construction of a DFA:

And then there’s RAGEL

which can compute the intersection of regular expressions too.

UPDATE: I just tried out Ragel with OP’s regexp. Ragel can generate a “dot” file for graphviz from the resulting state machine, which is terrific. The intersection of the OP’s regexp looks like this in Ragel syntax: 

('xy1' digit any*) & (any* ^digit digit '2')

and has the following state machine:

enter image description here

While the empty intersection: 

('xy1' digit any*) & ('q' any* ^digit digit '2')

looks like this:

enter image description here

So if all else fails, then you can still have Ragel compute the intersection and check if it outputs the empty state machine, by comparing the generated “dot” file.

More Related Contents:

  1. Phone number regular expressions exact format
  2. Regex to match string containing two names in any order
  3. Validating IPv4 addresses with regexp
  4. Does a dot have to be escaped in a character class (square brackets) of a regular expression?
  5. What flavor of Regex does Visual Studio Code use?
  6. How to back reference “inner” selections ( () ) in a regular expression?
  7. Regular expression – PCRE does not support \L, \l, \N, \P,
  8. sed one-liner to convert all uppercase to lowercase?
  9. Returning a regex match in VBA (excel)
  10. Regex to match month name followed by year
  11. regex to match word boundary beginning with special characters
  12. Does the ‘o’ modifier for Perl regular expressions still provide any benefit?
  13. regular expression to match everything until the last occurrence of /
  14. regular expression capture nth match
  15. What regex will match every character except comma ‘,’ or semi-colon ‘;’?
  16. Regular Expression Validation For Indian Phone Number and Mobile number
  17. Can I use Perl regular expressions to match balanced text?
  18. How do I perform a Perl substitution on a string while keeping the original?
  19. replace a unknown string between two known strings with sed
  20. Match Sequence using RegEx After a Specified Character
  21. How can I parse quoted CSV in Perl with a regex?
  22. Nginx location “not equal to” regex
  23. How to escape dollar sign ($) in a string using perl regex
  24. Checking for diacritics with a regular expression
  25. Design DFA accepting binary strings divisible by a number ‘n’
  26. Replace all whitespace with a line break/paragraph mark to make a word list
  27. Regex matching beginning AND end strings
  28. Regex return file name, remove path and file extension
  29. How do I turn any regex into an complement of itself without complex hand editing?
  30. Matching url with array list of words in AngularJS ui-router

Leave a Comment