CSIT 379: Computer Science Theory
Fall 2025
Sessions 2 & 3
Embedded Files
Textbooks: None.
References
Introduction to the Theory of Computation (3rd Edition), by Michael Sipser.
Automata, Computability and Complexity: Theory and Applications, by Elaine Rich.
Elements of the Theory of Computation (2nd Edition) by Harry R. Lewis and Christos H. Papadimitriou.
Introduction to Languages and the Theory of Computation (4th Edition) by John Martin.
Recommended reading
Advice on Mathematical Writing, by Kyu-Hwan Lee, University of Connecticut.
No need to purchase any textbooks/reference books of any kind.
Course Materials: Slides and lecture notes to be posted on Canvas and here.
Lectures
Session 2: TR 12 - 1:25 PM
Session 3: TR 2 - 3:25 PM.
Office Hours: TBD.
Tentative Topics
Part I: Regular Languages
Background (sets, functions, strings, languages, grammars, automatons, etc.) and proof techniques (contradiction, induction, pigeonhole principle, dovetailing, diagonalization, etc.)
Deterministic finite automata (DFA)
Non-deterministic finite automata (NFA)
Equivalence of DFA and NFA
DFA minimization
Closure properties of regular languages
Regular expressions
Equivalence of regular expressions and FA
Pumping lemma for regular languages and proofs of non-regular languages
Regular grammars
Part II: Context-free Languages
Context-free grammars (CFG), derivations, and parse trees
Closure properties of CFLs
Normal Forms of CLFs
Nondeterministic pushdown automata (NPDA)
Equivalence of CFG and NPDA
Pumping lemma for CLFs and proofs of non-context-free languages
Part III: Turing Machines
Introduction to Turing machines
Turing machine variants
Turing-decidable languages (TDLs) and Turing-recognizable languages (TALs)
The halting problem and its implications
Turing-unrecognizable language
Reductions and proofs of TDLs and TALs
Recursive and recursively-enumerable sets
The language hierarchy
Google Sites
Report abuse