4

There's a question on my exercise sheet to find the complement of two formulas

(1) (aa|bb)*

and

(2) (a|b)(aa|bb)(a|b).

complement of both is in my opinion a* | b*, meaning only a's or only b's?

Lemur
  • 2,659
  • 4
  • 26
  • 41
sushi
  • 41
  • 1
  • 1
  • 2
  • 1
    related: [A regular expression for the complement of the language L](http://stackoverflow.com/q/9861949/1048572) – Bergi Mar 16 '13 at 17:42
  • also: [How do I turn any regex into a complement of itself?](http://stackoverflow.com/questions/3977455/how-do-i-turn-any-regex-into-an-complement-of-itself-without-complex-hand-editin) – JohnJ Mar 16 '13 at 17:44
  • In short: No. `aba` for example is neither matched by the formulas nor by your solution, so it can't be the complement. – Bergi Mar 16 '13 at 17:47

2 Answers2

6

You need to go through the usual procedure:

  • Convert regex to NFA.
  • Convert NFA to DFA. For simple case, it is easy to convert (by hand) from regex to DFA directly.
  • Turn all non-terminal state into terminal states and vice versa.
  • Convert the complementing DFA to regex. This is one detailed example of such conversion

I won't show you the result since it is exercise, but I will show you the DFA for the first formula (aa|bb)*:

Formula 1

From this, you can see clearly that a* or b* will not give the correct result. You will never end up in the Trap state (which becomes a terminal state in the complementing regular expression), and you may end up in state 2a/2b (which becomes non-terminal state in the complementing regular expression).

Community
  • 1
  • 1
nhahtdh
  • 55,989
  • 15
  • 126
  • 162
0

Simply (aa+bb)* will contain sample strings such as null, aa, aaaa, bb, bbbb, aabb, bbaa, and so on observe that all strings that can be formed are of even length and a and b can be any order, so complement should contain all odd-length strings ((a+b)(a+b))*(a+b)

Dhruv Joshi
  • 33
  • 1
  • 7
arun sharma
  • 1
  • 1