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. This is a theoretical course and requires rigorous mathematical analysis, including deriving formal proofs, which will help you develop your on mathematical, abstraction and problem solving 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 Introduction
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-determinism: Non-deterministic Finite Automata (NFA)
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
Properties of Reg Languages
(Week 4) Chapter 4 (Linz)
Chapter 1.4 (Sipser)
Closure Properties and Decision Problems
Proving Non-regularity - Pumping Lemma
Example-Video
Summary-Regular Languages
Week 2 Lab Design of DFAs using JFLAP
Wrong DFA for “OR”
Correct DFA for “OR”
Week 3 Lab Non-deterministic Finite Automata - JFLAP examples
NFA and RE Review
Week 4 Lab Properties of regular languages - proofs and examples.
Week 5 Lab Review: Finite automata and regular languages
Exam 1 (Week 5) Feb.10 All material on regular languages.
Context Free Languages: Context Free Grammars and Pushdown Automata Materials
Pushdown Automation and Context Free Grammars (Weeks 6-7)
Chap. 5, 7 (Linz)
Chapter 2.2 (Sipser)
Pushdown Automata
Intro to Context Free Languages & Grammars
Deterministic PDAs and Parsing
Context Free Grammars (Weeks 7-8)
Chap. 5-6 7 (Linz)
Chapter 2.1 (Sipser)
Context Free Grammars and Normal Forms
Parsing: A Parsing Algorithm
CYK Parsing Algorithm Example - (Video). Provided by Grant McClearn
Properties of Context Free Languages (Weeks 9-10)
Chap 8 (Linz) or Chap 2.3 (Sipser)
CFL Properties- Pumping Lemma for Context Free Lang
Examples-Video
Ogden’s (Pumping)Lemma-another pumping Lemma:Example
Closure Properties of CFLs
Week 6 Lab PDAs examples and Exercises
JFLAP for PDAs-Tutorial (Video)
Week 7 Lab Examples and Review of CFGs
Week 8 Lab Review of Grammars, Parsing
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-12)
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 13-14)
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
JFLAP Tutorial on TM
TM examples
Review: Countable and Uncountable Sets & Multitape TM
Review: Non-Determinism and Diagonalization
Proving Undecidability of Problems
Quiz 9-10
Summary Materials
Course Summary Course Summary
Final Exam Finals Week Comprehensive but will focus primarily on material after Exam 2.