راهنمای مدل‌های ریاضی برای زبان‌ها و محاسبات (محاسبات و شبکه‌ها)

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 Contents Preface Acknowledgements List of implementations List of symbols List of mathematical models List of language families Part I. Basic mathematical concepts 1 Sets, sequences, and languages 1.1 Sets 1.2 Sequences 1.3 Formal languages 2 Relations and functions 2.1 Relations 2.2 Functions 3 Graphs 3.1 Directed graphs 3.2 Trees Part II. Classical models for languages and computation 4 Relations and language models 4.1 Rewriting systems 4.2 Language-defining models 5 Finite automata 5.1 Mathematical elements of finite automata 5.1.1 How to specify finite automata 5.1.1.1 Informal description 5.1.1.2 State table 5.1.1.3 State diagram 5.1.1.4 Formal description 5.2 Finite automata that always read 5.3 Determinism 5.4 Reduction and minimization 5.5 Regular expressions 6 Context-free grammars 6.1 Mathematical elements of context-free grammars 6.2 Canonical derivations and derivation trees 6.2.1 Leftmost derivations 6.2.2 Rightmost derivations 6.2.3 Derivation trees 6.2.4 Ambiguity 6.3 Useless symbols and their elimination 6.4 Erasing rules and their elimination 6.5 Single rules and their elimination 6.6 Chomsky normal form 6.7 Left recursion and its removal 6.7.1 Direct left recursion and its elimination 6.7.2 Left recursion and its elimination 6.7.3 Right recursion 6.8 Greibach normal form 7 Pushdown automata 7.1 Pushdown automata 7.2 Pushdown automata and context-free grammars are equivalent 7.3 Three types of acceptance by pushdown automata 7.4 Determinism 8 Turing machines 8.1 Turing machines and their languages 8.2 Determinism 8.3 Universalness 8.3.1 Turing machine codes 8.3.2 Construction of universal Turing machines 9 Computability 9.1 Functions computed by Turing machines 9.2 Mathematical theory of computability: an introduction 10 Decidability 10.1 Turing deciders 10.2 Decidable problems 10.2.1 Decidable problems for finite automata 10.2.2 Decidable problems for context-free grammars 10.3 Undecidability: diagonalization 10.4 Undecidability: reduction 10.5 Undecidability: a general approach to reduction 10.6 Computational complexity 10.6.1 Time complexity 10.6.2 Space complexity Part III. Alternative models for languages and computation 11 Context-dependent grammars 11.1 Tightly context-dependent grammars 11.2 Loosely context-dependent grammars 12 Regulated models 12.1 Grammars regulated by states 12.1.1 Definitions and examples 12.1.2 Generative power 12.2 Grammars regulated by control languages 12.2.1 Definitions and examples 12.2.2 Generative power 12.3 Matrix grammars 12.3.1 Definitions and examples 12.3.2 Generative power 12.3.3 Even matrix grammars 12.3.3.1 Definitions and examples 12.3.3.2 Generative power 12.3.3.3 Summary 12.4 Programmed grammars 12.4.1 Definitions and examples 12.4.2 Generative power 12.5 Regulated automata and computation 12.5.1 Self-regulating automata 12.5.2 Self-regulating finite automata 12.5.2.1 Definitions and examples 12.5.2.2 Accepting power 12.5.2.3 n-Turn first-move self-regulating finite automata 12.5.2.4 Language families accepted by n-first-SFAs and n-all-SFAs 12.5.3 Self-regulating pushdown automata 12.5.3.1 Definitions 12.5.3.2 Accepting power 12.5.4 Open problems 12.5.5 Regulated acceptance with control languages 12.5.6 Finite automata regulated by control languages 12.5.6.1 Definitions 12.5.6.2 Conversions 12.5.6.3 Regular-controlled finite automata 12.5.6.4 Context-free-controlled finite automata 12.5.6.5 Program-controlled finite automata 12.5.7 Pushdown automata regulated by control languages 12.5.7.1 Definitions 12.5.7.2 Regular-controlled pushdown automata 12.5.7.3 Linear-controlled pushdown automata 12.5.7.4 One-turn linear-controlled pushdown automata 12.5.8 Self-reproducing pushdown transducers 12.5.9 Definitions 12.5.10 Results 13 Parallel grammatical models 13.1 Partially parallel grammars 13.1.1 Definitions and examples 13.1.2 Generative power 13.1.3 Normal forms 13.1.4 Reduction 13.1.5 Economical transformations 13.2 Totally parallel grammars 13.2.1 Context-conditional ET0L grammars 13.2.1.1 Definitions 13.2.1.2 Generative power 13.2.2 Forbidding ET0L grammars 13.2.2.1 Definitions and examples 13.2.2.2 Generative power and reduction 13.2.3 Simple semi-conditional ET0L grammars 13.2.3.1 Definitions 13.2.3.2 Generative power and reduction 13.2.4 Left random context ET0L grammars 13.2.4.1 Definitions and examples 13.2.4.2 Generative power and reduction 13.3 Multigenerative grammar systems and parallel computation 13.3.1 Multigenerative grammar systems 13.3.2 Leftmost multigenerative grammar systems 14 Jumping models 14.1 Sequential jumping grammars 14.2 Parallel jumping grammars 14.2.1 Definitions 14.2.2 Results 14.2.2.1 Jumping derivation mode 1 14.2.2.2 Jumping derivation mode 2 14.2.2.3 Jumping derivation mode 3 14.2.2.4 Jumping derivation mode 4 14.2.2.5 Jumping derivation mode 5 14.2.2.6 Jumping derivation mode 6 14.2.2.7 Jumping derivation mode 7 14.2.2.8 Jumping derivation mode 8 14.2.2.9 Jumping derivation mode 9 14.2.2.10 Open problem areas 14.3 Jumping automata 14.3.1 Definitions and examples 14.3.1.1 Denotation of language families 14.3.2 Properties 14.3.2.1 Relations with well-known language families 14.3.2.2 Closure properties 14.3.2.3 Decidability 14.3.2.4 An infinite hierarchy of language families 14.3.2.5 Left and right jumps 14.3.2.6 A variety of start configurations 14.3.2.7 Relations between jumping automata and jumping grammars 14.3.2.8 A summary of open problems 15 Deep pushdown automata 15.1 Basic model 15.1.1 Definitions and examples 15.1.2 Accepting power 15.1.3 Open problems 15.1.3.1 Generalization 15.2 Restricted versions 15.2.1 Preliminaries and definitions 15.2.2 Results 15.2.3 Open problems Part IV. Applications 16 Applications in general 16.1 Applications in computational linguistics: general comments 16.2 Applications in computational biology: general comments 17 Applications in syntax analysis: programming languages 17.1 General parsers 17.1.1 Syntax specified by context-free grammars 17.1.2 Top-down parsing 17.1.3 Bottom-up parsing 17.2 Top-down parsers 17.2.1 Predictive sets and LL grammars 17.2.2 LL grammars 17.2.3 Predictive parsing 17.2.4 Predictive recursive-descent parsing 17.2.5 Predictive table-driven parsing 17.2.6 Handling errors 17.2.7 Exclusion of left recursion 17.3 Bottom-up parsers 17.3.1 Operator-precedence parsing 17.3.2 Operator-precedence parser 17.3.3 Construction of operator-precedence parsing table 17.3.4 Handling errors 17.3.5 Operator-precedence parsers for other expressions 17.3.6 LR parsing 17.3.7 LR parsing algorithm 17.3.8 Construction of the LR table 17.3.9 Handling errors in LR parsing 17.4 Syntax-directed translation: an implementation 18 Applications in syntax analysis: natural languages 18.1 Syntax and related linguistic terminology 18.1.1 Introduction by way of examples 18.1.2 Terminology 18.1.3 Verbs 18.1.4 Personal pronouns 18.2 Transformational scattered context grammars 18.3 Scattered context in English syntax 18.3.1 Clauses with neither and nor 18.3.2 Existential clauses 18.3.3 Interrogative clauses 18.3.4 Question tags 18.3.5 Generation of grammatical sentences 19 Applications in biology 19.1 Applications 19.1.1 Death 19.1.2 Degeneration 19.2 Implementation Part V. Conclusion 20 Concluding remarks 20.1 Summary of the book 20.2 Latest trends and open problems 20.3 Bibliographical remarks 20.3.1 Grammars 20.3.2 Automata References Index Back Cover 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#.