dharm
d:\N-com\TITLE.pm5 vii
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 discus-
sion 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. Further-
more, 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 lat-
tices. 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 lan-
guage 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, simplifica-
tion of Boolean function and its application in the logic deign of digital computers is presented
at last.( viii )