CS 3378: Theory of Automata - Fall 2017

Instructor: Byron Gao, bgao@txstate.edu, (512)245-0348, Comal 311D
Lectures: Tuesdays 6:30 - 9:20pm @ ALK 119 / AVRY 366
Office hours: Mondays noon - 5pm
Teaching Assistant: Christopher Bell, chris-bell@txstate.edu, Comal 309J, Tuesdays 3-5pm

Textbook: required

Automata, Computability, and Complexity: Theory and Applications
Elaine Rich
Prentice Hall, 2008
ISBN: 9780132288064

References: recommended

Introduction to the Theory of Computation, 2rd edition
Michael Sipser
Course Technology, 2006
ISBN: 9780534950972
Introduction to Automata Theory, Languages, and Computation, 3rd edition
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman
Addison Wesley, 2006
ISBN: 9780321462251
Elements of the Theory of Computation, 2rd edition
Harry R. Lewis and Christos H. Papadimitriou
Prentice Hall, 1997
ISBN: 9780132624787

Grading:

TBD
Academic honesty: Texas State Academic Honor Code

Topics: will cover most, but not all, of the following:

  1. Why study the theory of computation
  2. Languages and strings
  3. Language hierarchy
  4. Computation
  5. Finite-state machines
  6. Regular expressions
  7. Regular grammars
  8. Regular and nonregular languages
  9. Context-free grammars
  10. Pushdown automata
  11. Context-free and noncontext-free languages
  12. Turing machines
  13. Unsolvability of the halting problem
  14. Decidable and semidecidable languages
  15. Reduction
  16. Analysis of complexity
  17. Time complexity classes
  18. Space complexity classes

Outline: subject to change

Week Date Topics Readings Notes Events
1 Aug 29 Mathematical background Appendix A AppA.pdf a1.doc due Sep 12 6pm
2 Sep 5 Languages and strings Chapter 2 ch2.pdf  
3 Sep 12 The big picture: a language hierarchy Chapters 3-4 ch3-4.pdf a2.doc due Sep 19 6pm
4 Sep 19 Finite State Machines Chapter 5 ch5.pdf a3.doc due Oct 3 6pm
5 Sep 26        
6 Oct 3 Regular expressions/grammars
Regular and nonregular languages
Chapters 6-7
Chapter 8
ch6-7.pdf
ch8.pdf
tutorial.pdf; mini.doc due Oct 17 6pm
a4.doc due Oct 17 6pm
7 Oct 10        
8 Oct 17 Context-free grammars Chapter 11 ch11.pdf a5.doc due oct 31 6pm
9 Oct 24 Pushdown automata
Context-free and non-context-free languages
Chapter 12
Chapters 13-14
ch12.pdf
ch13-14.pdf
 
10 Oct 31 Turing machine Chapter 17 ch17.pdf a6.doc due Nov 28 6pm
11 Nov 7 Church-Turing thesis; Halting problem; D and SD; Reduction Chapters 18-21 ch18-21.pdf  
12 Nov 14 Complexity Chapters 27-28 ch27-28.pdf  
13 Nov 21        
14 Nov 28 Review   review.pdf  
15 Dec 5 Final1     last lecture
16 Dec 12 Final2     8-10:30pm