CS 420/520 Automata Theory

Fall 2023

• CRN: 15624 (420) and 15627 (520)
• Room: 260 Condon
• Times: Monday and Wednesday 2:00-3:20pm
• Instructor: Chris Wilson
  • Contact Info: room 326 DES, 346-3412, cwilson@cs.uoregon.edu
  • office hours: room 326 DES, MW 3:45-5:00
  • office hour Zoom link: https://uoregon.zoom.us/j/152119458
• Text: Introduction to the Theory of Computation 2nd Ed (or any edition), by Michael Sipser
  • an errata page, maintained by author
  • at amazon
  • Note: The third edition contains material on deterministic CFLs, which we will not cover.
  • (supplement:) a section of online text by Erickson
• Piazza class page

Evaluation

This will be based on written homework, probably 6 assignments. Two exams - one in-class midterm Wednesday, Nov 1 (tentative) and a take-home final. Assignments 55%, tests 40%, attendance/participation 5%.

Topics and Reading

1. • introduction, fundamentals of computation: Chapter 0
   • DFAs, regular expressions: sections 1.1, 1.3.1
   • regular grammar: regular grammar
2. • NFA, equivalence of NFA and DFA: section 1.2
   • equivalence of DFA and regular expressions: section 1.3
   • pumping lemma: section 1.4
3. • examples, examples
   • pumping lemma variations, more examples
   • DFA state minimization; context free grammars: section 2.1
4. • CFG examples, definitions
   • pushdown automata: sections 2.1, 2.2
   • CFG normal forms
5. • CFG normal forms. CYK algorithm
   • CFGs have PDAs: section 2.2
   • PDAs have CFGs: sections 2.1, 2.2
6. • pumping lemma for context free languages
   • test review
   • midterm Wednesday, Nov 1
7. • more pumping lemma
   • context sensitive grammars (notes)
   • Turing machines, examples
8. • Turing machines, decidable, recognizable languages: section 3.1
   • variations of Turing machines: multi-tape, non-deterministic: section 3.2
   • notion of algorithm, Church-Turing thesis: section 3.3
9. • halting problem: section 4.2
   • halting problem variants, reductions
   • Kolmogorov Complexity the Wed before Thanksgiving (also section 6.4)
   • thanksgiving
10. • recursion theorem, fixed point theorem, Rice's theorem: section 6.1, exercise 5.28

Assignments

• Assignment 1, due Tuesday, Oct 10.
• Assignment 2, due Wednesday, Oct 18.
• Assignment 3, due Thursday, Oct 26.
• Assignment 4, due Saturday, Nov 11.
• Assignment 5, due Monday, Nov 20
• Assignment 6, due Thursday, Nov 30.
• the take-home final exam is due Thursday, Dec 7.

Class Handouts

References

• other texts
  • Formal Languages and Automata, Peter Linz
  • The Language of Machines, Robert Floyd and Richard Beigel
  • Mathematics and Computation (Draft), Avi Wigderson (note to self: PHP p 71, DFA p 179, iO p 247)
• A post discussing whether we should still be teaching the Chomsky Hierarchy.
• regular grammar on wikipedia
• Regular languages are monoids, or worse.
• Myhill-Nerode theorem on wikipedia, see also write-up by Ken Regan and exercises 1.51 and 1.52 of our text
• regular languages from a categorical/algebraic point of view on CS Theory StackExchange
• Turing Categories, finally!
• CYK:
  • on wikipedia
  • a paper on teaching CYK, along with basic algorithm and variants
• the gap theorem.
• nice description of the busy beaver function, too big for TMs.
• map of the main complexity classes (from the petting zoo)
• the arithmetical hierarchy
• Some interesting articles from Godel's Lost Letter blog
  • separating words problem
  • connection of first-order logic and the star-free languages
• The stack construction programming contest problem, which relates to the PDA to CFG construction. (explanation of the recurrence for dynamic programming)
• Lecture notes on reductions and completeness
• interesting articles from Scott Aaronson's Shtetl-Optimized blog
  • MIP*=RE, it's a shocking result!
  • current frontiers of the busy beaver function
  • idiot's guide to the continuum hypothesis
• indistinguishability obfuscators
• Kolmogorov comlexity links:
  • Kolmogorov Complexity basics
  • relevance to cryptography (and the paper)
• programs as data: Exploding Dots meet Kurt Gödel

Comments and Announcements

• The midterm Nov 1 will cover course material up through section 2.2:
  • midterm used in Fall 2021
  • DFA, NFA, regular expressions
  • equivalence of above
  • state minimization (for 551)
  • pumping lemma for regular languages
  • CFG, PDA
  • equivalence of above
  It will not cover the pumping lemma for CFLs.

Attendance

Students here are expected to attend and participate in class. If you expect more than four unexcused absences, please contact the instructor before-hand. Failure to do so will adversely affect your grade and could result in failure.

Academic Honesty

• All projects turned in for the course must be your own work. Copying from other class members or other sources is not acceptable. If you collaborate with someone else on any assignment, you must indicate such on the work you turn in. Collaboration that is not explicitly credited is plagiarism.
• Academic honesty is expected and cases of suspected dishonesty will be handled according to university policy. In particular, copying someone else's work (including material found on the web) will not be tolerated. If solutions to assignments are obtained from outside sources, the source must be cited.
• You are also responsible for protecting your work. That is, you must take reasonable precautions to prevent your work from being copied. This means that if you store your assignment solutions on a shared server, the file permissions must be set to keep others from accessing your files. If you are working on assignments in the lab, you must remove any of your files on the lab machine before you leave.
• Turning in someone else's work is collusion, and is a particularly heinous form of plagiarism; if collusion is detected, all individuals involved (i.e., the copyee and all copyers) will be given a grade of F in the course.