FLAC.WS 15-453 Formal Languages, Automata and Computation (original) (raw)

| | 15-453 Formal Languages, Automata and Computation Spring 2014, TTH 12:00-1:20, GHC 4215 [Schedule/Assignments | Project Info | **What's New?**] Instructor: Lenore Blum (lblum@cs), Gates 7105. Office Hours : Tuesday 2-3pm, Gates 7105 TAs: Asa Frank (afrank@andrew.cmu.edu)Office Hours : Friday, 5:30-7:30pm, GHC 6002 Aashish Jindia (ajindia@andrew)Office Hours : Sunday, 6-8pm, Wean 5316 Andrew Smith (adsmith@andrew)Office Hours : Monday 5:45-7:45pm, Room GHC 7101 This course provides an introduction to formal languages, automata, computability, and complexity. The course consists of a traditional lecture component supported by weekly homework assignments and a course project. There are two midterms and a final examination. Topics Automata and Languages: finite automata, regular languages, pushdown automata, context-free languages, pumping lemmas. **Computability Theory:**Turing Machines, decidability, reducibility, the arithmetic hierarchy the recursion theorem, the Post correspondence problem. Complexity Theory: time complexity, classes P and NP, NP-completeness, space complexity PPACE, PSPACE-completeness, the polynomial hierarchy, randomized complexity, classes RP and BPP. Textbook: Introduction to the Theory of Computation (3rd� Ed.) by Michael Sipser, 2012. Errata for 3rd Edition: http://math.mit.edu/\~sipser/itoc-derrs3.1.html Prerequisites: 15-251 (or 21-228). Grading: Homework, 25%; Class Participation, 5%; Midterm I, 15%; Midterm II, 15%; Final, 25%; Project 15%. Attendance is required. Homework: Homework is due one week after it is assigned and should be handed in at the beginning of class. Late homework will be accepted only under exceptional circumstances. All assignments must be typeset (exceptions allowed for diagrams). Each problem should be done on a separate page. Each student is to do their own work and hand in their own homework individually. Collaboration is allowed, but References used (including books, articles, websites, people, including yourself) must be listed! Project: See Project Info. | | | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | |