CS 5338: Formal Languages - Fall 2018

Instructor: Byron Gao, bgao@txstate.edu, (512)245-0348, Comal 311D
Lectures: Mondays / Wednesdays 5 - 6:20pm @ ALK 119 / AVRY 366
Office hours: Mondays/Wednesdays 6:30 - 8pm after class; Tuesdays 5 - 6:30pm before class and 9:30 - 10pm after class
Teaching Assistant: Christopher Bell, chris-bell@txstate.edu, Derrick Mezzanine M13, Tuesdays/Wednesdays 3-4:30pm

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 27/29 Mathematical background Appendix A AppA.pdf a1.doc due Sep 10 5pm
2 Sep 3/5 Languages and strings Chapter 2 ch2.pdf Sep 3 Labor Day no class
3 Sep 10/12 The big picture: a language hierarchy Chapters 3-4 ch3-4.pdf a2.doc due Sep 19 5pm
4 Sep 17/19 Finite State Machines Chapter 5 ch5.pdf a3.doc due Oct 1 5pm
5 Sep 24/26        
6 Oct 1/3 Regular expressions/grammars
Regular and nonregular languages
Chapters 6-7
Chapter 8
ch6-7.pdf
ch8.pdf
tutorial.pdf; mini.doc due Oct 15 5pm
a4.doc due Oct 15 5pm
7 Oct 8/10 Context-free grammars Chapter 11 ch11.pdf a5.doc due Oct 29 5pm
8 Oct 15/17 Pushdown automata
Context-free and non-context-free languages
Chapter 12
Chapters 13-14
ch12.pdf
ch13-14.pdf
 
9 Oct 22/24 Turing machine Chapter 17 ch17.pdf a6.doc due Nov 28 5pm
10 Oct 29/31 Church-Turing thesis; Halting problem; D and SD; Reduction Chapters 17-20 ch18-21.pdf  
11 Nov 5/7 Complexity Chapters 27-28 ch27-28.pdf  
12 Nov 12/14        
13 Nov 19/21       Nov 21 Thanksgiving no class
14 Nov 26/28 Review   review.pdf online course evaluation due Dec 7
15 Dec 3 Final1     4-6:20pm
16 Dec 7 Final2     5-7:30pm