Formal Languages and Automata Theory/
Nagpal,C.K.
- New York: Oxford University Press, 2012.
- 348
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