CS467: Theory of Computation (Autumn 2017)

Announcement

(Introduction to CS467)

PART I: Automata and Language

  1. Finite automata and regular language(pdf)
  2. Pushdown automata and context free language(pdf)
  3. (*) Deterministic Context-Free Languages (pdf)

PART II: Computability

  1. The Church-Turing Thesis (pdf)
  2. Decidability (pdf)
  3. Reducibility (pdf)

PART III: Computational Complexity

Assignments

  1. Textbook, Chapter 1, Exercises and Problems: 1.5 (a,d); 1.6 (e,l); 1.11; 1.17.
  2. Textbook, Chapter 1, Exercises and Problems: 1.29; 1.31; 1.66.
  3. Textbook, Chapter 2, Exercises and Problems: 2.4 (a,b,c); 2.9; 2.14.
  4. Textbook, Chapter 2, Exercises and Problems: 2.15; 2.16; 2.30(c); 2.33.
  5. Textbook, Chapter 3, Exercises and Problems: 3.6; 3.9; 3.15.
  6. Textbook, Chapter 4, Exercises and Problems: 4.1; 4.3; 4.5.
  7. Textbook, Chapter 4, Exercises and Problems: 4.7; 4.13; 4.16; 4.25.
  8. Textbook, Chapter 5, Exercises and Problems: 5.1; 5.2; 5.28.

References

Last updated: Sep. 4, 2016

7