Computer Science 456/656
Automata and Formal Languages
Fall 2002

Check the Assignments and Lecture Topics Page frequently.

Revised November 21, 2002.

• Instructor: Dr. Larmore Office, TBE B378B. Telephone, 702-895-1096, email: larmore@cs.unlv.edu
• Office Hours: 9:30 to 11:00 A.M., Tuesdays and Thursdays.
• Graduate Assistant: Dawn Liang
• Room and Time: TBE A107, Tuesdays and Thursdays, 4:00 PM to 5:15 PM.
• Days of Instruction: August 27, 2002 -- December 7, 2002.
• Holiday: November 28
• Mid-term examinations: September 26, October 31.
• Final Examination: Tuesday December 10, 2002, 6:00 - 8:00 PM. (Note that College of Engineering Final Examinations may have different times than examinations for other courses.)
• Introduction to Automata Theory, Languages, and Computation, by John E. Hopcrof, Rajeev Motwani, and Jeffrey D. Ullman.
• Prerequisites: CSC 269 (Introduction to Data Structures) and MAT 351 (Discrete Mathematics II).
  Click here if you did not take both CSC 269 and MAT 351 at UNLV and receive a grade of "C" or better in each of those two courses.
• CSC 456/656 is a prerequisite for CSC 478/678 (Compiler Construction).
• If you want graduate credit, you must enroll in 656, not 456.

• Automaton.
• Language. (You may have thought you knew this one!)
• Grammar. (You probably thought you knew this one, too!)
• Computable. There are functions which cannot be implemented by any machine that could ever be built.

  Perhaps you have heard that progress will make the "impossible" possible, like flying. But there are limits. For example, you could not write a function in any computer language which would implement the "busy beaver" function.

• 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, but few can give a precise definition.
• 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 collected in class September 3.

Detailed description of the CYK algorithm.