Chapter 1. Preliminaries

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

Sets, Relations, and Functions


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,

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}


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

A set ...

Get Introduction to Formal Languages, Automata Theory and Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.