http:^^www.cs.cornell.edu^info^courses^current^cs481^syllabus.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 170 行
HTML
170 行
MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:37:24 GMT
Content-Type: text/html
Content-Length: 5372
Last-Modified: Wednesday, 06-Nov-96 05:01:50 GMT
<HTML><HEAD><TITLE>CS381/481 Fall 96 Syllabus</TITLE></HEAD><BODY><H1>CS381/481 Fall 1996<br>Automata and Computability Theory<br>Syllabus</H1><HR>Below is a tentative list of topics to be covered in the course. Theyfall into three major areas:<ul><li><!WA0><!WA0><!WA0><!WA0><a href="#1">Finite Automata and Regular Sets</A><li><!WA1><!WA1><!WA1><!WA1><a href="#2">Pushdown Automata and Context Free Languages</A><li><!WA2><!WA2><!WA2><!WA2><a href="#3">Turing Machines and Effective Computability</A></ul>Each area will comprise roughly a third of the course. The entirebody of lecture notes is available in postscript format by clicking <!WA3><!WA3><!WA3><!WA3><ahref="http://www.cs.cornell.edu/Info/Courses/Fall-96/CS481/481.ps">here</A>,or you can obtain hardcopy for $7 from Linda Mardel in 5147.<p> The lecture notes are soon to be published as a textbook bySpringer-Verlag. For that reason, I am very interested in yourcomments and suggestions. In particular, I will pay you $1 for eachmistake, typo, misspelling, etc. that you find that I don't alreadyknow about. [<!WA4><!WA4><!WA4><!WA4><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/errata.html">known errata</a>]<p>Suggested supplementary readings are taken from the text byJ. E. Hopcroft and J. D. Ullman, <i>Introduction to Automata Theory,Languages, and Computation</i>, Addison-Wesley, 1979 (H&U).<p> In addition to these specific topics, it is important that by theend of the course, you have a good general understanding of what itmeans for a set to be regular, context-free, recursive, and r.e.; ofthe capabilities of finite automata, pushdown automata, and Turingmachines; and of how to describe sets using regular expressions andcontext-free grammars.<hr><H2><A NAME = "1">Finite Automata and Regular Sets (H&U Chps. 1-3)</a></H2><!WA5><!WA5><!WA5><!WA5><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l1.ps">Lecture 1: Course Roadmap and Historical Perspective</a><br><!WA6><!WA6><!WA6><!WA6><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l2.ps">Lecture 2: Operations on Sets</a><br><!WA7><!WA7><!WA7><!WA7><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l3.ps">Lecture 3: Finite Automata and Regular Sets</a><br><!WA8><!WA8><!WA8><!WA8><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l4.ps">Lecture 4: More on Regular Sets</a><br><!WA9><!WA9><!WA9><!WA9><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l5.ps">Lecture 5: Nondeterministic Finite Automata</a><br><!WA10><!WA10><!WA10><!WA10><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l6.ps">Lecture 6: The Subset Construction</a><br><!WA11><!WA11><!WA11><!WA11><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l7.ps">Lecture 7: Pattern Matching and Regular Expressions</a><br><!WA12><!WA12><!WA12><!WA12><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l8.ps">Lecture 8: More on Pattern Matching</a><br><!WA13><!WA13><!WA13><!WA13><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l9.ps">Lecture 9: Regular Expressions and Finite Automata</a><br><!WA14><!WA14><!WA14><!WA14><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lA.ps">Supplementary Lecture A: Kleene Algebra and Regular Expressions</a><br><!WA15><!WA15><!WA15><!WA15><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l10.ps">Lecture 10: Homomorphisms</a><br><!WA16><!WA16><!WA16><!WA16><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l11.ps">Lecture 11: Limitations of Finite Automata</a><br><!WA17><!WA17><!WA17><!WA17><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l12.ps">Lecture 12: Using the Pumping Lemma</a><br><!WA18><!WA18><!WA18><!WA18><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l13.ps">Lecture 13: DFA State Minimization</a><br><!WA19><!WA19><!WA19><!WA19><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l14.ps">Lecture 14: A Minimization Algorithm</a><br><!WA20><!WA20><!WA20><!WA20><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l15.ps">Lecture 15: Myhill-Nerode Relations</a><br><!WA21><!WA21><!WA21><!WA21><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l16.ps">Lecture 16: The Myhill-Nerode Theorem</a><br><!WA22><!WA22><!WA22><!WA22><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lB.ps">Supplementary Lecture B: Collapsing Nondeterministic Automata</a><br><!WA23><!WA23><!WA23><!WA23><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lC.ps">Supplementary Lecture C: Automata on Terms</a><br><!WA24><!WA24><!WA24><!WA24><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lD.ps">Supplementary Lecture D: The Myhill-Nerode Theorem for Term Automata</a><br><!WA25><!WA25><!WA25><!WA25><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l17.ps">Lecture 17: Two-Way Finite Automata</a><br><!WA26><!WA26><!WA26><!WA26><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l18.ps">Lecture 18: 2DFAs and Regular Sets</a><br><H2><A NAME = "2">Pushdown Automata and Context Free Languages (H&U Chps. 4-6, 9.1)</H2><!WA27><!WA27><!WA27><!WA27><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l19.ps">Lecture 19: Context-Free Grammars and Languages</a><br><!WA28><!WA28><!WA28><!WA28><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l20.ps">Lecture 20: Balanced Parentheses</a><br><!WA29><!WA29><!WA29><!WA29><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l21.ps">Lecture 21: Normal Forms</a><br><!WA30><!WA30><!WA30><!WA30><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l22.ps">Lecture 22: The Pumping Lemma for CFLs</a><br><!WA31><!WA31><!WA31><!WA31><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l23.ps">Lecture 23: Pushdown Automata</a><br><!WA32><!WA32><!WA32><!WA32><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lE.ps">Supplementary Lecture E: Final State vs. Empty Stack</a><br><!WA33><!WA33><!WA33><!WA33><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l24.ps">Lecture 24: PDAs and CFGs</a><br><!WA34><!WA34><!WA34><!WA34><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l25.ps">Lecture 25: Simulating NPDAs by CFGs</a><br><!WA35><!WA35><!WA35><!WA35><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lF.ps">Supplementary Lecture F: Deterministic Pushdown Automata</a><br><!WA36><!WA36><!WA36><!WA36><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l26.ps">Lecture 26: Parsing</a><br><!WA37><!WA37><!WA37><!WA37><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l27.ps">Lecture 27: The Cocke-Kasami-Younger Algorithm</a><br><!WA38><!WA38><!WA38><!WA38><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lG.ps">Supplementary Lecture G: The Chomsky-Schutzenberger Algorithm</a><br><!WA39><!WA39><!WA39><!WA39><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lH.ps">Supplementary Lecture H: Parikh's Theorem</a><br><H2><A NAME = "3">Turing Machines and Effective Computability (H&U Chps. 7-8)</H2><!WA40><!WA40><!WA40><!WA40><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l28.ps">Lecture 28: Turing Machines and Effective Computability</a><br><!WA41><!WA41><!WA41><!WA41><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l29.ps">Lecture 29: More on Turing Machines</a><br><!WA42><!WA42><!WA42><!WA42><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l30.ps">Lecture 30: Equivalent Models</a><br><!WA43><!WA43><!WA43><!WA43><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l31.ps">Lecture 31: Universal Machines and Diagonalization</a><br><!WA44><!WA44><!WA44><!WA44><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l32.ps">Lecture 32: Decidable and Undecidable Problems</a><br><!WA45><!WA45><!WA45><!WA45><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l33.ps">Lecture 33: Reductions</a><br><!WA46><!WA46><!WA46><!WA46><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l34.ps">Lecture 34: Rice's Theorem</a><br><!WA47><!WA47><!WA47><!WA47><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l35.ps">Lecture 35: Undecidable Problems about CFLs</a><br><!WA48><!WA48><!WA48><!WA48><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l36.ps">Lecture 36: Other Formalisms</a><br><!WA49><!WA49><!WA49><!WA49><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l37.ps">Lecture 37: The Lambda-Calculus</a><br><!WA50><!WA50><!WA50><!WA50><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lI.ps">Supplementary Lecture I: While Programs</a><br><!WA51><!WA51><!WA51><!WA51><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lJ.ps">Supplementary Lecture J: Beyond Undecidability</a><br><!WA52><!WA52><!WA52><!WA52><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l38.ps">Lecture 38: Gödel's Incompleteness Theorem</a><br><!WA53><!WA53><!WA53><!WA53><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/l39.ps">Lecture 39: Proof of the Incompleteness Theorem</a><br><!WA54><!WA54><!WA54><!WA54><A href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/lK.ps">Supplementary Lecture K: Gödel's Proof</a><br><hr><!WA55><!WA55><!WA55><!WA55><img align=top src="http://www.cs.cornell.edu/Info/Misc/images/hand_point1.gif"><!WA56><!WA56><!WA56><!WA56><a href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/CS481.html">CS381/481 home page</a>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?