Countability and diagonalization.
Finite automata (FA as illustrated above) and regular sets. Regular set pumping lemma.
Pushdown automata, context-free languages, context-free grammars. Pumping lemma for CFLs.
Introduction to Turing machines and undecidability (to a description of Rice's Theorem). Recursive and recursively enumerable languages.
The course covers some basics of theoretical computer science and computational models. The text is INTRODUCTION TO AUTOMATA THEORY, LANGUAGES, AND COMPUTATION by Hopcroft and Ullman. This material is in chapters 1 through 9, but we will not cover all sections. In addition to the text, there will be numerous handouts in class throughout the semester. You are responsible for all assignments in the text and the handouts. It's not possible to answer technical questions about this kind of material by email. Use the office hours or make an appointment on a timely basis if you have questions.
We use the book by two authors (Hopcroft & Ullman) reprinted with permission and used by other sections of 380. This is NOT the newer book by Hopcroft-Motwani-Ullman. There will be numerous handouts in class. You are responsible for all assignments in the text and all handouts.
Prereq is COCS311. Discrete math definitions, models, and proofs are fundamental in the material in COCS380.
There will be three 50-minute, in-class, closed book exams for 100 pts each. Exams will be spaced roughly evenly through the semester. There will also be 5 to 10 graded homework assignments, each around 10-30 pts, totaling about 90 to 150 pts graded homework.
Most homework is for your practice, not to be turned in. Homework to be turned in for grading will be clearly indicated when handed out in class. You must work alone on graded homework and must turn it in yourself on time in class.
Here is postscript of syllabus/first handout: Handout,
Here are examples of homework after the relevant definitions, theorems, and algorithms have been covered. Sample 1, Sample 2, Sample 3 Sample 4 Sample 5
Students who have a disability that requires accomodation should make an appointment with the Office of Disability Services (974-6087) to discuss their specific needs.
(11 NOV 2010)