2
$\begingroup$

The question is relates to languages in automata theory. Give an example of a language W such that W∗ has exactly one more element than W.

My guess is that the answer to this problem is the empty set (∅). Since the star of the empty set is {e}, that makes it one element bigger.

Am I correct? My other guess is that it is an infinite set, but I have no idea how to represent an infinite set on paper.

Thanks very much.

$\endgroup$
3
$\begingroup$

Your answer is correct. For an infinite example, try the set $A=\{a\}^*\setminus\{\epsilon\}$, sometimes written $\{a\}^+$: this is the set of all non-empty strings of $a$’s.

This example and yours are just instances of a more general observation: if $W$ is any language such that $\epsilon\notin W$ and $W$ is closed under concatenation, then $W^*=W\cup\{\epsilon\}$.

$\endgroup$
  • $\begingroup$ @user1305850: You’re very welcome. $\endgroup$ – Brian M. Scott Sep 19 '13 at 2:56

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.