LEADER 04114nam 2200697Ia 450 001 9911018975403321 005 20200520144314.0 010 $a9786610264742 010 $a9781280264740 010 $a1280264748 010 $a9780470321478 010 $a0470321474 010 $a9780471464082$b(electronic bk.) 010 $a0471464082 010 $a9780471224648$b(electronic bk.) 010 $a0471224642 035 $a(CKB)111087027130570 035 $a(EBL)215154 035 $a(OCoLC)475923550 035 $a(SSID)ssj0000080481 035 $a(PQKBManifestationID)11312308 035 $a(PQKBTitleCode)TC0000080481 035 $a(PQKBWorkID)10095356 035 $a(PQKB)10033213 035 $a(MiAaPQ)EBC215154 035 $a(Perlego)2766286 035 $a(EXLCZ)99111087027130570 100 $a20011012d2001 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aProblem solving in automata, languages, and complexity /$fDing-Zhu Du, Ker-I Ko 210 $aNew York $cWiley$dc2001 215 $a1 online resource (405 p.) 300 $a"A Wiley-Interscience publication." 311 08$a9780471439608 311 08$a0471439606 320 $aIncludes bibliographical references (p. 387-388) and index. 327 $aContents; Preface; 1 Regular Languages; 1.1 Strings and Languages; 1.2 Regular Languages and Regular Expressions; 1.3 Graph Representations for Regular Expressions; 2 Finite Automata; 2.1 Deterministic Finite Automata; 2.2 Examples of Deterministic Finite Automata; 2.3 Nondeterministic Finite Automata; 2.4 Converting an NFA to a DFA; 2.5 Finite Automata and Regular Expressions; 2.6 Closure Properties of Regular Languages; 2.7 Minimum Deterministic Finite Automata; 2.8 Pumping Lemmas; 3 Context-Free Languages; 3.1 Context-Free Grammars; 3.2 More Examples of Context-Free Grammars 327 $a3.3 Parsing and Ambiguity3.4 Pushdown Automata; 3.5 Pushdown Automata and Context-Free Grammars; 3.6 Pumping Lemmas for Context-Free Languages; 4 Turing Machines; 4.1 One-Tape Turing Machines; 4.2 Examples of Turing Machines; 4.3 Multi-Tape Turing Machines; 4.4 Church-Turing Thesis; 4.5 Unrestricted Grammars; 4.6 Primitive Recursive Functions; 4.7 Pairing Functions and Go?del Numberings; 4.8 Partial Recursive Functions; 5 Computability Theory; 5.1 Universal Turing Machines; 5.2 R. E. Sets and Recursive Sets; 5.3 Diagonalization; 5.4 Reducibility; 5.5 Recursion Theorem; 5.6 Undecidable Problems 327 $a6 Computational Complexity6.1 Asymptotic Growth Rate; 6.2 Time and Space Complexity; 6.3 Hierarchy Theorems; 6.4 Nondeterministic Turing Machines; 6.5 Context-Sensitive Languages; 7 NP-Completeness; 7.1 NP; 7.2 Polynomial-Time Reducibility; 7.3 Cook's Theorem; 7.4 More NP-Complete Problems; 7.5 NP-Complete Optimization Problems; References; Index; A; B; C; D; E; F; G; H; I; K; L; M; N; O; P; Q; R; S; T; U; V; W; X; Z 330 $aAutomata and natural language theory are topics lying at the heart of computer science. Both are linked to computational complexity and together, these disciplines help define the parameters of what constitutes a computer, the structure of programs, which problems are solvable by computers, and a range of other crucial aspects of the practice of computer science. In this important volume, two respected authors/editors in the field offer accessible, practice-oriented coverage of these issues with an emphasis on refining core problem solving skills. 606 $aMachine theory 606 $aFormal languages 606 $aComputational complexity 615 0$aMachine theory. 615 0$aFormal languages. 615 0$aComputational complexity. 676 $a511.3 700 $aDu$b Dingzhu$061540 701 $aKo$b Ker-I$0772066 712 02$aWiley Online Library (Servicio en línea) 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9911018975403321 996 $aProblem solving in automata, languages, and complexity$94416882 997 $aUNINA