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,
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 ...
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.