Formal Languages and Automata Theory
Home > Computing and Information Technology > Computer programming / software engineering > Programming and scripting languages: general > Formal Languages and Automata Theory
Formal Languages and Automata Theory

Formal Languages and Automata Theory


     0     
5
4
3
2
1



Available


X
About the Book

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.

Table of 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

About the Author :
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.


Best Sellers


Product Details
  • ISBN-13: 9780198071068
  • Publisher: OUP India
  • Publisher Imprint: OUP India
  • Height: 241 mm
  • No of Pages: 380
  • Spine Width: 18 mm
  • Width: 185 mm
  • ISBN-10: 019807106X
  • Publisher Date: 24 Apr 2012
  • Binding: Paperback
  • Language: English
  • Returnable: Y
  • Weight: 514 gr


Similar Products

Add Photo
Add Photo

Customer Reviews

REVIEWS      0     
Click Here To Be The First to Review this Product
Formal Languages and Automata Theory
OUP India -
Formal Languages and Automata Theory
Writing guidlines
We want to publish your review, so please:
  • keep your review on the product. Review's that defame author's character will be rejected.
  • Keep your review focused on the product.
  • Avoid writing about customer service. contact us instead if you have issue requiring immediate attention.
  • Refrain from mentioning competitors or the specific price you paid for the product.
  • Do not include any personally identifiable information, such as full names.

Formal Languages and Automata Theory

Required fields are marked with *

Review Title*
Review
    Add Photo Add up to 6 photos
    Would you recommend this product to a friend?
    Tag this Book Read more
    Does your review contain spoilers?
    What type of reader best describes you?
    I agree to the terms & conditions
    You may receive emails regarding this submission. Any emails will include the ability to opt-out of future communications.

    CUSTOMER RATINGS AND REVIEWS AND QUESTIONS AND ANSWERS TERMS OF USE

    These Terms of Use govern your conduct associated with the Customer Ratings and Reviews and/or Questions and Answers service offered by Bookswagon (the "CRR Service").


    By submitting any content to Bookswagon, you guarantee that:
    • You are the sole author and owner of the intellectual property rights in the content;
    • All "moral rights" that you may have in such content have been voluntarily waived by you;
    • All content that you post is accurate;
    • You are at least 13 years old;
    • Use of the content you supply does not violate these Terms of Use and will not cause injury to any person or entity.
    You further agree that you may not submit any content:
    • That is known by you to be false, inaccurate or misleading;
    • That infringes any third party's copyright, patent, trademark, trade secret or other proprietary rights or rights of publicity or privacy;
    • That violates any law, statute, ordinance or regulation (including, but not limited to, those governing, consumer protection, unfair competition, anti-discrimination or false advertising);
    • That is, or may reasonably be considered to be, defamatory, libelous, hateful, racially or religiously biased or offensive, unlawfully threatening or unlawfully harassing to any individual, partnership or corporation;
    • For which you were compensated or granted any consideration by any unapproved third party;
    • That includes any information that references other websites, addresses, email addresses, contact information or phone numbers;
    • That contains any computer viruses, worms or other potentially damaging computer programs or files.
    You agree to indemnify and hold Bookswagon (and its officers, directors, agents, subsidiaries, joint ventures, employees and third-party service providers, including but not limited to Bazaarvoice, Inc.), harmless from all claims, demands, and damages (actual and consequential) of every kind and nature, known and unknown including reasonable attorneys' fees, arising out of a breach of your representations and warranties set forth above, or your violation of any law or the rights of a third party.


    For any content that you submit, you grant Bookswagon a perpetual, irrevocable, royalty-free, transferable right and license to use, copy, modify, delete in its entirety, adapt, publish, translate, create derivative works from and/or sell, transfer, and/or distribute such content and/or incorporate such content into any form, medium or technology throughout the world without compensation to you. Additionally,  Bookswagon may transfer or share any personal information that you submit with its third-party service providers, including but not limited to Bazaarvoice, Inc. in accordance with  Privacy Policy


    All content that you submit may be used at Bookswagon's sole discretion. Bookswagon reserves the right to change, condense, withhold publication, remove or delete any content on Bookswagon's website that Bookswagon deems, in its sole discretion, to violate the content guidelines or any other provision of these Terms of Use.  Bookswagon does not guarantee that you will have any recourse through Bookswagon to edit or delete any content you have submitted. Ratings and written comments are generally posted within two to four business days. However, Bookswagon reserves the right to remove or to refuse to post any submission to the extent authorized by law. You acknowledge that you, not Bookswagon, are responsible for the contents of your submission. None of the content that you submit shall be subject to any obligation of confidence on the part of Bookswagon, its agents, subsidiaries, affiliates, partners or third party service providers (including but not limited to Bazaarvoice, Inc.)and their respective directors, officers and employees.

    Accept

    New Arrivals


    Inspired by your browsing history


    Your review has been submitted!

    You've already reviewed this product!