Introduction to Automata Theory, Languages, and Computation, 2/E
Publisher: Addison Wesley;
Author: John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman
Edition: 2 edition (November 24, 2000)
Format: PDF
ISBN: 0201441241
EAN: 978-0201441246
No.ofPages: 521
Book Description:
It has been more than 20 years since this classic book on formal languages, automata theory, and computational complexity was first published. With this long-awaited revision, the authors continue to present the theory in a concise and straightforward manner, now with an eye out for the practical applications. They have revised this book to make it more accessible to today's students, including the addition of more material on writing proofs, more figures and pictures to convey ideas, side-boxes to highlight other interesting material, and a less formal writing style. Exercises at the end of each chapter, including some new, easier exercises, help readers confirm and enhance their understanding of the material.
Table of Contents:
The purpose of this course is to acquaint the student with an overview of the theoretical foundations
of computer science from the perspective of formal languages.
• Classify machines by their power to recognize languages.
• Employ finite state machines to solve problems in computing.
• Explain deterministic and non-deterministic machines.
• Comprehend the hierarchy of problems arising in the computer sciences.
UNIT I :
Fundamentals : Strings, Alphabet, Language, Operations, Finite state machine, definitions, finite
automaton model, acceptance of strings, and languages, deterministic finite automaton and non
deterministic finite automaton, transition diagrams and Language recognizers.
UNIT II :
Finite Automata : NFA with Î transitions - Significance, acceptance of languages. Conversions and
Equivalence : Equivalence between NFA with and without Î transitions, NFA to DFA conversion,
minimisation of FSM, equivalence between two FSM’s, Finite Automata with output- Moore and Melay
machines.
UNIT III :
Regular Languages : Regular sets, regular expressions, identity rules, Constructing finite Automata for a
given regular expressions, Conversion of Finite Automata to Regular expressions. Pumping lemma of
regular sets, closure properties of regular sets (proofs not required).
UNIT IV :
Grammar Formalism : Regular grammars-right linear and left linear grammars, equivalence between
regular linear grammar and FA, inter conversion, Context free grammar, derivation trees, sentential forms.Right most and leftmost derivation of strings.
UNIT V :
Context Free Grammars : Ambiguity in context free grammars. Minimisation of Context Free Grammars.Chomsky normal form, Greiback normal form, Pumping Lemma for Context Free Languages. Enumeration of properties of CFL (proofs omitted).
UNIT VI :
Push Down Automata : Push down automata, definition, model, acceptance of CFL, Acceptance by final state and acceptance by empty state and its equivalence. Equivalence of CFL and PDA, interconversion.(Proofs not required). Introduction to DCFL and DPDA.
UNIT VII :
Turing Machine : Turing Machine, definition, model, design of TM, Computable functions, recursively
enumerable languages. Church’s hypothesis, counter machine, types of Turing machines (proofs not
required).
UNIT VIII
Computability Theory : Chomsky hierarchy of languages, linear bounded automata and context sensitive language, LR(0) grammar, decidability of, problems, Universal Turing Machine, undecidability of posts. Correspondence problem, Turing reducibility, Definition of P and NP problems, NP complete and NP hard problems.
------> Download Here
