Topics to be Covered in CS 456/656

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.

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.