This is a core undergraduate Computer Science course on the theory of computing. The course introduces the foundations of computer computer science including questions such as “what is computation”, “what are the mathematical models of computing machines”, “what are the formal models to define languages, including syntax of programming languages”, “what is a computable problem”. The course covers these questions and in the process introduces important concepts such as Turing machines, formal languages, models of automata, theory behind parsing (the first stage in a compiler), and algorithms for parsing and design of finite state machines. Topics covered include: finite state automata and regular languages; context free grammars and pushdown automata; Turing machines and computability and computational complexity. This is a theoretical course and requires rigorous mathematical analysis, including deriving formal proofs, which will help you develop your on mathematical and abstraction skills. The lecture, and some lab sessions, will consist of in-class activities and students will be required to work in groups.

Announcements

  • This website is under construction - all content subject to change!

Class Resources

Schedule

Introduction Materials
Week 1-Lecture 1
Chapter 1 (Linz) or Chap.0 (Sipser)
Course Logistics and Syllabus [Meet the instruction team]
Course Intro
Lab Week 1 Review: Proof techniques, Graphs, Sets.
Finite State Automata and Regular Languages Materials
Finite Automata (Weeks 1-2)
Chapter 2 (Linz)
Chapter 1.1-1.2 (Sipser)
Deterministc Finite Automata (DFAs) Example: DFA design(Video)
Non-determinitic Finite Automata (NFA)
NFA example)
JFLAP - NFA Example and Tutorial (Video)
Regular Expressions and Finite Automata
(Week 3) Chap.3
Chapter 1.3 (Sipser)
Regular Expressions - Definitions
Equivalence of Regular Exp and NFAs Example-Video
Regular Grammars
Grammars-Intro(video)
Properties of Reg Languages
(Week 4) Chapter 4 (Linz)
Chapter 1.4 (Sipser)
Closure Properties and Decision Problems
Non-regular Lang-Pumping Lemma
Example-Video
Week 2 Lab Design of DFAs using JFLAP
Week 3 Lab Non-deterministic Finite Automata - JFLAP examples
NFA Review and E-transitions
Week 4 Lab Properties of regular languages - proofs and examples.
Week 5 Lab Review: Finite automata and regular languages
Exam 1 (Week 5) All material on regular languages.
Context Free Languages: Grammars and Automata Materials
Context Free Grammars (Weeks 6-7)
Chap. 5-6 (Linz)
Chapter 2.1 (Sipser)
Intro to grammars and Context Free Grammars
Simplification of Grammars
Chomsky Normal Form and a Parsing Algorithm
CYK Algorithm Example - (Video)
Pushdown Automata (Weeks 7-8)
Chapter 7 (Linz)
Chapter 2.2 (Sipser)
Pushdown Automata
Equivalence of PDAs and CFGs
Properties of Context Free Languages (Week 9)
Chap 8 (Linz) or Chap 2.3 (Sipser)
Pumping Lemma for Context Free Lang
Examples-Video
Ogden’s (Pumping)Lemma-another pumping Lemma:Example
Closure Properties of CFLs
Applications of CFGs
DCFLs and Parsing
Application of CFGs to Malware Detection Algorithms
Week 6 Lab Grammars-Review and Examples
Week 7 Lab CNF Algorithm and Examples
Week 8 Lab PDAs Examples
JFLAP for PDAs- Tutorial (Video)
Week 9 Lab Properties of CFLs- Examples using Pumping Lemma
Week 10 Lab Review
Exam 2 (Week 10) All material on Context Free Languages
Turing Machines and Computability Materials
Turing Machines (Weeks 10-11)
Chapter 9,10 (Linz), Chap 3 (Sipser)
Introduction to Theory of Computation
Introduction to Turing Machine model
Turing Machines to Compute Functions
Other Models of Turing Machines
Non-deterministic TMs and Equivalence with TMs
Computational Complexity-Intro
Computability and Undecidable Problems (Weeks 12-13)
Chap. 11,12 (Linz), Chap.4 (Sipser)
Universal Turing Machine
Closure Properties of RE and Recursive Languages
Decidability and Undecidable Problems
More Undecidable Problems and Rice’sTheorem
Lab Week 11

Lab Week 12
Lab Week 13
Review: Countable and Uncountable Sets
JFLAP Tutorial on TM
TM examples
More TM Examples
Proving Undecidability of Problems
Summary Materials
Course Summary Course Summary
Final Exam Finals Week Comprehensive but will focus primarily on material after Exam 2.