3
$\begingroup$

Given a $\Sigma$ I define a regular language as one of the folllows:

  • $\emptyset$
  • $\left\{ \sigma \right\}$ for any $\sigma \in \Sigma$
  • $L_1 \cup L_2$ for regular $L_1, L_2$
  • $L_1 \cdot L_2 $ for regular $L_1,L_2$
  • $L^*$ for regular $L$

Now, I would like to show that for a given regular language $L$, its complement $\overline{L}$ is regular as well. I want to do so based only on this definition (i.e. without proving its equivalent to DFA, NFA or reg expression).

However, I'm having a bit of trouble here, not sure how to do so. Maybe I want to express the complement of $L$ as a sort of unions/contactinations? Not really sure how to go for it. Any ideas?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Your definition is the same as the usual definition with regular expressions. While regular expressions also admit the empty word $\epsilon$, it is expressible as $\emptyset^*$.

There is no simple rule for complementing regular expressions, and it is known that such complementation can result in an exponential blow-up (for example, the language of all words not containing all alphabet symbols has a regular expression of size $O(|\Sigma|^2)$, but its complement requires a regular expression of length exponential in $|\Sigma|$).

$\endgroup$
2
  • $\begingroup$ So there's no way of proving $\overline{L}$ is regular without a DFA/NFA? $\endgroup$
    – Eric_
    Nov 2, 2021 at 12:21
  • $\begingroup$ None that I’m aware of. $\endgroup$ Nov 2, 2021 at 12:23
1
$\begingroup$

Complement means relative complement $Σ^* - L$. You already have closure under set subtraction and, in fact, also intersection and even interleave. So, the real question is how to do set-subtraction.

You can evaluate it algebraically, but you get a system that amounts to the description of a deterministic automaton. I will only illustrate it with a couple of examples, one of which will involve the relative complement with respect to $Σ^*$, where $Σ = \{a,b\}$.

Example 1: $a b^* a - (ab)^*a$:
Set $A = a b^* a - (ab)^*a$. Using the identity $x^*y = y + x x^* y$, we write $$A = a b^* a - (a + a b (a b)^* a) = a\left(b^* a - 1 - b (a b)^* a\right) = a B,$$ where $B = b^* a - 1 - b (a b)^* a$ and $1$ denotes the empty word.

The set-theoretic subtraction of $1$ is trivial since $b^* a$ does not contain the empty word. Therefore, we can write $B = b^*a - b (a b)^* a$. Thus, continuing on, we have $$B = a + b b^* a - b (a b)^* a = a + b\left(b^* a - (a b)^* a\right) = a C + b D,$$ where, $C = 1$ and $D = b^* a - (a b)^* a$.

For $D$, we have $$D = a + b b^* a - a - a b (a b)^* a = a\left(1 - 1 - b (a b)^* a\right) + b b^* a = b b^* a,$$ since the set-theoretic identity holds $x - x - y = 0 - y = 0$.

The resulting system $$A ≥ a B, B ≥ a C + b D, C ≥ 1, D ≥ b b^* a,$$ has to be written as a system of inequalities to avoid infinite regresses that occur if repeats of terms appear on the right-hand side (e.g. an equation like $D = ⋯ + D + ⋯$); and it is the least solution we seek out.

Solving for $(C,D)$ immediately yield the results $(C,D) = \left(1, b b^* a\right)$. Substituting into the other two inequalities yields $$A ≥ a B, B ≥ a + b b b^* a = \left(1 + b b b^*\right) a,$$ whose least solution is $$(A,B) = \left(a \left(1 + b b b^*\right) a, \left(1 + b b b^*\right) a\right).$$

The corresponding automaton has states $A$, $B$, $C$, $D$, plus whatever other states result from reducing the expression for $D$ to a system of inequalities. The start state is $A$, and $C$ is a final state, plus whatever other final state might come from the subsystem headed by $D$. (There are none. The subsystem headed by $D$ leads back to $C$ as its sole final state.) The expression of interest is that for $A$, and we can thus write $$ab^*a - (ab)^*a = a\left(1 + b b b^*\right)a.$$

Example 2: $(a + b)^* - (a + b)^* b b (a + b)^*$
Setting this expression to $A$, you can write $$A = 1 + a A + b \left(A - b (a + b)^*\right) = 1 + a A + b B,$$ where $B = A - b (a + b)^*$. In-line substituting this expression for $A$ into $B$ yields $$B = 1 + a A + b \left(B - (a + b)^*\right) = 1 + a A.$$ The last equality follows from the identity $f(a,b) - (a + b)^* = 0$, for any regular expression $f(a,b)$ in $a$ and $b$, since the set corresponding to $(a + b)^*$ is maximal. Thus, the corresponding system is $$A ≥ 1 + a A + b B, B ≥ 1 + a A,$$ which, upon in-line substitution of the expression for $B$ into $A$, yields $$A ≥ 1 + a A + b + b a A = 1 + b + (a + b a) A,$$ whose least solution is $A = (a + b a)^* (1 + b)$. Thus, $$(a + b)^* - (a + b)^* b b (a + b)^* = (a + b a)^* (1 + b).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.