CSC 456/656

Computer Science 456/656: Automata and Formal Languages

Fall 1998

Instructor: Dr. Larmore Office, TBE A214. Telephone, 702-895-1096
Office Hours: 2:00 pm - 4:00 pm, Tuesdays and Thursdays.
Graduate Assistant: Yu Zhang
Room and Time: TBE B172, Tuesdays and Thursdays, 4:00 PM to 5:15 PM.
Days of Instruction: September 1, 1998 -- December 10, 1998.
Holiday: November 26.
Short Quiz: September 10.
Midterm Examinations: October 15, November 24.
Final Examination: Tuesday, December 15, 6:00 P.M.
Textbook: ``Introduction to Languages and the Theory of Computation," by John C. Martin.
Prerequisites: CSC 269 (Introduction to Data Structures) and MAT 351 (Discrete Mathematics II).
Postrequisite: CSC 478/678 (Compiler Construction)

This course is arguably the most interesting in the Computer Science core curriculum. During this Semester, you will learn the accurate meanings of a number of terms that you have probably heard. In some cases, you will have to unlearn what you previously believed! For example, you will learn the following concepts:

Automaton.
Language. (You may have thought you knew this one!)
Grammar. (You probably thought you knew this one, too!)
Turing Machine.
Universal Turing Machine. The machine that can do anything that any machine in this or any other universe could possibly do. But, rather slowly!
NP-complete. Almost everyone in computer science has heard this term. You will learn the precise meaning.
Undecidability. There are problems that are undecidable. There are propositions that are true but for which there is no proof. I don't mean no one has found a proof yet, I mean that no proof can exist at all! There are problems, such as the halting problem, which cannot be solved by any algorithm. No future genius, with a finite intellect, will ever find one, not in this (or any other) universe, ever.
P = NP? The most famous open question in all of computer science. What does this mean? What does it mean in practical terms?

Written Homework will be assigned, collected, and graded. You are permitted to discuss homework. The first assignment will be handed out on Thursday, September 3, and will be collected in class Tuesday, September 8. (If you cannot attend class that day, leave your homework, in an envelope, with one of the office staff, on or before that day.)

Homework and tests from prior semesters are available.