---
title: Automata
author: ""
subtitle: ""
format: html
---
# CS 351: Analysis of Algorithms
### Aync
### [Prof. Calvin](mailto:ckdeutschbein@willamette.edu)
### Syllabus
- [Syllabus link](syllabus/syllabus.pdf)
# Calendar
|Week|Date|Lecture|Video|HW|
|:--:|:---|:----|:-------|:-------|
|0x0|01/12|[Aims of Education](00_aims.qmd)|[Video](https://www.youtube.com/watch?v=trabJm8GT0s)|Watch Guest Lecture|
|0x1|01/19|[Quarto](https://cd-public.github.io/python-stack-book/doc/VSCode.html)|[Video](https://www.youtube.com/live/ExpLC4r4H9M?feature=shared)|Make GitHub Pages|
|0x2|01/26|[Finite Automata](01_starfa.qmd)|[Video](https://www.youtube.com/watch?v=PgZxswUfypU)|[Exercise](01_starfa.qmd#exercise)|
|0x3|02/02|[Regular Expressions](02_regexp.qmd)|[Video](https://www.youtube.com/live/PgZxswUfypU?t=4525)|[Exercise](02_regexp.qmd#exercise)|
|0x4|02/09|[Nondeterminism](03_nfas.qmd)|[Video](https://www.youtube.com/live/PgZxswUfypU?t=7341)|[Exercises](03_nfas.qmd#exercise-0)|
|0x5|02/16|[Closures](04_closures.qmd)|[Video](https://www.youtube.com/live/Bx8e0cFMv4c)|[Problem Set 1](https://github.com/cd-public/compute/blob/main/ps/FA_Reg.ipynb)|
|0x6|02/23|[Regularity](05_regularity.qmd)|[Video](https://www.youtube.com/live/Bx8e0cFMv4c?si=o9rCRGxTCiYpmlpH&t=3120)|$\varnothing$|
|0x7|03/02|[Pumping Lemma](06_pump.qmd)|[Video](https://www.youtube.com/live/Bx8e0cFMv4c?si=tmpYkuklpMXzTODU&t=8468)|[Examples](06_pump.qmd#examples)|
|0x8|03/09|[CFG's](07_cfg.qmd)|[Video](https://www.youtube.com/live/Bx8e0cFMv4c?si=hsujmioNzsMG10m1&t=10965)|[Exercise](07_cfg.qmd#exercise)|
|0x9|03/16|[PDA's](08_pda.qmd)|Video `[`[0](https://www.youtube.com/live/HGl6XvfjBXI?si=wQAGZ0dpdPkipTh_&t=4447)`,`[1](https://www.youtube.com/live/nOf4VPbtVeU?si=K3GNoug6LXz24Qtj)`]`|Exercise `[`[0](08_pda.qmd#exercise)`,`[1](08_pda.qmd#exercise-1)`]`|
|0bX|03/23|
|0xA|03/30|[CFG->PDA](09_cfgpda.qmd)|[Video](https://www.youtube.com/live/nOf4VPbtVeU?si=0OX6Q2ozz5jspexI)|[Problems 2.1, 2.2. 2.4](https://github.com/cd-public/compute/blob/main/ps/PDA_CFG_CNF.ipynb)|
|0xB|03/06|[CF Pumping](10_cfpump.qmd)|[Video](https://www.youtube.com/live/qffFOREtze0?si=zTmCRJjc5-sH5sYL)|$\varnothing$
|0xC|04/13|[Turing Machines](11_tm.qmd)|[Video](https://www.youtube.com/live/qffFOREtze0?si=hIFmoAPBc8noqgC4&t=3005)|[Problem 3.1](https://github.com/cd-public/compute/blob/main/ps/TM.ipynb)|
|0xD|04/20|[TM Variants](12_variants.qmd)|[Video](https://www.youtube.com/live/qffFOREtze0?si=t7MzqYyrDh2IAQ4B&t=6648)|[Problem 3.2](https://github.com/cd-public/compute/blob/main/ps/TM.ipynb)|
|0xE|04/29|[Church-Turing](13_thesis.qmd)|[Video](https://www.youtube.com/live/qffFOREtze0?si=DV3ti6S7PLyMu45Y&t=10644)|[Problem 3.3](https://github.com/cd-public/compute/blob/main/ps/TM.ipynb)|
# Lecture Recordings
<iframe width="560" height="315" src="https://www.youtube.com/embed/videoseries?si=pC-m9sxBsXOKhUle&list=PLu3KAnn4RkATkXZsQuk6Fj7p3iqn-iYj1" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>