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

- Piazza
- Blackboard
- JFLAP
- JFLAP tutorial and installation video
- [JFLAP tutorial on NFA, now available in Week 3 Lab]

## 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. |