Nagpal

Formal Languages and Automata Theory

• Broschiertes Buch

Produktbeschreibung

Theory of Automata is designed to serve as a textbook for undergraduate students of B..E, B.Tech. CSE and MCA/IT. It attempts to help students grasp the essential concepts involved in automata theory.

Produktdetails

• Verlag: Oxford University Press, USA
• Seitenzahl: 380
• Erscheinungstermin: 2. August 2012
• Englisch
• Abmessung: 234mm x 180mm x 18mm
• Gewicht: 517g
• ISBN-13: 9780198071068
• ISBN-10: 019807106X
• Artikelnr.: 43487372

Autorenporträt

Chander Kumar Nagpal is currently working as Assistant Professor in YMCA University of Science & Technology, Faridabad. A PhD in computer science from Jamia Milia Islamia University he has close to 30 years of teaching experience. An expert in his field, Chander Kumar Nagpal has designed course materials on subjects such as Computer Programming, Artificial Intelligence, and System Analysis and Design for Indian Society for Technical Education (ISTE). He has also published several research papers in various journals of national and international repute.

Inhaltsangabe

*
* AUTOMATA, FORMAL LANGUAGES AND COMPUTABILITY
* 1.1 Formal Languages
* 1.1.1 Phrase Structure Grammars
* 1.2 Chomsky Classification of Grammars
* 1.3 Computability
* Supplementary Examples
* A Quick Review
* Problems for Practice
* Objective Type Questions
*
* MATHEMATICAL PRELIMINARIES
* 2.1 Set Theory
* 2.2 Relations
* 2.2.1 Types of Relations
* 2.3 Functions
* 2.4 Counting Techniques
* 2.4.1 Permutations
* 2.4.2 Combinations
* 2.4.3 Pigeonhole Principle
* 2.5 Logic
* 2.5.1 Propositions and Logic
* 2.6 Methods of Proof
* 2.6.1 Direct Proof
* 2.6.2 Indirect Proof
* Supplementary Examples
* A Quick Review
* Problems for Practice
* Objective Type Questions
*
* FINITE AUTOMATA
* 3.1 Finite Automata
* 3.1.1 String processing by finite automaton
* 3.2 Properties of transition function
* 3.3 Deterministic and Nondeterministic Finite Automaton
* 3.3.1 Acceptance of a string by NFA
* 3.4 Equivalence of NFA and DFA
* 3.4.1 Converting a NFA to equivalent DFA
* 3.4.2 Equivalence of DFAs
* 3.5 Level Equivalence and Reduction in Finite Automaton
* 3.6 Finite automata with outputs
* 3.6.1 Moore and Mealy Machines
* 3.6.2 Conversion of a Moore Machine to equivalent Mealy Machine
* 3.6.3 Conversion of a Mealy Machine to equivalent Moore Machine
* 3.7 Finite automata with null moves
* 3.7.1 Removal of null moves
* Supplementary Examples
* A Quick Review
* Problems for Practice
* Objective Type Questions
*
* REGULAR SETS AND REGULAR GRAMMAR
* 4.1 Regular Expression
* 4.2 Correspondence between regular expression and regular set
* 4.3 Identities related to regular expressions
* 4.4 Relation between Regular Languages and Finite Automata
* 4.4.1 Finite automaton corresponding to regular expression
* 4.4.2 Regular expression corresponding to finite automaton
* 4.5 Closure properties of regular sets
* 4.6 Automata for union, intersection and difference of languages
* 4.7 Pumping Lemma for regular Languages
* 4.7.1 Applications of pumping lemma
* 4.7.2 Suitability of pumping lemma
* 4.8 Production System associated with regular grammar
* 4.9 Myhill Nerode Theorem (Equivalent Classes and Regular Languages)
* 4.10 Some Decision Problems related to Finite Automata and Regular
Langauges
* 4.11 Regular language and current programming language scenario
* Supplementary Examples
* A Quick Overview
* Problems for Practice
* Objective Type Questions
*
* CONTEXT FREE GRAMMARS AND LANGUAGES
* 5.1 Some example recursive grammars
* 5.2 Context Free Grammars
* 5.2.1 Leftmost and Rightmost Derivation of a string
* 5.2.2 Some example context free languages and grammars
* 5.2.3 Ambiguity in Context Free Grammar and Parse Tree
* 5.2.4 Possible defects in CFG and their removal
* 5.2.4.1 Failure of non terminal(s) to generate terminal(s)
* 5.2.4.2 Problem of unit productions
* 5.2.4.3 Problem of unreachable non terminal
* 5.2.4.4 Problem of null productions
* 5.3 Context Free languages as superset of regular languages
* 5.4 Closure properties of Context Free languages
* 5.4.1 Intersection of a CFL and a regular language
* 5.5 Normal Forms for CFGs
* 5.5.1 Chomsky Normal Form
* 5.5.2 Greibach Normal Form
* 5.6 Pumping lemma for Context Free Grammars
* 5.6.1 Applications of pumping lemma
* 5.7 More on closure properties
* 5.7 Applications of Context Free Grammars
* 5.7.1 Programming language Constructs
* 5.7.2 Natural Language
* 5.7.3 Markup Languages
* Supplementary Examples
* A Quick Overview
* Problems for Practice
* Objective Type Questions
*
* PUSHDOWN AUTOMATA
* 6.1 Basic Structure of Pushdown Automata
* 6.2 Two types of acceptance by PDA
* 6.3 Correspondence between PDA and CFL
* 6.3.1 PDA corresponding to a given CFG
* 6.3.2 CFG corresponding to a given PDA
* 6.4 Parsing and PDA
* 6.4.1 Design of Top Down Parser
* 6.4.2 Design of a Bottom up Parser
* Supplementary Examples
* A Quick Overview
* Problems for Practice
* Objective Type Questions
*
* TURING MACHINES
* 7.1 Basic structure and working of a Turing Machine
* 7.2 Instantaneous Description of a Turing Machine
* 7.3 Language of a Turing machine
* 7.4 Turing Machine as computer for positive integers
* 7.5 Universal Turing machine (UTM)
* 7.5.1 UTM and Modern Day Computer
* 7.6 Enhancements in Turing Machine
* 7.6.1 Multi-track Turing Machine
* 7.6.2 Multi-tape Turing Machine
* 7.7 Turing Machine as Enumerator
* 7.8 Non-Deterministic and Deterministic Turing machine
* 7.9 lternative representations of Turing Machines
* 7.9.1 Turing Machine with semi infinite Tape
* 7.9.2 Two stack machine
* 7.10 Time and Space Complexity of a Turing Machine
* 7.11 Some other machines
* 7.11.1 Linear Bound Automata
* 7.11.2 Post Machine
* Supplementary Examples
* A Quick Overview
* Problems for Practice
* Objective Type Questions
*
* THE PITFALL OF ALGORITHMIC COMPUTING: UNDECIDABILITY
* 8.1 Recursive and Non Recursive Languages
* 8.2 Language of Turing machines
* 8.3 Some decision problems relating to Turing Machines
* 8.4 Some Decision Problems relating to CFG
* 8.5 Post Correspondence Problem
* 8.5.1 Constructing CFG using PCP
* Supplementary Examples
* A Quick Overview
* Problems for Practice
* Objective Type Questions
*
* COMPUTABLE FUNCTIONS
* 9.1 Primitive Recursive Functions
* 9.2 µ Recursive Functions
* 9.2.1 Computability and µ Recursive Functions
* Supplementary Examples
* A Quick Overview
* Problems for Practice
* Objective Type Questions
*
* COMPUTATIONAL COMPLEXITY: TRACTABLE AND POSSIBLY INTRACTABLE PROBLEMS
* 10.1 Growth Rates of Functions
* 10.2 Languages and complexity classes
* 10.3 Decision Problems and Optimization Problems
* 10.4 The classes P and NP
* 10.5 NP Complete Problems
* 10.6 Significance of discovering NP complete problems
* 10.7 Some misconceptions about NP-complete problems
* Supplementary Examples
* A Quick Overview
* Problems for Practice
* Objective Type Questions
* APPENDIX A
* Church-Turing hypothesis
* APPENDIX B
* Godel Numbering
* APPENDIX C
* Homage to key scientists in the field of automata theory and
computation
* APPENDIX D
* Chronology of Some Important Events