Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to describe the set of all words in the following format: a0w1

where a represents EITHER 0 or 1, and w represents {0,1}*

So 00011 is valid as is 1010011, etc. etc.

I'm really new to set notation, so I'm not sure what I can do.

Is L = {a,0,w,1 | a = 0 or 1, w $\in$ {0,1}*} valid for what I want to describe?


share|improve this question

1 Answer 1

up vote 1 down vote accepted

You can describe that set in many ways. For instance, it corresponds to the regular expression $(0\lor 1)0(0\lor 1)^*1$ (in one common formalism for regular expressions). However, if you want to describe it as a set of strings using standard set notation, you want something like

$$\Big\{a0w1\in\{0,1\}^*:a\in\{0,1\}\text{ and }w\in\{0,1\}^*\Big\}\;.$$

In particular, you don’t want the commas: words over an alphabet are normally written without, unless some of the symbols in the alphabet require more than one typographical symbol to represent them.

share|improve this answer
Thank you very much! –  pauliwago Jul 19 '12 at 6:25
Actually, why is the first $\in$ {0,1}* necessary? Could it have been written as {a0w1 | a $\in$ {0,1} and w $\in$ {0,1}*} ? Also, does the : and | have the same meaning? –  pauliwago Jul 19 '12 at 6:28
@pauliwago: Yes, the colon and the vertical bar have the same meaning; I prefer the colon, since the bar is used to mean so many other things. The $\in\{0,1\}^*$ before the colon is not strictly speaking necessary, but I consider it good practice to specify the set from which the objects one is collecting will be drawn. (In abstract set theory it’s technically necessary to do so, and I’m in the habit of doing it more generally.) –  Brian M. Scott Jul 19 '12 at 6:34
OK got it, thanks –  pauliwago Jul 19 '12 at 6:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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