Handbook of mathematical models for languages and computation (ISBN 978178561-6594)

The theory of computation is used to address challenges arising in many computer science areas such as artificial intelligence, language processors, compiler writing, information and coding systems, programming language design, computer architecture and more. To grasp topics concerning this theory readers need to familiarize themselves with its computational and language models, based on concepts of discrete mathematics including sets, relations, functions, graphs and logic. This handbook introduces with rigor the important concepts of this kind and uses them to cover the most important mathematical models for languages and computation, such as various classical as well as modern automata and grammars. It explains their use in such crucially significant topics of computation theory as computability, decidability, and computational complexity. The authors pay special attention to the implementation of all these mathematical concepts and models and explains clearly how to encode them in computational practice. All computer programs are written in C#. Cover......Page 1 Contents......Page 8 Preface......Page 14 Acknowledgements......Page 18 List of implementations......Page 20 List of symbols......Page 22 List of mathematical models......Page 24 List of language families......Page 26 Part I. Basic mathematical concepts......Page 30 1.1 Sets......Page 32 1.2 Sequences......Page 39 1.3 Formal languages......Page 40 2.1 Relations......Page 50 2.2 Functions......Page 54 3.1 Directed graphs......Page 58 3.2 Trees......Page 59 Part II. Classical models for languages and computation......Page 64 4.1 Rewriting systems......Page 66 4.2 Language-defining models......Page 71 5.1 Mathematical elements of finite automata......Page 76 5.1.1 How to specify finite automata......Page 77 5.1.1.3 State diagram......Page 78 5.1.1.4 Formal description......Page 79 5.2 Finite automata that always read......Page 82 5.3 Determinism......Page 89 5.4 Reduction and minimization......Page 100 5.5 Regular expressions......Page 104 6.1 Mathematical elements of context-free grammars......Page 116 6.2.1 Leftmost derivations......Page 123 6.2.3 Derivation trees......Page 125 6.2.4 Ambiguity......Page 127 6.3 Useless symbols and their elimination......Page 131 6.4 Erasing rules and their elimination......Page 138 6.5 Single rules and their elimination......Page 143 6.6 Chomsky normal form......Page 147 6.7 Left recursion and its removal......Page 152 6.7.1 Direct left recursion and its elimination......Page 153 6.7.2 Left recursion and its elimination......Page 154 6.8 Greibach normal form......Page 161 7.1 Pushdown automata......Page 168 7.2 Pushdown automata and context-free grammars are equivalent......Page 175 7.3 Three types of acceptance by pushdown automata......Page 179 7.4 Determinism......Page 181 8.1 Turing machines and their languages......Page 188 8.2 Determinism......Page 196 8.3.1 Turing machine codes......Page 200 8.3.2 Construction of universal Turing machines......Page 205 9.1 Functions computed by Turing machines......Page 208 9.2 Mathematical theory of computability: an introduction......Page 213 10.1 Turing deciders......Page 220 10.2.1 Decidable problems for finite automata......Page 223 10.2.2 Decidable problems for context-free grammars......Page 225 10.3 Undecidability: diagonalization......Page 227 10.4 Undecidability: reduction......Page 230 10.5 Undecidability: a general approach to reduction......Page 233 10.6 Computational complexity......Page 237 10.6.1 Time complexity......Page 238 10.6.2 Space complexity......Page 240 Part III. Alternative models for languages and computation......Page 242 11.1 Tightly context-dependent grammars......Page 244 11.2 Loosely context-dependent grammars......Page 261 12.1.1 Definitions and examples......Page 322 12.2.1 Definitions and examples......Page 324 12.3.1 Definitions and examples......Page 328 12.3.3 Even matrix grammars......Page 330 12.3.3.1 Definitions and examples......Page 331 12.3.3.2 Generative power......Page 334 12.4.1 Definitions and examples......Page 342 12.5.1 Self-regulating automata......Page 345 12.5.2.1 Definitions and examples......Page 346 12.5.2.2 Accepting power......Page 348 12.5.2.3 n-Turn first-move self-regulating finite automata......Page 349 12.5.2.4 Language families accepted by n-first-SFAs and n-all-SFAs......Page 359 12.5.3.1 Definitions......Page 361 12.5.3.2 Accepting power......Page 362 12.5.6 Finite automata regulated by control languages......Page 364 12.5.6.1 Definitions......Page 365 12.5.6.2 Conversions......Page 366 12.5.6.4 Context-free-controlled finite automata......Page 368 12.5.6.5 Program-controlled finite automata......Page 369 12.5.7.1 Definitions......Page 378 12.5.7.2 Regular-controlled pushdown automata......Page 379 12.5.7.3 Linear-controlled pushdown automata......Page 380 12.5.7.4 One-turn linear-controlled pushdown automata......Page 385 12.5.8 Self-reproducing pushdown transducers......Page 389 12.5.9 Definitions......Page 390 12.5.10 Results......Page 391 13.1.1 Definitions and examples......Page 396 13.1.3 Normal forms......Page 400 13.1.4 Reduction......Page 402 13.1.5 Economical transformations......Page 414 13.2 Totally parallel grammars......Page 421 13.2.1.1 Definitions......Page 422 13.2.1.2 Generative power......Page 423 13.2.2.1 Definitions and examples......Page 429 13.2.2.2 Generative power and reduction......Page 430 13.2.3.1 Definitions......Page 448 13.2.3.2 Generative power and reduction......Page 449 13.2.4 Left random context ET0L grammars......Page 462 13.2.4.1 Definitions and examples......Page 463 13.2.4.2 Generative power and reduction......Page 465 13.3 Multigenerative grammar systems and parallel computation......Page 478 13.3.1 Multigenerative grammar systems......Page 479 13.3.2 Leftmost multigenerative grammar systems......Page 495 14.1 Sequential jumping grammars......Page 508 14.2 Parallel jumping grammars......Page 523 14.2.1 Definitions......Page 525 14.2.2.1 Jumping derivation mode 1......Page 527 14.2.2.2 Jumping derivation mode 2......Page 529 14.2.2.3 Jumping derivation mode 3......Page 537 14.2.2.4 Jumping derivation mode 4......Page 540 14.2.2.5 Jumping derivation mode 5......Page 544 14.2.2.6 Jumping derivation mode 6......Page 546 14.2.2.7 Jumping derivation mode 7......Page 547 14.2.2.8 Jumping derivation mode 8......Page 551 14.2.2.9 Jumping derivation mode 9......Page 552 14.3 Jumping automata......Page 553 14.3.1 Definitions and examples......Page 555 14.3.2 Properties......Page 556 14.3.2.1 Relations with well-known language families......Page 559 14.3.2.2 Closure properties......Page 560 14.3.2.3 Decidability......Page 563 14.3.2.4 An infinite hierarchy of language families......Page 565 14.3.2.5 Left and right jumps......Page 566 14.3.2.6 A variety of start configurations......Page 567 14.3.2.7 Relations between jumping automata and jumping grammars......Page 569 14.3.2.8 A summary of open problems......Page 571 15.1 Basic model......Page 574 15.1.1 Definitions and examples......Page 575 15.1.2 Accepting power......Page 576 15.1.3 Open problems......Page 584 15.2 Restricted versions......Page 585 15.2.2 Results......Page 586 15.2.3 Open problems......Page 591 Part IV. Applications......Page 592 16.1 Applications in computational linguistics: general comments......Page 594 16.2 Applications in computational biology: general comments......Page 596 17 Applications in syntax analysis: programming languages......Page 598 17.1 General parsers......Page 599 17.1.1 Syntax specified by context-free grammars......Page 600 17.1.2 Top-down parsing......Page 602 17.1.3 Bottom-up parsing......Page 605 17.2.1 Predictive sets and LL grammars......Page 611 17.2.2 LL grammars......Page 618 17.2.4 Predictive recursive-descent parsing......Page 620 17.2.5 Predictive table-driven parsing......Page 626 17.2.6 Handling errors......Page 632 17.3 Bottom-up parsers......Page 634 17.3.2 Operator-precedence parser......Page 635 17.3.3 Construction of operator-precedence parsing table......Page 643 17.3.4 Handling errors......Page 644 17.3.5 Operator-precedence parsers for other expressions......Page 648 17.3.7 LR parsing algorithm......Page 650 17.3.8 Construction of the LR table......Page 659 17.3.9 Handling errors in LR parsing......Page 672 17.4 Syntax-directed translation: an implementation......Page 675 18.1.1 Introduction by way of examples......Page 690 18.1.2 Terminology......Page 692 18.1.4 Personal pronouns......Page 693 18.2 Transformational scattered context grammars......Page 695 18.3 Scattered context in English syntax......Page 697 18.3.1 Clauses with neither and nor......Page 698 18.3.2 Existential clauses......Page 699 18.3.3 Interrogative clauses......Page 700 18.3.4 Question tags......Page 702 18.3.5 Generation of grammatical sentences......Page 704 19.1 Applications......Page 708 19.1.1 Death......Page 711 19.1.2 Degeneration......Page 712 19.2 Implementation......Page 715 Part V. Conclusion......Page 722 20.1 Summary of the book......Page 724 20.2 Latest trends and open problems......Page 727 20.3.1 Grammars......Page 729 20.3.2 Automata......Page 730 References......Page 731 Index......Page 750 Back Cover......Page 761 The book comprises 20 chapters dealing with the following subjects: mathematical models for languages and computation; sets; sequences; relations; functions; graphs; classical models; finite automata; context-free grammars; pushdown automata; Turing machines; computability; decidability; context-dependent grammars; regulated models; parallel grammatical models; jumping models; deep pushdown automata; syntax analysis; programming languages; natural languages; and biology This handbook introduces a variety of concepts in discrete mathematics and mathematical modeling for languages and computation. The authors pay special attention to the implementation of mathematical concepts to explain clearly how to encode them in computational practice. All computer programs are written in C#.