CS 5338: Formal Languages - Fall 2019

Instructor: Byron Gao, bgao@txstate.edu, (512)245-0348, Comal 311D
Lectures: Mondays / Wednesdays 5 - 6:20pm @ Derrick 114C / Avery 365
Office hours: Mondays/Wednesdays 6:30 - 8:30pm after class; Tuesdays 9:30 - 10:30pm after class
Teaching Assistant: Christopher Bell, chris-bell@txstate.edu, Derrick M6, Tuesdays/Wednesdays 3:30-5pm

Textbook: required

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

References: recommended

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

Grading:

Academic honesty: Texas State Academic Honor Code

Outline: subject to change

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