0
$\begingroup$

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?

Thanks!

1 Answers 1

1

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.

  • 0
    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?2012-07-19
  • 0
    @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.)2012-07-19
  • 0
    OK got it, thanks2012-07-19