The course provides an introduction to the theory of computation, with emphasis on formal languages, automata and abstract models of computation. Students will learn the conceptual models on which the modern digital computer is based. We are interested in both the capabilities and limitations of these models, and their relationships with languages. An important goal through this course is to gain proficiency with mathematical tools and formal methods that are essential to the understanding and appreciation of computer science as a coherent discipline.
week 1 : introduction.
week 2: math preliminaries. (Ch.1) alphabets and languages. (Ch.1)
week 3: mathematical proof techniques. (Ch.2) mathematical induction and recursions. (Ch.2) HW#1 starts
week 4: regular expressions. (Ch.3) finite automata. (Ch.3)
week 5: finite automata. (Ch.3) non-deterministic finite automata. (Ch.4)
week 6: non-deterministic finite automata. (Ch.4) HW#1 due Kleene's theorem. (Ch.4) HW#2 starts
week 7: minimal finite automata. (Ch.5) regular grammar and Pumping lemma. (Ch.5) HW#2 due
week 8: Midterm context-free grammar. (Ch.6)
week 9: deviation tree and ambiguity. (Ch.6) simplified forms and normal forms. (Ch.6) HW#3 starts
week 10: pushdown automata. (Ch.6) PDA for context-free grammar. (Ch.7)
week 11: context-free grammar for PDA. (Ch.7) Pumping lemma for context-free languages. (Ch.8) HW#3 due
week 12: Turing machine concepts. (Ch.9) computing with Turing machines. (Ch.9)
week 13: modifications to turing machines. (Ch.9) non-deterministic Turing machines and universal Turing machines. (Ch.9) HW#4 starts
week 14: recursively enumerable and recursive languages. (Ch.10) Nov 22 (Th): No Class (Thanksgiving Holiday)
week 15: unrestricted grammars. (Ch.10) HW#4 due Solvability and computability.
week 16: introduction to complexity theory. Final Exam
Grading scale is based on our school regulation.
Exams: 60% (midterm 30%, final 30%). Assignments and small tests: 40%. Late submission may take 10% point off.
Class attendance will be considered in boarderline cases. It is the student's responsibility to pass the examinations and complete the assignments, if he or she doesn't attend class regularly.
This class will partially use Oncourse, and website is at: http://www.cs.iupui.edu/~jzheng/470.html. You need to subscribe to the class mailing list to receive class related information. Send a mail to: majordomo@cs.iupui.edu with only "subscribe cs470" in the mail body. To post a message to the mailing list, send mail to: cs470@cs.iupui.edu.