This book deals with a fascinating and important subject which has the
fundamentals of computer hardware, software and some of their applications.
This book is intended as an introductory graduate text in computer science
theory. I have taken care to present the material very clearly and interestingly.
As an introductory subject to computer science, this book has been written
with major stress on worked examples. Chapter 0 covers the basics required
for this subject viz., sets, relations, functions, graphs, trees, languages, and
fundamental proof techniques.
Chapter 1 deals with the different aspects of Deterministic Finite
Automata (DFA) and Non-Deterministic Finite Automata (NFA). A brief
introduction to pumping lemma and some theorems relating to Regular Sets
have also been given.
Chapter 2 covers the concepts relating to context free grammar viz.,
derivation trees, parsing, ambiguity, and normal forms. Chapter 3 deals with
Pushdown Automata and their relation to Context-Free Grammar with some
introduction to decision algorithms.
Chapter 4 deals with the Turing Machine model and the variations of
Turing Machines with introduction to Church-Turing Thesis and the concept
of undecidability. Chapter 5 explains the concepts viz., regular grammars,
unrestricted grammars and Chomsky hierarchy of languages.
Chapter 6 deals with the different aspects of computability with an
introduction to formal systems, recursive functions, primitive recursive
functions, and recursion. Chapter 7 covers the various aspect of complexity
theory such as polynomial time algorithms, non-polynomial time algorithm
class P and NP problems.
Chapter 8 covers propositions and predicates with lot of illustrative
examples.
I wish to thank my teachers who helped me to get a good grasp of the
subject and for having motivated me to write this book.
I want to place on record my sincere thanks to my family?Shri. Papu
Antony, my father; Mrs. Maria Daisy, my mother; Mrs. Assumpta Eugene, my
wife; and Ms. E. Catherine Praveena, my only daughter, for their great
patience and prayers while I was writing this book.