How to determine if a regex is orthogonal to another regex?

Question

I guess my question is best explained with an (simplified) example.

Given the case there's one regex like

^\d+_[a-z]+$

and another regex like

^\d*$

it's clear that something regex 1 matches to, will never match regex 2. So regex 2 is orthogonal to regex 1.

As many people asked what I meant by orthogonal I'll try to clarify it:

Let S1 be the (infinite) set of strings where regex 1 matches. S2 is the set of strings where regex 2 matches. Regex 2 is orthogonal to regex 1 iff the intersection of S1 and S2 is empty. The regex ^\d_a$ would be not orthonal as the String '2_a' is in the set S1 and S2.

In some cases it is certainly not possible to determine if a regex is orthogonal to another regex.

My question is, how can it be programmatically determined, if a regex is orthognal to another?

Best case would be some library that implements a method like:

/**
 * @return True if the regex is orthogonal (i.e. "intersection is empty"), False otherwise or Null if it can't be determined
 */
public Boolean isRegexOrthogonal(Pattern regex1, Pattern regex2);

Answer 1

You can maybe use something like Regexp::Genex to generate test strings to match a specified regex and then use the test string on the 2nd regex to determine whether the 2 regexes are orthogonal.

Answer 2

Proving that one regular expression is orthogonal to another can be trivial in some cases, such as mutually exclusive character groups in the same locations. For any but the simplest regular expressions this is a nontrivial problem. For serious expressions, with groups and backreferences, I would go so far as to say that this may be impossible.

Answer 3

This seems to be a different use of the word orthogonal than I'm used to.

Do you consider two REs orthogonal if they overlap in any way? Or if one is a subset of the other? Or simply if they cannot be used to match the same text?

If the last, then you can use the fact that any RE can be translated into a finite state machine. Two finite state machines are equal if they have the same set of nodes, with the same arcs connecting those nodes.

So, given what I think you're using as a definition for orthogonal, if you translate your REs into FSMs and those FSMs are not equal, the REs are orthogonal.

Answer 4

By "Orthogonal" you mean "the intersection is the empty set" I take it?

I would construct the regular expression for the intersection, then convert to a regular grammar in normal form, and see if it's the empty language...

Then again, I'm a theorist...

Answer 5

I believe kdgregory is correct you're using Orthogonal to mean Complement.

Is this correct?

Answer 6

Let me start by saying that I have no idea how to construct such an algorithm, nor am I aware of any library that implements it. However, I would not be at all surprised to learn that nonesuch exists for general regular expressions of arbitrary complexity.

Every regular expression defines a regular language of all the strings that can be generated by the expression, or if you prefer, of all the strings that are "matched by" the regular expression. Think of the language as a set of strings. In most cases, the set will be infinitely large. Your question asks whether the intersections of the two sets given by the regular expressions is empty or not.

At least to a first approximation, I can't imagine a way to answer that question without computing the sets, which for infinite sets will take longer than you have. I think there might be a way to compute a limited set and determine when a pattern is being elaborated beyond what is required by the other regex, but it would not be straightforward.

For example, just consider the simple expressions (ab)* and (aba)*b. What is the algorithm that will decide to generate abab from the first expression and then stop, without checking ababab, abababab, etc. because they will never work? You can't just generate strings and check until a match is found because that would never complete when the languages are disjoint. I can't imagine anything that would work in the general case, but then there are folks much better than me at this kind of thing.

All in all, this is a hard problem. I would be a bit surprised to learn that there is a polynomial-time solution, and I would not be at all surprised to learn that it is equivalent to the halting problem. Although, given that regular expressions are not Turing complete, it seems at least possible that a solution exists.

Answer 7

I would do the following:

• convert each regex to a FSA, using something like the following structure:

  struct FSANode
  {
      bool accept;
      Map<char, FSANode> links;
  }
  List<FSANode> nodes;
  FSANode start;
  

Note that this isn't trivial, but for simple regex shouldn't be that difficult.

• Make a new Combined Node like:

  class CombinedNode
  {
      CombinedNode(FSANode left, FSANode right)
      {
          this.left = left;
          this.right = right;
      }
  
  
  Map<char, CombinedNode> links;
  bool valid { get { return !left.accept || !right.accept; } }
  
  
  public FSANode left;
  public FSANode right;
  
  
  }
  

Build up links based on following the same char on the left and right sides, and you get two FSANodes which make a new CombinedNode.

Then start at CombinedNode(leftStart, rightStart), and find the spanning set, and if there are any non-valid CombinedNodes, the set isn't "orthogonal."

Answer 8

The fsmtools can do all kinds of operations on finite state machines, your only problem would be to convert the string representation of the regular expression into the format the fsmtools can work with. This is definitely possible for simple cases, but will be tricky in the presence of advanced features like look{ahead,behind}.

You might also have a look at OpenFst, although I've never used it. It supports intersection, though.

Answer 9

I would construct the regular expression for the intersection, then convert to a regular grammar in normal form, and see if it's the empty language...

That seems like shooting sparrows with a cannon. Why not just construct the product automaton and check if an accept state is reachable from the initial state? That'll also give you a string in the intersection straight away without having to construct a regular expression first.

I would be a bit surprised to learn that there is a polynomial-time solution, and I would not be at all surprised to learn that it is equivalent to the halting problem.

I only know of a way to do it which involves creating a DFA from a regexp, which is exponential time (in the degenerate case). It's reducible to the halting problem, because everything is, but the halting problem is not reducible to it.

If the last, then you can use the fact that any RE can be translated into a finite state machine. Two finite state machines are equal if they have the same set of nodes, with the same arcs connecting those nodes.

So, given what I think you're using as a definition for orthogonal, if you translate your REs into FSMs and those FSMs are not equal, the REs are orthogonal.

That's not correct. You can have two DFAs (FSMs) that are non-isomorphic in the edge-labeled multigraph sense, but accept the same languages. Also, were that not the case, your test would check whether two regexps accepted non-identical, whereas OP wants non-overlapping languages (empty intersection).

---

Also, be aware that the \1, \2, ..., \9 construction is not regular: it can't be expressed in terms of concatenation, union and * (Kleene star). If you want to include back substitution, I don't know what the answer is. Also of interest is the fact that the corresponding problem for context-free languages is undecidable: there is no algorithm which takes two context-free grammars G1 and G2 and returns true iff L(G1) ∩ L(g2) ≠ Ø.

Answer 10

Convert each regular expression into a DFA. From the accept state of one DFA create an epsilon transition to the start state of the second DFA. You will in effect have created an NFA by adding the epsilon transition. Then convert the NFA into a DFA. If the start state is not the accept state, and the accept state is reachable, then the two regular expressions are not "orthogonal." (Since their intersection is non-empty.)

There are know procedures for converting a regular expression to a DFA, and converting an NFA to a DFA. You could look at a book like "Introduction to the Theory of Computation" by Sipser for the procedures, or just search around the web. No doubt many undergrads and grads had to do this for one "theory" class or another.

Answer 11

I spoke too soon. What I said in my original post would not work out, but there is a procedure for what you are trying to do if you can convert your regular expressions into DFA form.

You can find the procedure in the book I mentioned in my first post: "Introduction to the Theory of Computation" 2nd edition by Sipser. It's on page 46, with details in the footnote.

The procedure would give you a new DFA that is the intersection of the two DFAs. If the new DFA had a reachable accept state then the intersection is non-empty.

Answer 12

Excellent point on the \1, \2 bit... that's context free, and so not solvable. Minor point: Not EVERYTHING is reducible to Halt... Program Equivalence for example.. – Brian Postow

[I'm replying to a comment]

IIRC, a^n b^m a^n b^m is not context free, and so (a\*)(b\*)\1\2 isn't either since it's the same. ISTR { ww | w ∈ L } not being "nice" even if L is "nice", for nice being one of regular, context-free.

I modify my statement: everything in RE is reducible to the halting problem ;-)