Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$.

This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. The author provides the following answer: $\overline L = \{\lambda, a, b, ab, ba\} \cup \{ w \in \{a, b\}^+ : |w|\geq 3\}$. Mine on the other hand is the following: $\overline L = \Sigma^* - L = \{w \in \Sigma^* : w \neq aa, w \neq bb\}$. Is my answer wrong? Thanks in advance.

  • 2
    $\begingroup$ What is meant by "set notation"? Your answer is what I would write. Anyway, representation is definitely not unique and I wouldn't care that much about it. $\endgroup$
    – user114966
    Feb 14, 2021 at 21:40
  • $\begingroup$ Your answer is not wrong, but the book's answer makes it easier to write a regular expression or regular grammar. $\endgroup$
    – rici
    Feb 14, 2021 at 21:55
  • $\begingroup$ Alright then. Thanks! $\endgroup$ Feb 14, 2021 at 22:01

1 Answer 1


You already got your answer in the comments: both the solutions provided solve the task. The only thing in which they differ is from which angle the attempt to solve the task. The author one goes from an empty set and adds only words that satisfy the given constraints (bottom-up approach). Yours goes from the set of all possible words and removes the ones that do not satisfy the constraint (top-down approach).

I would say his is more accurate IF you are not allowed to use $L$ or $\Sigma$, as it is often the case in exercise text books.


Your Answer

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

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