Review of Topics

CS 3810 – Summer 2008

  1. Regular Languages

    1. Deterministic Finite Automata (DFAs) and Transition Diagrams

    2. Nondeterministic Finite Automata and the Subset Construction

    3. ε-Transitions

    4. Regular Expressions and Equivalence to DFAs

    5. The Pumping Lemma for regular languages

    6. Regular Language Closure Properties

    7. Finding a Minimum DFA

  2. Context-Free Languages (CFLs)

    1. Context-Free Grammars (CFGs)

    2. Derivations and Sentential Forms

    3. Parse Trees & Parsing

    4. Ambiguity

    5. Pushdown Automata & Equivalence to CFGs

    6. Deterministic Pushdown Automata

    7. Eliminating Useless Symbols; Eliminating ε-Productions; Eliminating Unit-Productions

    8. Chomsky Normal Form

    9. The Pumping Lemma for CFLs

    10. Closure Properties for CFLs

  3. Turing Machines (TMs)

    1. Finite Control & Infinite Tape

    2. Instantaneous Descriptions (IDs)

    3. Multi-Tape TMs & Nondeterministic TMs

    4. Two-Stack Machines & Counter Machines

    5. Recursive & Recursively Enumerable (RE) Languages

    6. Decidable vs. Undecidable

    7. The Language Ld & the Language Lu

    8. Rice's Theorem

    9. Post's Correspondence Problem

  4. P vs. NP

    1. Definitions

    2. Polynomial-Time Reduction

    3. NP-Completeness