📄 http:^^www.cis.upenn.edu^~jean^cse262.html
字号:
Server: Netscape-Communications/1.1
Date: Wednesday, 20-Nov-96 23:25:04 GMT
Last-modified: Tuesday, 05-Nov-96 22:46:08 GMT
Content-length: 4961
Content-type: text/html
<HTML><HEAD><TITLE>CSE 262 Handout 1</TITLE><BODY><! BODY BGCOLOR = "#000000" TEXT = "#FFFFFF"><BODY bgcolor="#FFEFDB"> <! AntiqueWhite1><H1><CENTER>CSE 262, Fall 96 </center> <p><center> Automata, Computability & Complexity</CENTER><CENTER>Course Information</CENTER><CENTER>August 30, 1996</CENTER></H1><P><H4><H2>Coordinates:</H2> TOWNE 311, Mo We Fr 11-12<P><H2>Instructor:</H2> <!WA0><A HREF="mailto:jean@saul.cis.upenn.edu">Jean H. Gallier</A>, MRE 176, 8-4405, jean@saul <P><H2>Office Hours:</H2> Mon-Wed, 3-4pm, Thurs, 4:45-5:45pm <P><H2>Teaching Assistant:</H2> <!WA1><A HREF="mailto:dparkes@unagi"</A>David Parkes</A>, Towne 353, dparkes@unagi<P><H2>Office Hours:</H2> Mon.-Wed., 5-6pm<P><H2>Textbook(required):</H2> <I>An Introduction to Formal Languages and Automata</I>, Peter Linz, D.C. Heath and Co<P>Also recommended:<P><I>Introduction to Automata Theory, Languagesand Computation </I>, J.E. Hopcroft and J.D. Ullman, Addison Wesley<P><H2>Grades:</H2><P>1/2: Homework Assignments (5-6 of them)<BR><BR>1/8: Intermediate Exam 1 (1h closed book; Wed. October 23, 1996)<BR><BR>1/8: Intermediate Exam 2 (1h closed book; mid November)<BR><BR>1/4: Final Exam <BR><P><H2> Problem Sets </H2> <ul><li><!WA2><a href="http://www.cis.upenn.edu/~jean/cse262hw1.ps.Z"> Homework1 </a><li><!WA3><a href="http://www.cis.upenn.edu/~jean/cse262hw2.ps.Z"> Homework2 </a><li><!WA4><a href="http://www.cis.upenn.edu/~jean/cse262hw3.ps.Z"> Homework3 </a></ul><P><H2> Some Transparencies and Notes</H2><ul><li> <!WA5><a href="http://www.cis.upenn.edu/~jean/cse262sl1.ps.Z"> Basics of language theory, DFA's, the cross-product construction</a><li> <!WA6><a href="http://www.cis.upenn.edu/~jean/cse262sl2.ps.Z"> NFA's, labeled directed graphs, regular expressions </a><li> <!WA7><a href="http://www.cis.upenn.edu/~jean/cse262sl3.ps.Z"> The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's </a><li> <!WA8><a href="http://www.cis.upenn.edu/~jean/cse262sl4.ps.Z"> Context-free grammars and context-free languages (slides) </a><li> <!WA9><a href="http://www.cis.upenn.edu/~jean/cfl1.ps.Z"> Context-free grammars and context-free languages (notes) </a></ul><P><H2>Brief description:</H2> The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) computability and recursive function theory; (3) complexity theory. The course will focus mostly on (1) and (2). Applications of (1) to programming (and natural) language specification and recognition (in particular, compiler construction), will be emphasized.<BR><P>Topics will include:<UL><LI> Basics of language theory: alphabets, strings, concatenation, languages, operations on languages (including Kleene *)<LI> Deterministic finite automata (DFA's)<LI> The cross-product construction<LI> Nondeterministic finite automata (NFA's)<LI> From NFA's to DFA's, the subset algorithm (Rabin and Scott)<LI> Labeled directed graphs, NFA's and DFA's<LI> Regular languages and regular expressions<LI> From regular expressions to NFA's<LI> From NFA's to regular expressions (node elimination)<LI> The Myhill-Nerode Theorem, State equivalence, minimal DFA's<LI> The pumping lemma for regular languages<LI> Fractals and languages (a glimpse)<LI> Context-free grammars and context-free languages<LI> Leftmost derivations, rightmost derivations, parse trees<LI> The universality of leftmost derivations<LI> Cleaning-up context-free grammars (e-rules, chain rules)<LI> Chomsky Normal Form<LI> Right-linear grammars and regular languages<LI> Eliminating useless productions<LI> Greibach Normal Form<LI> Tree domains, Gorn trees, and parse trees<LI> A pumping lemma for context-free languages<LI> Pushdown Automata (PDA's), instantaneous descriptions, acceptance modes<LI> DPDA's (Deterministic PDA's) <LI> From context-free grammars to PDA's<LI> From PDA's to context-free grammars<LI> A glimpse at LR-parsing<LI> Generalities on computability, models of computation<LI> Turing Machines<LI> RAM programs (flowchart and sequential form)<LI> Primitive recursive functions<LI> Recursive and partial recursive functions<LI> Recursively enumerable languages and recursive languages<LI> The equivalence of RAM computable and Turing computable functions<LI> The equivalence of Turing computable functions and partial recursive functions<LI> Phrase-Structure Grammars <LI> Type-0 Languages<LI> Type-0 Grammars and Context-Sensitive Grammars<LI> Monotonic Grammars and Linear-Bounded Automata<! The undecidability of the halting problem ><! More Undecidable problems, the PCP ></UL><P><I>published by:<H2><!WA10><A HREF="mailto:jean@saul.cis.upenn.edu">Jean Gallier</A></H2></H4><BODY><HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -