Computer Science 456/656
Automata and Formal Languages
Fall 2000
Revised September 21, 2000.

-
Instructor:
Dr. Larmore
Office, TBE B378B. Telephone, 702-895-1096, larmore@cs.unlv.edu
-
Office Hours: 2:00 pm - 3:30 pm, Tuesdays and Thursdays.
-
Graduate Assistant:
Doina Bein siona@cs.unlv.edu
-
Office, CEB 399J. Telephone, 702-895-1634.
-
Office Hours: 10:00 am - 1:00 pm, Tuesdays and
3:00 pm - 5:00 pm, Wednesdays.
-
Room and Time: TBE B172,
Tuesdays and Thursdays, 4:00 PM to 5:15 PM.
-
Days of Instruction: August 28, 2000 -- December 7, 2000.
-
Holiday: November 23.
-
Final Examination: Time to be announced.
(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).
-
CSC 456/656 is a prerequisite for CSC 478/678 (Compiler Construction).
-
If you want graduate credit, you must enroll in 656, not 456.
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!)
-
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?
Today's Lecture Topics.
Written Homework
will be assigned, collected, and graded.
You are permitted to discuss homework. The first assignment
will be found on the web page (follow a link on this page)
and will be collected
in class Setember 5. (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.
Turing Machine Emulation
