Computer Science 456/656
Automata and Formal Languages
Fall 2004
Revised August 31, 2004
-
Instructor:
-
Dr. Larmore
- Office, TBE B378B. Telephone, 702-895-1096, larmore@cs.unlv.edu
- Office Hours:
-
Tuesdays 10:00-11:00 AM
-
Thursdays 8:30-9:30 AM
-
Tuesdays and Thursdays 7:00-7:30 PM
-
Contacting Me:
- It's best to send me email at
larmore@cs.unlv.edu. Be sure to write "CS456" (or "CSC656")
in the subject field
so that I know what the message is about. (I delete lots of messages
without reading them, based on the subject fields.)
-
You may also telephone my office and leave a message.
-
Please, never try to communicate with me by leaving notes on my
door, under my door, or in my mailbox in the department office, as
those notes get lost, and I can't retrieve them remotely.
-
Graduate Assistant:
- Doina Bein.
-
Days of Instruction:
- August 31, 2004 - December 9, 2004.
-
Time of Instruction:
- 4:00 - 5:15,
Tuesday and Thursday.
- Holidays: November 11, November 25.
-
Place of Instruction:
- TBE B178.
-
Final Examination:
- Tuesday, December 14, 6:00 - 8:00 PM.
-
Textbook:
-
Introduction to the
Theory of Computation, by Michael Sipser. PWS. ISBN 0-534-95651-3.
-
Prerequisites:
-
CSC 269 (Introduction to Data Structures), currently relabeled as CS 302.
-
MAT 351 (Discrete Mathematics II).
-
Click here
if you did not take both
CSC 269 (currently CS 302) and MAT 351 at UNLV and
receive a grade of "C" or better in each of those two courses.
-
Graduate Students:
-
If you want graduate credit, you must enroll in 656, not 456.
-
Compiler Construction:
-
CS 456/CSC 656 is a prerequisite for CS 460/CSC 678 (Compiler Construction).
-
I do not
advise you to try to take that course concurrently. (Usually, we
schedule the courses simultaneously to make it impossible, but this
Semester we didn't.)
-
Written Homework:
-
will be assigned, collected, and graded.
You are permitted to discuss homework.
-
Examinations:
-
First examination will be (to be announced).
-
Second examination will be (to be announced).
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, 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, and I will prove
that to you.
-
Computable. There are functions which cannot be implemented by
any machine that could ever be built.
-
"But they told the Wright brothers that a flying machine was
impossible."
-
P = NP? The most famous open question in all of computer
science. What does this mean? What does it mean in practical terms?
Detailed description of the CYK algorithm.
Homework and
tests from prior semesters are available.