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
- Piazza
- Blackboard
- JFLAP
- JFLAP tutorial and installation video (provided by Grant McClearn, Class of 2021; currently at Stanford)
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. |