问题:

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?

回答1:

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)*:

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).

回答2:

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)