- ホーム
- > 洋書
- > 英文書
- > Computer / Languages
Full Description
Formal Language and Automata Theory 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.
The book starts with basic concepts such as discrete mathematical structures and fundamentals of automata theory, which are prerequisites for understanding further topics. Description of important topics such as regular sets and grammar, context free languages, and various types of automata such as DFA, NDFA, push down, LBA, and Turing Machine is then taken up in detail. Special emphasis is laid on design and applications of Turing Machines. Finally, the book focuses on decidability factor of recursively enabled languages and the complexity problem dealing with the relation between P and NP classes.
Written in a lucid and student-friendly manner the book contains a large number of solved examples. Each chapter consists of a set of chapter-end exercises, which aid students in acquiring better understanding of the concepts. It also provides appendices on Church-Turing thesis, Godel numbering, chronology of some important events, and a write-up paying homage to all the scientists who have contributed significantly in shaping this subject area to its present form.
Contents
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
