Introduction to Formal Languages, Automata Theory and Computation

Chapter 1. Preliminaries

In this chapter, we review some basic concepts required for understanding the contents of this book.

Sets, Relations, and Functions

Sets

A set is a collection of well-defined objects. Usually the elements of a set have common properties. For example, all the students who enroll for a course ‘Computability’ make up a set. Formally,

Definition 1.1

A set is an unordered collection of objects.

Note that the definition of a set is intuitive in nature and was stated by the German mathematician Cantor in 1895. The objects in a set are called the elements or members of the set.

Example 1.1. 

The set E of even positive integers less than 20 can be expressed by:

E = {2, 4, 6, 8, 10, 12, 14, 16, 18}

or

E = {x|x is even and 0 < x < 20}

A set ...