Lectures: Tuesdays and Thursdays - 10:50-12:05 pm - Pereira Hall 109
Instructor: Philip Dorin - Doolan 102 - (310) 338-2832 - philip.dorin@lmu.edu
Secretary: Jacqi Davis - Doolan 101 - (310) 338-7351 - JaDavis@lmu.edu
The goal is to become familiar with some of the main ideas in the theory of computation.
We will emphasize classical automata (especially finite automata, pushdown automata, and Turing machines); formal grammars and languages (especially regular sets, context-free languages, recursive and recursively enumerable languages); computability and decidability.
Some of the material in this course (especially the stuff having to do with regular expressions, finite automata, context-free languages, and pushdown machines) is needed in, and is, therefore, pre-requisite to CMSI 488.
CMSI 281 - Data Structures and Algorithms I
MATH 248 - Introduction to Methods of Proof
Hopcroft, Ullman, and Motwani. Introduction to Automata Theory, Languages, and Computation (3rd edition). Addison-Wesley, 2007.
Expect, roughly, a new homework assignment each week; a mid-term exam (tentatively scheduled for Thursday, October 22); and a two-hour final exam (consult the university's official exam schedule).
In evaluating the quality of your work, I will take into consideration your total course effort, including homework, midterm exam, and final exam, with emphasis on the exams.
Grades will be awarded as follows: for superior work, A; for good work, B; for satisfactory work, C; for poor work, D; for failing work, F. At the discretion of the instructor, these may be raised by a + or lowered by a -.
Regarding academic honesty and integrity, students are referred to the LMU Bulletin 2008-2010, specifically, the section dealing with the university's honor code and process.
Kindly turn off the ringer on your cell phone before class begins.
Music players, laptops, netbooks, etc., should not be used during class.
The contents of this syllabus are subject to change, as necessary. You should periodically monitor this website to keep abreast of any changes, as well as posted homework assignments, hints, solutions, etc.
Twenty questions about languages and cardinality. Distributed in class. [9/15; not collected]
Ten questions about regular sets. Distributed in class. [9/22]
Design four finite state machines, and a question about regular expressions. Assigned during class. [9/24]
Design one finite state machine. Assigned during class. [9/29; not collected]
Design two non-deterministic finite state machines, and prove that if L = L(M) for some nfsm, then Reverse(L) is also the language of some nfsm. Assigned during class. [10/1]
Machines with lambda-moves. Assigned during class. [10/6]
Machines to/from regular expressions. Assigned during class. [10/8; not collected]
Three Pumping Lemma proofs. Assigned during class. [10/13]
Machines to/from right-linear grammars; some closure properties. Assigned during class. [10/15]
Here are some practice problems about finite automata, regular expressions, right-linear grammars, etc.
Revised: 22:00 on 15 October 2009
