|Publishers||R. Narain & Co.|
|Author||Nobel Editorial Board|
|Subject||Theory of Automata & Formal Languages|
Theory of Automata & Formal Languages – MCA (201)
This book is designed to meet the needs of master of computer application students studying for the very first time in their curriculum. Thus complexity of the matter has been avoided with a view that complete course content has to be completed by the student in limited time period. The subject matter has been presented in a lucid, comprehensive and systematic manner which is easy to understand and also develops writing ability for students to score good marks in upcoming examination. This book includes all types of questions according to new pattern of university. Course content has been divided into topic wise and in chapter wise form according to curriculum framed by Dr. A.P.J. Abdul Kalam Technical University, Lucknow. This book includes unsolved papers of last years and sample paper. We hope that this book will be successful in its objectives and will receive appreciation from students and teachers alike.
Estimated Delivery for Urban Areas 3 to 4 Days
Estimated Delivery for Rural Areas 5 to 7 Days
|Dimensions||20 × 12 × 1 cm|
Table of Content
Unit I – Basic Concepts and Automata Theory: Introduction to Theory of Computation- Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA)- Definition, Representation, Acceptability of a String and Language, Non Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with å-Transition, Equivalence of NFA’s with and without å-Transition, Finite Automata with output- Moore machine, Mealy Machine, Equivalence of Moore and Mealy Machine, Minimization of Finite Automata, Myhill-Nerode Theorem, Simulation of DFA and NFA.
UNIT II – Regular Expressions and Languages: Regular Expressions, Transition Graph, Kleen’s Theorem, Finite Automata and Regular Expression-Arden’s theorem, Algebraic Method Using Arden’s Theorem, Regular and Non-Regular Languages- Closure properties of Regular Languages, Pigeonhole Principle, Pumping Lemma, Application of Pumping Lemma, Decidability- Decision properties, Finite Automata and Regular Languages, Regular Languages and Computers, Simulation of Transition Graph and Regular language.
UNIT III – Regular and Non-Regular Grammars: Context FreeGrammar(CFG)-Definition, Derivations, Languages, Derivation Trees and Ambiguity, Regular Grammars-Right Linear and Left Linear grammars, Conversion of FA into CFG and Regular grammar into FA, Simplification of CFG, Normal Forms- Chomsky Normal Form(CNF), Greibach Normal Form (GNF),Chomsky Hierarchy, Programming problems based on the properties of CFGs.
UNIT IV – Push Down Automata and Properties of Context Free Languages: Nondeterministic Pushdown Automata (NPDA)- Definition, Moves,A Language Accepted by NPDA, Deterministic PushdownAutomata(DPDA) and Deterministic Context free Languages(DCFL), Pushdown Automata for Context Free Languages, Context Free grammars for Pushdown Automata, Two stack Pushdown Automata, Pumping Lemma for CFL, Closure properties of CFL, Decision Problems of CFL, Programming problems based on the properties of CFLs.
UNIT V – Turing Machines and Recursive Function Theory : Basic Turing Machine Model, Representation of Turing Machines, Language Acceptability of Turing Machines, Techniques for Turing Machine Construction, Modifications of Turing Machine, Turing Machine as Computer of Integer Functions, Universal Turing machine, Linear Bounded Automata, Church’s Thesis, Recursive and Recursively Enumerable language, Halting Problem, Post Correspondence Problem, Introduction to Recursive Function Theory.
Salient features include:
- Comprehensive coverage of theoretical aspects in easiest way through diagrams and flow charts.
- All intricate aspects are explained by simple, lucid and specific explanations and substantiated with neat and elaborate diagrammatic sketches.