| Instructor: | Andrew L. Mackey |
|---|---|
| Meeting Times: | Tuesdays/Thursdays at 11:00 - 12:15 pm Tuesdays/Thursdays at 6:50 - 8:05 pm |
| Location: | Baldor 147 |
| Graduate Assistant: | Adrian Cuevas |
| Lab Times: | TBD |
This course introduces fundamental concepts in automata theory and formal languages. Topics include finite automata, pushdown automata, regular expressions, grammars, formal languages, context-free languages, Turing machines, and Church’s thesis. The course also presents applications of these models to algorithms, complexity theory, and compiler design.
Students are required to have a prior background in object-oriented programming languages (e.g. Java, C++, etc.), working knowledge of data structures, and discrete mathematics.
Required Courses: CS 2003 - Data Structures and MATH 2443 - Discrete Mathematics I
The follow represents a tentative schedule of topics.
| Week | Topic | Notes |
|---|---|---|
| 1 | Course Introduction | Quick Review of Sets, Functions, Quantifiers, and Logic |
| 2 | Regular Languages, DFA, and NFA | |
| 3 | Regular Expressions, GNFA, Equivalence, Minimization | |
| 4 | Non-regular Languages | |
| 5 | Context Free Languages and Grammar | |
| 6 | CNF and Pushdown Automata | |
| 7 | Non-context-free Languages | |
| 8 | Decidable Languages and Turing Machines | |
| 9 | Decidable Languages and Turing Machines (cont.) | |
| 10 | Computability Theory | |
| 11 | Undecidable Problems and Reduction | |
| 12 | Undecidable Problems and Reduction (cont.) | |
| 13 | Complexity Theory | |
| 14 | Complexity Theory (cont.) | |
| 15 | Complexity Theory (cont.) | |
| 16 | Final Examination |
The following textbook is assigned to this course:
The following resources are available for students to use.
Review the course website for more information