Hầu hết mọi người được giới thiệu khoa học máy tính bằng cách sử dụng một máy tính thực sự của khóa học, và hầu hết các phần này đòi hỏi một kiến thức về chỉ một số đại số cơ bản. Tuy nhiên, như là một bắt đầu để tìm hiểu thêm về lý thuyết | The Theory of Languages and Computation Jean Gallier jean@ Andrew Hicks rah@ Department of Computer and Information Science University of Pennsylvania Preliminary notes - Please do not distribute. a a b 1 Contents 1 Automata 3 Notation. 3 Proofs. 3 Set Theory . 3 The Natural numbers and Induction. 15 Foundations of Language Theory. 20 Operations on Languages. 21 Deterministic Finite Automata. 23 The Cross Product Construction. 27 Non-Deterministic Finite Automata . 29 Directed Graphs and Paths . 32 Labeled Graphs and Automata . 34 The Theorem of Myhill and Nerode . 42 Minimal DFAs . 46 State Equivalence and Minimal DFA s. 47 2 Formal Languages 54 A Grammar for Parsing English . 54 Context-Free Grammars . 56 Derivations and Context-Free Languages . 57 Normal Forms for Context-Free Grammars Chomsky Normal Form . 61 Regular Languages are Context-Free . 67 Useless Productions in Context-Free Grammars . 68 The Greibach Normal Form. 69 Least Fixed-Points . 69 Context-Free Languages as Least Fixed-Points . 71 Least Fixed-Points and the Greibach Normal Form . 75 Tree Domains and Gorn Trees . 79 Derivations Trees . 81 Ogden s Lemma. 83 Pushdown Automata . 87 From Context-Free Grammars To PDA s . 91 From PDA s To Context-Free Grammars. 93 3 Computability 95 Computations of Turing Machines . 97 The Primitive Recursive Functions. 99 The Partial Recursive Functions .102 Recursively Enumerable Languages and Recursive Languages . 103 2 Phrase-Structure Derivations and Type-0 Type-0 Grammars and Context-Sensitive The Halting A Univeral Machine .107 The Parameter Recursively Enumerable Languages . 107 Hilbert s Tenth 4 Current Topics 108 DNA Computing . 108 Analog .
