Mathematical Foundation of Computer Science
Copyright © 2005 New Age International (P) Ltd., Publishers
Published by New Age International (P) Ltd., Publishers
Preface
To understand the fundamentals of computer science it is essential for us to begin with study of
the related mathematical topics ranging from discrete mathematics, concepts of automata theory
and formal languages. It is high time to recognize the importance of discrete mathematics as it
finds various applications in the field of computer science. However, it requires a full fledged
study and its potential with respect to computer sciences and natural sciences have long been
well recognized. To understand the principles of computer science that is evenly acknowledged
as mathematical foundation of computer science, this book present a selection of topics both
from discrete mathematics and from automata theory and formal languages. The objective of
selection of topics was due to my aspiration to commence with most of the fundamental terminology
employed in higher courses in computer science as plausible. As per the requirements of
the study, the formal appearance of the discrete mathematics includes set theory, algebraic
systems, combinatorics, Boolean algebra, propositional logic, and other relevant issues. Likewise,
abstract models of computations, models of computability, language theory concepts, and
the application of language theory ideas are the subject matter of the concepts of automata and
formal languages. These topics will also assist to understand the concepts and philosophies
used in advanced stages of computer learning such as computation theory and computability,
artificial intelligence, switching theory and logic design, design of softwares like high speed
compilers, sophisticated text processors and programming languages, assembly and rescue of
information.
The texts of this book are intended primarily for use in graduate as well as post graduate
courses in ‘Mathematical Foundation of Computer Science’, ‘Discrete Mathematics’ and
‘Automata Theory and Formal Languages’. Although, the topics discussed in the book primarily
focuses on the mathematical aspects of engineering in context of computer science, however it
is also suited to the technical professionals.
Motivation
The manuscript presented in this book is an outcome of the experience gained in the teaching
the courses like discrete mathematics, automata theory, and mathematical foundation of computer
science at Department of Computer Science & Engineering at I E T, UP Technical University,
Lucknow and elsewhere for last ten years. I am hopeful that presentation of this text
imitates the planning of the lectures. I always tried to avoid the mathematical-rigors, complicated
concepts and formalisms and presented them in a more precise and interesting manner.
Moreover, I hope during my teaching students not only learned the courses as a powerful mathematical
tool but also widened their ability and understanding to perceive, devise, and attempt
the mathematical problems with the application of the theory to computer science. The prolific
and valuable feedback from my students motivates me to prepare this manuscript. Ultimately,
I expect that this text would extend the understanding of mathematical theory of computer
science with the explosion of computer science, computer application, engineering, and information
technology.
Feature of the book
The interesting feature of this book is its organization and structure. That consists of
systematizing of the definitions, methods, and results that something resembling a theory.
Simplicity, clarity, and precision of mathematical language makes theoretical topics more
appealing to the readers who are of mathematical or non-mathematical background. For quick
references and immediate attentions—concepts and definitions, methods and theorems, and
key notes are presented through highlighted points from beginning to end. Whenever, necessary
and probable a visual approach of presentation is used. The amalgamation of text and figures
make mathematical rigors easier to understand. Each chapter begins with the detailed contents
which are discussed inside the chapter and conclude with a summary of the material covered in
the chapter. Summary provides a brief overview of all the topics covered in the chapter. To
demonstrate the principles better, the applicability of the concepts discussed in each topic are
illustrated by several examples followed by the practice sets or exercises.
The material of this book is divided into 5 Units that are distributed among 12 chapters.
Unit I gives general overview of discrete objects theory its relations and functions, enumeration,
recurrence relations and algebraic structures. It contains four chapters.
Chapter 1 is a discussion of discrete objects theory its relations and functions. We start
our discussion from the theory of discrete objects which is commonly known as algebra of sets.
The concepts of relations and functions are presented after a discussion of algebra of sets. This
chapter is concluded with the study of natural numbers, Peano axioms and mathematical induction.
Chapter 2 discusses enumeration that includes discrete numeric functions and generating
functions. This chapter covers a class of functions whose domain is the set of natural numbers
and the range is the set of real numbers—better known as discrete numeric functions that
are widely used in digital computations. An alternative way to represent the numeric functions
efficiently and conveniently the reader will also find a discussion over generating function in
the chapter.
Chapter 3 is concerned with recurrence relation and the methods of finding the solution
of the recurrence relation (difference equation). A variety of common recurrences obtained from
the algorithms like divide & conquer and chip & conquer is given. The chapter concludes the
methods to obtain the solution of the recursive procedure codes.
Chapter 4 Latter in this unit we emphasized the algebraic structures where a thorough
discussion of group theory and brief discussion of other algebraic structures like rings and
fields are presented. This discussion is in fact very important in formal language theory and
automata. This chapter concludes with the discussion of class of group mappings like
homomorphism, isomorphism, and automorphism.
Unit II is devoted to the discussion of propositional logic and lattices that are presented
in two chapters.
Oaf! After a successful study of mathematical–rigors, readers find an interesting and
detail overview of logic in Chapter 5. An elementary introduction to logic not only enlightens
the students who are eager to know the role of logic in computer science but equally to other
students of human sciences, philosophy, reasoning, and social sciences as well. A brief discussion
of the theory of inference persuades the criteria to investigate the validity of an argument
is included. In the chapter the stress is mainly on the natural deduction methods to investigate
the validity of an argument instead a lengthy and tedious approach using truth table. Furthermore,
the introduction of predicate logic and inference theory of predicate logic along with a
number of solved examples conclude the chapter.
Chapter 6 deals the Order Theory that includes partial ordered sets (posets) and lattices.
This chapter also covers a detail discussion on lattice properties and its classification
along with a number of solved examples.
Unit III, IV, and V are concerned with automata theory and introduction to formal
languages, which comprises chapters 7, 8–9, and 10–12 correspondingly. Chapter 7 starts
with the study of introduction to the languages and finite automata. The class of finite automata -
deterministic and nondeterministic is included with the definition, representation, and the
discussion of the power of them.
Chapter 8 deals the relationship between the classes of finite automata. Examples are
given to explain better how one form of finite automata is converted to other form of automata
with preservance of power. Of course, a brief illustration of the state minimization problem of
deterministic finite automata concludes the chapter.
Chapter 9 discusses about the regular expressions. Since generalization of regular
expression gives regular language which is the language of the finite automaton. So this chapter
illustrates the relationship between finite automata and regular expressions and vice-versa.
This chapter also introduces another form of finite automata called finite automata with output
such as Melay and Moore machines, which operate on input string and returns some output
string. It also included the discussion on equivalence of Melay and Moore machines.
Chapter 10 deals with regular and non-regular languages. To prove whether any language
is regular or not we discuss a lemma called pumping lemma of regular language. This
lemma is necessarily checking the regularity of the language. The characterizations of regular
languages and decision problems of regular languages are also discussed here.
Chapter 11 begins with the study of grammars. Classification of grammars of type 0,
type 1, type 2, and type 3 are discussed here. A detailed discussion of non-regular grammar
such as context free grammar (type 2) and context free language its characteristics, ambiguity
features are presented in this chapter. The automaton which accepts the context free language
is called pushdown automata. This chapter also discusses about the pushdown automata. Reader
will also find the simplification method of any grammar including normal forms of grammars.
Pumping lemma for proving any language is context free language or not and a brief discussion
on decision problems concludes the chapter.
Chapter 12 deals the study of an abstract machine introduced by Allen Turing called
Turing machine. Turing machine is a more general model of computation in such a way that
any algorithmic procedure that can be carried by human could be possible by a Turing machine.
Chapter includes a brief discussion on this hypothesis usually referred as Church-Turing
hypothesis which laid the theoretical foundation for the modern computer. Variations of Turing
machines and its computing power concluded the study of this chapter.
In Appendix a discussion on Boolean algebra, where reader will find the basic theorems
of Boolean algebra and its most common postulates. A preamble to Boolean function, simplification
of Boolean function and its application in the logic deign of digital computers is presented at last.
http://ifile.it/hmc17kr/282132.rar pass:twilightzone
