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