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.
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 CS311. Discrete math definitions, models, and proofs are fundamental in the material in CS380.
There will be three 50-minute, in-class, closed book quizzes for 100 pts each. Quizzes 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 require accomodation(s) should make an appointment with the Office of Disability Services (974-6087) to discuss their specific needs as well as schedule an appointment with Linda Silvers, Administrative Services Assistant, College of Arts and Sciences (974-4161) during her office hours.
(1 DEC 2005)