Course Outline: This course is an introduction to the theory of computation, from the point of view of languages over finite alphabets. We are going to start with Regular Languages, and the equivalence of several definitions: Finite Automata (deterministic and non-deterministic) and Regular Expressions (and applications to text search). The Pumping Lemma, and other approaches to showing that languages are not regular. We will continue with Context-free languages, and again the equivalence of several definitions: Context-free grammars and Push-Down Automata. We will finish with a version of the Pumping Lemma for Context-free languages. The final topic will be the Church-Turing thesis, and decidability.
Lectures: W 6:00-7:15, in SIE1422
Textbook: Introduction to the Analysis of Algorithms (Chapter 8)
Grading: 10 quizzes, worth 5% each, and 5 assignments, worth 10% each. Please form a group of 3 at the beginning of the course, and work on all the assignments with the same group. There is tremendous value in working on problems with your group; it amplifies the learning experience, and teaches teamwork. The quizzes will be written on Wednesdays, at the beginning of the class time, online.
How to avoid plagiarism: As mentioned above, the assignments will be written in groups. Each group has to work independently of the other groups; verbal discussions of problems among groups are allowed, but you should not show written notes, and you should not leave such discussions with written notes.
Attendance: Students are encouraged but not required to attend the lectures. The assignments will be posted online. The final exam will be written in class.
Students with disabilities: Cal State Channel Islands is committed to equal educational opportunities for qualified students with disabilities in compliance with Section 504 of the Federal Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990. The mission of Disability Accommodation Services is to assist students with disabilities to realize their academic and personal potential. Students with physical, learning, or other disabilities are encouraged to contact the Disability Accommodation Services office at (805) 437-8510 for personal assistance and accommodations. Please discuss your arrangements with the instructor as soon as possible.