An introduction to formal languages and automata / (Record no. 2358)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 05590cam a2200205 a 4500 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 0763737984 (casebound) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9780763737986 |
| 040 ## - CATALOGING SOURCE | |
| Transcribing agency | CUS |
| 082 00 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 005.13/1 |
| Item number | LIN/F |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Linz, Peter. |
| 245 13 - TITLE STATEMENT | |
| Title | An introduction to formal languages and automata / |
| Statement of responsibility, etc. | Peter Linz. |
| 250 ## - EDITION STATEMENT | |
| Edition statement | 4th ed. |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Place of publication, distribution, etc. | Sudbury, Mass. : |
| Name of publisher, distributor, etc. | Jones and Bartlett Publishers, |
| Date of publication, distribution, etc. | c2006. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | xiii, 415 p. : |
| Other physical details | ill. ; |
| Dimensions | 25 cm. |
| 504 ## - BIBLIOGRAPHY, ETC. NOTE | |
| Bibliography, etc | Includes bibliographical references (p. 409) and index. |
| 505 ## - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Introduction to the Theory of Computation<br/>1.1 Mathematical Preliminaries and Notation<br/>Sets<br/>Functions and Relations<br/>Graphs and Trees<br/>Proof Techniques<br/>1.2 Three Basic Concepts<br/>Languages<br/>Grammars<br/>Automata<br/>1.3 Some Applications*<br/>Finite Automata<br/>2.1 Deterministic Finite Accepters<br/>Deterministic Accepters and TVansition Graphs<br/>Languages and Dfa's<br/>Regular Languages<br/>2.2 Nondeterministic Finite Accepters<br/>Definition of a Nondeterministic Accepter<br/>Why Nondeterminism?<br/>2.3 Equivalence of Deterministic and Nondeterministic Finite*<br/>Accepters<br/>2.4 Reduction of the Number of States in Finite Automata* .<br/>3 Regular Languages and Regular Grammars<br/>3.1 Regular Expressions<br/>Formal Definition of a Regular Expression<br/>Languages Associated with Regular Expressions<br/>3.2 Connection Between Regular Expressions and Regular<br/>Languages<br/>Regular Expressions Denote Regular Languages<br/>Regular Expressions for Regular Languages<br/>Regular Expressions for Describing Simple Patterns<br/>3.3 Regular Grammars<br/>Right- and Left-Linear Grammars<br/>Right-Linear Grammars Generate Regular Languages<br/>Right-Linear Grammars for Regular Languages<br/>Equivalence of Regular Languages and Regular<br/>Grammars .<br/>4 Properties of Regular Languages<br/>4.1 Closure Properties of Regular Languages<br/>Closure under Simple Set Operations<br/>Closure under Other Operations<br/>4.2 Elementary Questions about Regular Languages<br/>4.3 Identifying Nonregular Languages<br/>Using the Pigeonhole Principle<br/>A Pumping Lemma<br/>5 Context-Free Languages<br/>5.1 Context-Free Grammars<br/>Examples of Context-Free Languages<br/>Leftmost and Rightmost Derivations<br/>Derivation Trees<br/>Relation between Sentential Forms and Derivation<br/>Trees<br/>5.2 Parsing and Ambiguity<br/>Parsing and Membership<br/>Ambiguity in Grammars and Languages<br/>5.3 Context-Free Grammars and Programming Languages<br/>6 Simplification of Context-Free Grammars and Normal<br/>Forms<br/>6.1 Methods for Transforming Grammars<br/>A Useful Substitution Rule<br/>Removing Useless Productions<br/>Removing A-Productions<br/>Removing Unit-Productions<br/>6.2 Two Important Normal Forms<br/>Chomsky Normal Form<br/>Greibach Normal Form<br/>6.3 A Membership Algorithm for Context-Free Grammars*<br/>7 Pushdown Automata<br/>7.1 Nondeterministic Pushdown Automata<br/>Definition of a Pushdown Automaton<br/>The Language Accepted by a Pushdown Automatoi<br/>7.2 Pushdown Automata and Context-Free Languages<br/>Pushdown Automata for Context-Free Languages<br/>Context-Free Grammars for Pushdown Automata<br/>7.3 Deteritiinistic Pushdown Automata and Deterministic<br/>Context-Free Languages<br/>7.4 Grammars for Deterministic Context-Free Languages*<br/>8 Properties of Context-Free Languages<br/>8.1 Two Pumping Lemmas<br/>A Pumping Lemma for Context-Free Languages<br/>A Pumping Lemma for Linear Languages<br/>8.2 Closure Properties and Decision Algorithms for Context-<br/>Free Languages<br/>Closure of Context-Free Languages<br/>Some Decidable Properties of Context-Free Languages<br/>9 Turing Machines<br/>9.1 The Standard Turing Machine<br/>Definition of a Turing Machine<br/>Turing Machines as Language Accepters<br/>Turing Machines as Transducers<br/>9.2 Combining Turing Machines for Complicated Tasks<br/>9.3 Turing's Thesis<br/>10 Other Models of Turing Machines<br/>10.1 Minor Variations on the Turing Machine Theme<br/>Equivalence of Classes of Automata<br/>Turing Machines with a Stay-Option<br/>Turing Machines with Semi-Infinite Tape<br/>The Off-Line Turing Machine<br/>10.2 Turing Machines with More Complex Storage<br/>Multitape Turing Machines<br/>Multidimensional Turing Machines<br/>10.3 Nondeterministic Turing Machines<br/>10.4 A Universal Turing Machine<br/>10.5 Linear Bounded Automata<br/>11 A Hierarchy of Formal Languages and Automata<br/>11.1 Recursive and Recursively Enumerable Languages<br/>Languages That Are Not Recursively Enumerable<br/>A Language That Is Not Recursively Enumerable<br/>A Language That Is Recursively Enumerable but Not<br/>Recursive<br/>11.2 Unrestricted Grammars<br/>11.3 Context-Sensitive Grammars and Languages<br/>Context-Sensitive Languages and Linear Bounded<br/>Automata<br/>Relation Between Recursive and Context-Sensitive<br/>Languages<br/>11.4 The Chomsky Hierarchy<br/>12 Limits of Algorithmic Computation<br/>12.1 Some Problems That Cannot Be Solved by Turing<br/>Machines<br/>Computability and Decidability<br/>The Turing Machine Halting Problem<br/>Reducing One Undecidable Problem to Another<br/>12.2 Undecidable Problems for Recursively Enumerable<br/>Languages<br/>12.3 The Post Correspondence Problem<br/>12.4 Undecidable Problems for Context-Free Languages<br/>12.5 A Question of Efficiency<br/>13 Other Models of Computation<br/>13.1 Recursive Functions<br/>Primitive Recursive Functions<br/>Ackermann's Function<br/>p Recursive Functions<br/>13.2 Post Systems<br/>13.3 Rewriting Systems<br/>Matrix Grammars<br/>Markov Algorithms<br/>L-Systems<br/>14 An Overview of Computational Complexity<br/>14.1 Efficiency of Computation<br/>14.2 Turing Machine Models and Complexity .<br/>14.3 Language Families and Complexity Classes<br/>14.4 The Complexity Classes P and NP<br/>14.5 Some NP Problems<br/>14.6 Polynomial-Time Reduction<br/>14.7 NP-Completeness and an Open Question |
| 650 #0 - SUBJECT | |
| Keyword | Formal languages. |
| 650 #0 - SUBJECT | |
| Keyword | Machine theory. |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | General Books |
| Withdrawn status | Lost status | Damaged status | Not for loan | Home library | Current library | Shelving location | Date acquired | Full call number | Accession number | Date last seen | Date last checked out | Koha item type |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Central Library, Sikkim University | Central Library, Sikkim University | General Book Section | 07/06/2016 | 005.13/1 LIN/F | P19616 | 18/10/2022 | 06/09/2022 | General Books |