that will be required. While intuition will frequently be our guide in exploring
ideas, the conclusions we draw will be based on rigorous arguments. This will
involve some mathematical machinery, although the requirements are not
extensive. The reader will need a reasonably good grasp of the terminology and
of the elementary results of set theory, functions, and relations. Trees and graph
structures will be used frequently, although little is needed beyond the definition
of a labeled, directed graph. Perhaps the most stringent requirement is the ability
to follow proofs and an understanding of what constitutes proper mathematical
reasoning. This includes familiarity with the basic proof techniques of deduction,
induction, and proof by contradiction. We will assume that the reader has this
necessary background. Section 1.1 is included to review some of the main results
that will be used and to establish a notational common ground for subsequent
discussion.
In Section 1.2, we take a first look at the central concepts of languages,
grammars, and automata. These concepts occur in many specific forms
throughout the book. In Section 1.3, we give some simple applications of these
general ideas to illustrate that these concepts have widespread uses in computer
science. The discussion in these two sections will be intuitive rather than
rigorous. Later, we will make all of this much more precise; but for the moment,
the goal is to get a clear picture of the concepts with which we are dealing.
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 = {0, 1, 2}.
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
ideas, the conclusions we draw will be based on rigorous arguments. This will
involve some mathematical machinery, although the requirements are not
extensive. The reader will need a reasonably good grasp of the terminology and
of the elementary results of set theory, functions, and relations. Trees and graph
structures will be used frequently, although little is needed beyond the definition
of a labeled, directed graph. Perhaps the most stringent requirement is the ability
to follow proofs and an understanding of what constitutes proper mathematical
reasoning. This includes familiarity with the basic proof techniques of deduction,
induction, and proof by contradiction. We will assume that the reader has this
necessary background. Section 1.1 is included to review some of the main results
that will be used and to establish a notational common ground for subsequent
discussion.
In Section 1.2, we take a first look at the central concepts of languages,
grammars, and automata. These concepts occur in many specific forms
throughout the book. In Section 1.3, we give some simple applications of these
general ideas to illustrate that these concepts have widespread uses in computer
science. The discussion in these two sections will be intuitive rather than
rigorous. Later, we will make all of this much more precise; but for the moment,
the goal is to get a clear picture of the concepts with which we are dealing.
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 = {0, 1, 2}.
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