What is the set builder notation for the following two:

a) The set of all binary strings of even length and ending with 1.
b) L* has exactly one more element than L.

I am totally puzzled by these two. Could someone show me the solution to these two problems. An explanation would be great to help me understand.

  • $\begingroup$ How is this computer science? It seems more appropriate for math.se. $\endgroup$ – Yuval Filmus Sep 16 '16 at 21:30
  • $\begingroup$ Please don't delete your question after you've gotten an answer. That's considered impolite, as someone has put time into writing down an answer to your question. We want to build up an archive of good questions and answers that will be useful to others, not just you, and deleting the question prevents others from benefitting from it. Thank you! $\endgroup$ – D.W. Oct 5 '16 at 17:00
  • $\begingroup$ a) asks for a set, but b) is a statement? $\endgroup$ – Hagen von Eitzen Oct 5 '16 at 17:22

Here is one solution:

a) $\{ x \in \{0,1\}^* : \text{$x$ has even length and ends with $1$} \}$

b) $\{ L : \text{$L^*$ has one more element than $L$}\}$

There are many other solutions possible, for example:

a) $\{ x1 : x \in \{0,1\}^* \text{ and } 2 \mid |x1| \}$

b) $\{ L : |L|,|L^*| < \infty \text{ and } |L^*| = |L| + 1 \}$

Note that the condition in b) only holds for $L = \emptyset$; therefore another solution for b) would be $\{ \emptyset \}$.

| cite | improve this answer | |
  • $\begingroup$ $2 | |x1|$ confusing notation... and if in your handwriting $1$ is written $|$... $\endgroup$ – GEdgar Oct 5 '16 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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