2

I'd like to know how you can tell if some regular expression is the complement of another regular expression. Let's say I have 2 regular expressions r_1 and r_2. I can certainly create a DFA out of each of them and then check to make sure that L(r_1) != L(r_2). But that doesn't necessarily mean that r_1 is the complement of r_2 and vice versa. Also, it seems to be that many different regular expressions that could be the same complement of a single regular expression. So I'm wondering how, given two regular expressions, I can determine if one is the complement of another. This is also new to me, so perhaps I'm missing something that should be apparent.

Edit: I should point out that I am not simply trying to find the complement of a regular expression. I am given two regular expressions, and I am to determine if they are the complement of each other.

JohnnyD27
  • 83
  • 1
  • 7
  • 1
    Possible duplicate of [Finding the complement of a DFA?](https://stackoverflow.com/questions/14802732/finding-the-complement-of-a-dfa) – Callum Watkins Mar 03 '19 at 21:44
  • No, this is not a duplicate. I am not trying to find the complement of a DFA or of a regular expression. I am given two regular expressions, and I need to determine if they are the complement of each other. – JohnnyD27 Mar 03 '19 at 22:22
  • Surely though, if you convert one to its complement, then compare with the other, you should have your answer? i.e. `L(r_1) == !L(r_2)`, where the `!` is finding the complement. – Callum Watkins Mar 03 '19 at 22:23
  • Not necessarily. You can have many equivalent regular expressions that do not "look" the same. I found this out by doing that very method that you suggested. – JohnnyD27 Mar 04 '19 at 19:54
  • Once you have converted the regular expressions to finite automata, you can compare them, for example: https://stackoverflow.com/questions/6905043/equivalence-between-two-automata – Callum Watkins Mar 04 '19 at 19:56
  • Ah I see. So then this would be the best solution: Given regex r_1 and r_2, to see if one is the complement of the other, create two DFAs A and B out of each of them, convert one to its complement form, let's say A to A_comp, and see if A_comp and B are equivalent. I think that makes sense. Thanks! – JohnnyD27 Mar 04 '19 at 20:02
  • Precisely, you’re welcome. – Callum Watkins Mar 04 '19 at 20:03

2 Answers2

0

Here is one approach that is conceptually simple, if not terribly efficient (not that there is necessarily a more efficient solution...):

  1. Construct NFAs M and N for regular expressions r and s, respectively. You can do this using the construction introduced in the proof that finite automata describe the same languages.
  2. Determinize M and N to get M' and N'. We might as well go ahead and minimize them at this point... giving M'' and N''.
  3. Construct a machine C using the Cartesian product machine construction on machines M'' and N''. Acceptance will be determined by the symmetric difference, or XOR, criterion: accepting states in the product machine correspond to pairs of states (m, n) where exactly one of the two states is accepting in its automaton.
  4. Minimize C and call the result C'
  5. If L(r) = L(s)', then the initial state of C' will be accepting and C' will have all transitions originating in the initial state also terminating in the initial state. If this is the case,

Why should this work? The symmetric difference of two sets is the set of everything in exactly one (not both, not neither). If L(s) and L(r) are complementary, then it is not difficult to see that the symmetric difference includes all strings (by definition, the complement of a set contains everything not in the set). Suppose now there were non-complementary sets whose symmetric difference were the universe of all strings. The sets are not complementary, so either (1) their union is non-empty or (2) their union is not the universe of all strings. In case (1), the symmetric difference will not include the shared element; in case (2), the symmetric difference will not include the missing strings. So, only complementary sets have the symmetric difference equal to the universe of all strings; and a minimal DFA for the set of all strings will always have an accepting initial state with self-loops.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
-1

For complement: L(r_1) == !L(r_2)

user2468968
  • 286
  • 3
  • 9
  • 2
    Can you elaborate? – JohnnyD27 Mar 03 '19 at 19:26
  • Assuming you have a prover, either a formal one or you have a large enough data-set for qualification; if r_1 hits and r_2 does not, and r_2 hits and r_1 does not, then they are complementary. – user2468968 Mar 03 '19 at 19:31
  • I'm still not sure I understand what you mean. Are you perhaps suggesting that I create a DFA A out of r_1 and check that A rejects r_2, and then create a DFA B out of r_2 and check that B rejects r_1? – JohnnyD27 Mar 03 '19 at 19:37
  • You should be proving "L(r_1) == !L(r_2)" for a complementary relation, rather than "L(r_1) != L(r_2)". (Using whatever method) – user2468968 Mar 03 '19 at 19:46
  • 1
    I see. But I think you're essentially rewording my question. What are those methods for showing that L(r_1) == ! L(r_2)? – JohnnyD27 Mar 03 '19 at 19:50
  • If you have DFA and looking for formal proof software, try Googling for "model checking". – user2468968 Mar 03 '19 at 20:13