An Introduction to Formal Languages and Automata, 7th Edition

1.1 MATHEMATICAL PRELIMINARIES AND NOTATION

Sets

A set is a collection of elements, without any structure other than membership. To indicate that x is an element of the set S, we write x ∈ S. The statement that x is not in S is written x ∉ S. A set can be specified by enclosing some description of its elements in curly braces; for example, the set of integers 0, 1, 2 is shown as

$$S=\left\{0,1,2\right\}.$$

Ellipses are used whenever the meaning is clear. Thus, {a, b, …, z} stands for all the lowercase letters of the English alphabet, while {2,4,6, …} denotes the set of all positive even integers. When the need arises, we use more explicit notation, in which we write

$S=\left\{i:i>0,i\text{ is even}\right\}$

(1.1)

for the last example. We read this as “S is the set of all ...