University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page

Computer Science 456/656
Automata and Formal Languages
Fall 2018

Check the Assignments and Lecture Topics Page frequently.

Instructor:
Dr. Larmore
Office, TBE B378B. Telephone ☎ 702-895-1096. Email: larmore "at" egr "dot" unlv "dot" edu
Office Hours:
10:00 - 11:00 and 1:00 - 2:00: Mondays and Wednesdays.
Contacting Me:
You may telephone my office. Please do not leave a telephone message.
It's best to send me email. Be sure to write "CS456" (or "CS656") 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.)
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.
If it is necessary to give me something, please leave it with the department staff, and then send me an email message saying that the item has been left for me.
Graduate Assistant:
Shekhar Singh
Email: shekhar.singh "at" unlv "dot" edu
Office Hours: Tuesdays and Thursdays, 10:00 to 1:00 Room TBE346 or TBE361 (check both)
Office: TBE B346
Days of Instruction:
August 27, 2018 - December 5, 2018.
Time of Instruction:
11:30 - 12:45, Monday and Wednesday.
Place of Instruction:
TBE B174.
Textbook:
Introduction to the Theory of Computation, by Michael Sipser. PWS.
We are using the most recent edition, which is the third. However, if you have the first or second edition, that will be acceptable.
Prerequisites:
CS 302 (Data Structures)
MAT 351 (Discrete Mathematics II).
Click here if you did not take both CSC 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.
Each CSC 656 student must turn in at least one challenge problem and turn it in by the last week of class. CS 456 students are also permitted to work challenge problems, but I will not permit students to improve a poor grade in this manner. The reason for this policy is that I want students who are doing poorly in the course to devote their energy to mastering the regular material.
Compiler Construction:
CS 456/656 is a prerequisite for CS 460/CS 678 (Compiler Construction).
I do not advise you to take that course concurrently.
Written Homework:
will be assigned, collected, and graded. You are permitted to discuss homework.
Examinations:
First Examination: Wednesday, September 19.
Second Examination: Wednesday, October 17
Third Examination: Wednesday, November 14
Final Examination: 10:10 - 12:10 Wednesday December 12
Grading:
Your grade will be based on:
  • The examinations. 60%
  • The homework. 5%
  • The final examination. 35%
Although the homework will take a substantial amount of time to work, and will actually be harder than the examinations, it counts for a smaller part of the grade. The reason for this is that I allow you to work together on homework. If you work the homework regularly, you should do well on the examinations.
Topics to be Covered:
  • Formal Languages.
    1. Symbols.
    2. Alphabets.
    3. Strings.
      1. ε, the Empty String.
    4. Languages.
      1. Union.
      2. Concatenation.
      3. Kleene Closure.
      4. Atomic Languages.
        1. {ε}, the Language Whose Only Member is ε.
        2. {a}, the Language Whose Only Member is the String a.
        3. Confusion Alert! If a is a symbol, then a denotes two different things: the symbol a, and the string of length one whose only symbol is a.
        4. ∅, the Empty Language.
        5. Confusion Alert! The empty language is not same as the language whose only member is the empty string.
  • Regular Languages and Finite Automata.
    1. Deterministic Finite Automata (DFAs).
      1. States.
      2. Transitions.
      3. Start State, Computations.
      4. Final States, Acceptance.
      5. Dead States.
      6. Minimal DFAs, Moore's Algorithm.
    2. Regular Expressions.
      1. Confusion Alert! In a regular expression, the symbol ε does not denote the empty string. Instead, it denotes {ε}, the language which has one member, the empty string.
    3. Myhill Nerode Theorem
    4. Non-deterministic Finite Automata (NFAs).
      1. ε-Transitions.
      2. Equivalence of DFAs, NFAs, and Regular Expressions.
        1. Powerset Construction.
    5. The Pumping Lemma.
      1. What is it Used For?
  • Context-Free Languages and Grammars.
    1. Context-Free Grammars.
      1. Variables and Terminals.
      2. Derivations.
      3. The Language Generated by a Context-Free Grammar is a Context-Free Language.
      4. Equivalent Context-Free Grammars.
      5. Chomsky Normal Form.
      6. Ambiguous Context-Free Grammars.
      7. Confusion Alert! There is no such thing as an "Ambiguous Context-Free Language." If a language has an unambiguous context-free grammar, it also has an ambiguous context-free grammar.
      8. Inherently Ambiguous Context-Free Languages. However, there are some context-free languages that have no unambiguous context-free grammar.
    2. Every Regular Language is Context-Free, but not Vice-Versa.
    3. Union, Contanenation, and Kleene Closure.
    4. Push-Down Automata (PDAs).
      1. Stack, Input Stream, Finite Control.
      2. Non-Deterministic.
      3. Accepting Computations.
        1. Read, Pop, Push, Change State.
        2. Read Entire Input.
        3. By Final State.
        4. By Empty Stack.
        5. By Final State and Empty Stack.
        6. These Three are Equivalent.
      4. Chomsky's Theorem: The Class of Languages Accepted by PDAs is the Class of Context-Free Languages.
      5. Deterministic Push-Down Automata (DPDAs) and Deterministic Context-Free Languages.
    5. Pumping Lemma for Context-Free Languages.
    6. Applications.
      1. Algebraic Languages.
      2. Programming Languages.
  • Parsing.
    1. Non-determistic parsing.
    2. LALR parsing.
  • Turing Machines and Decidability.
    1. The Church-Turing Thesis.
    2. Reduction and Undecidability.
    3. The Diagonal Language.
    4. The halting problem is undecidable.
    5. There exist mathematical statements that are true but have no proof.
    6. A few other undecidable problems.
    7. Computable and uncomputable functions. There exist well-defined mathematical functions which cannot be computed. For example, the busy beaver function.
  • Complexity Theory.
    1. 0-1 Problems.
    2. Reduction and NP-Completeness.
    3. The class P-TIME.
    4. The class NP-TIME.
    5. Guide Strings.
    6. Certificates = Witnesses.
    7. NP-Complete Problems.
      1. SAT.
      2. 3-SAT.
      3. The Clique Problem. (The Luce-Perry Problem.)
      4. The Independent Set Problem.
      5. The Knapsack Problem.
      6. The Partition Problem.
    8. Other topics.
      1. The class P-SPACE.
      2. Nick's Class.
      3. The Boolean Circuit Problem.


    • 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. The plural of "automaton" is "automata." [Greek]
    • Language. (You may have thought you knew this one!)
    • Grammar. (You probably thought you knew this one, too!)
    • Turing Machine.
    • Universal Turing Machine. A 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 and Uncomputable Functions. There are functions which cannot be computed by any machine that could ever be built.
    • 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.