Computer Science 456/656
Automata and Formal Languages
Spring 2001

Revised January 17, 2001.

• Instructor: Dr. Larmore Office, TBE B378B. Telephone, 702-895-1096, larmore@cs.unlv.edu
• Office Hours: 10:00 to 11:30 A.M., Mondays and Wednesdays.
• Graduate Assistant: Doina Bein siona@cs.unlv.edu
  • Office, CEB 399J. Telephone, 702-895-1634.
  • Office Hours: (To be announced)
• Room and Time: TBE A107, Mondays and Wednesdays, 4:00 PM to 5:15 PM.
• Days of Instruction: January 17, 2001 -- May 2, 2001.
• Holidays: February 19, March 12, March 14.
• Final Examination: May 9, 2001, 6:00 PM. (Note that College of Engineering Final Examinations may have different times than examinations for other courses.)
• 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).
  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 January 24. (If you cannot attend class that day, leave your homework, in an envelope, with one of the office staff, on or before that day.)

Turing Machine Emulation