Theory of Automata, Formal Languages, and Computation Fall 2024

Theory of Automata, Formal Languages, and Computation

CS 3252 and CS 5252
Fall 2024

Time and Place: TTh 2:45 PM to 4:00 PM, FGH 132

Instructor: Douglas H. Fisher (Doug, Professor/Dr Fisher, Professor/Dr Doug) douglas.h.fisher@vanderbilt.edu

Instructor Office hours: See the Fall 2024 hours posted at https://my.vanderbilt.edu/douglasfisher/.

TA: TBA

TA Office Hours: TBA

Course Overview: This course is fundamentally on finite representations of infinite languages, where the representations are amenable to computational analysis and formal characterization. That’s it in a nutshell. The rest of this course fleshes out this nutshell in considerable detail. The details are in the form of various kinds of grammars for infinite languages, such as context-free grammars and context sensitive grammars; automata of various kinds that recognize languages, such as finite-state automata, pushdown automata, and Turing machines; and formal computational characteristics of languages, notably (un)decidability and computational complexity of tests of membership in various languages. Prerequisite: CS 2212.

Course materials

Most of what you need to know will be in lectures, slides, and the online textbook on Wikibooks (link: https://en.wikibooks.org/wiki/Theory_of_Formal_Languages,_Automata,_and_Computation). Slides with skeletal content will be available on Top Hat in advance of lectures. For those of you who love the material, particularly more formalism, I recommend that you have one of the texts in the classic lineage of Hopcroft and Ullman.

  • Formal Languages and their Relation to Automata by John E. Hopcroft and Jeffrey D. Ullman, Addison Wesley, 1969.
  • Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffrey D. Ullman, Addison Wesley, 1979.
  • Introduction to Automata Theory, Languages, and Computation, 3rd Edition by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addison Wesley, 2007.

The course schedule (below) lists the required readings from the Wikibook for each week.

Other Materials: You will be reading other papers, watching videos, and listening to podcasts throughout the semester. These are listed in the course schedule below for each week. Over Summer I emailed preregistered students suggesting that they take the Vanderbilt-Coursera course on prompt engineering. You can still work it in to your schedule (optional) and it will come up in class and discussion, along with two papers along the same lines (“ChatGPT Prompt Patterns for Improving Code Quality,
Refactoring, Requirements Elicitation, and Software Design“, “A Prompt Pattern Catalog to Enhance Prompt Engineering with ChatGPT“).

Course Organization

The course requires attendance in class, homework, exams, a project, and encourages you to participate in discussion, even if only to read the posts.

Attendance in class is required, not just by me but by School of Engineering policy. I will take attendance with Top Hat and I will sometimes ask questions on Top Hat, where participation and correctness of your answers will be factored into your grade. So bring a device that allows you to interact with Top Hat. See more about grading of attendance under Grading.

There are two exams during the semester, each of which covers an interval of material, as well as a comprehensive final exam. Our final exam is scheduled for Tuesday, December 10 at 9:00 am – 12:00 Noon CENTRAL TIME. There are no alternative times. At least some component of each exam, perhaps an entire exam, will be on Brightspace and will be autograded (so bring your laptops or other suitable device).

We will be using Piazza as the class discussion forum. The TA and I will typically use Piazza to make announcements too. If you have not been previously enrolled by me, you can join the class forum by following the Piazza link. The discussion forum is for students to ask questions and give comments on any aspect of the course. The TA and I will respond as appropriate, but students are encouraged to respond too. We also encourage knowledge sharing of ideas, specifications, prompts, and designs regarding the project. In general, students can and should be learning from other students in this course. There may also be prompts from me and the TA for questions and comments regarding the my slides and instructor notes, source reference texts, practice problems, the programming project, and societal issues of current relevance. And if you find an interesting paper or topic, then feel free to post that, along with your commentary.

A project will dominate the last weeks of class. This is intended to be project that allows you to dive more deeply into an issue or problem that interests you in an area relevant to this course. The project can be a programming project (e.g., a recursive-descent compiler for a programming language, an AI theorem prover), or it can be research into a theoretical question (e.g., formally characterizing the class of inherently ambiguous languages). It is intended as an individual project, but I will entertain proposals for a group project of two students. We will talk more as the semester unfolds.

Homework is elaborated in its own section below.

Homework

There is regular homework, which is available on Top Hat. There are two aspects to each homework. You are given questions that ask for open format answers (e.g., show a proof for X). You will turn in a pdf of your open format answers to Brightspace under Assignments. But for primary purposes of grading you will take a “quiz” on those questions, or close approximations, as well as other material from lectures and textbook.

  • You must submit the open format pdf BEFORE you take the quiz portion of the homework.
  • You will take the quiz portion of the homework for the first time IN CLASS on Wednesdays. You take the quiz component on Brightspace, so have uploaded the free form before class and bring your laptops or other suitable device.
  • You can take the quiz component on Brightspace (under Quizzes) one additional time until Wednesday midnight.
  • Your grade on the quiz component is the average of your quiz attempts, either one or two attempts.

The TA and I may consult the free-form answer under Assignments to check your work (and in particular, don’t game the system by uploading irrelevant material). We may adjust the homework score accordingly but the default is that your score is reflected entirely by the quiz component of a homework. Think of the free-form version as “showing your work” for the quiz version that will actually count as your grade. See us if you think that your free form answers show a greater degree of understanding than what was suggested by the quiz component — examination of the free form can raise, as well as lower, your grade, but either change is an exception rather than the rule.

Grading

  • Attendance and in-Class (Top-Hat) Questions: 5% or more
  • Exam 1: 15%
  • Exam 2: 15%
  • Final Exam: 20%
  • Project: 15%
  • Homework: 30%

Again, in-class attendance is required. If you attend all classes (as recorded on Top Hat at the start of class), excepting previously-excused absences, then attendance counts for 5% of your grade. If you miss all classes, then your (lack of) attendance counts for 30% of your grade (i.e., 0%/30%), with the extra 25% taken proportionally out of the weights of other factors. Intermediate between perfect attendance and zero attendance is something intermediate, which will effect the factor weight and percentage attendance proportionally. If you record yourself present on Top Hat from outside the classroom then that is an honor offense.

The letter grade breakdown is

  • [93, 100] A (a very few A+s may be given)
  • [90, 93) A-
  • [88, 90) B+
  • [83, 88) B
  • [80, 83) B-
  • [78, 80) C+
  • [73, 78) C
  • [70, 73) C-
  • [68, 70) D+
  • [63, 68) D
  • [60, 63) D-
  • [0, 60) F

Honor Code

Fundamentally, the honor code is about giving credit to others where credit is due, which allows for a more accurate assessment of your knowledge and it better ensures community trust and the societal benefits that stem from that trust.

For this class

  • you may NOT consult texts, notes, slides, AIs, or with others when you take exams (nothing, except your own brain);
  • you MAY consult with texts, notes, slides, AIs, and with others on the open format components of homework, but you must precisely declare the nature of any help you received or gave to other people (and from/to whom) in the open format submission; your grade may be adjusted based on the nature of help from other people, but its unlikely; the same need to precisely declare help from an AI is not required, but I would be interested to hear about it, perhaps on the free form submission;
  • you may NOT consult with texts, notes, slides, AIs, other people while you are actually taking a quiz attempt, but you can consult sources (except other people) between attempts;
  • you must be in the classroom for class if you respond that you are present on Top Hat.

Schedule

Week 1 Overview and Basics

Week 2: Grammars and languages

  • Read
  • Do Week 2 Homework Free Form due Tuesday September 3 before class (See Top Hat)
  • Class meetings
    • Tuesday, August 27: Quiz HW1; Unrestricted grammars and languages; Context-Sensitive Grammars (CSGs) and Languages (CSLs); Context-free grammars (CFGs) and languages (CFLs), derivations; Markov Algorithms;
    • Thursday, August 29:  Context-free grammars and languages continued, including parse trees, ambiguity,  normal forms, inherent ambiguity

Week 3: Regular languages and automata

  • Read
  • Do Week 3 Homework Free Form due Tuesday September 10 before class (See Top Hat)
  • Class meetings
    • Tuesday, September 3: Quiz HW2; Pumping Lemma for CFLs; Regular Grammars (RGs) and Languages (RLs), the Pumping Lemma for RLs, Chomsky hierarchy
    • Thursday, September 5: Deterministic (DFA) and nondeterministic (NFA) finite automata; equivalences of regular grammars, DFAs, and NFAs

Week 4: Finite Automata, Regular Expressions, and Regular Languages

  • Read
  • Do Week 4 Homework Free Form due Tuesday September 17 before class (See Top Hat)
  • Class meetings
    • Tuesday, September 10: Quiz HW3; NFAs with epsilon moves; equivalence of NFAs with epsilon transitions and DFAs; Regular Expressions (REs) and Regular Languages;
    • Thursday, September 12:  equivalences between FAs and REs; Pumping Lemma for RLs revisited; DFA minimization; equivalence algorithm for RLs;

Week 5: Pushdown Automata and CFLs

  • Read
  • Do Week 5 Homework Free Form due Tuesday September 24 before class
  • Class Meetings
    • Tuesday, September 17: Quiz HW4; Pushdown Automata (PDAs) and CFLs; Applications of CFGs and RGs to programming languages
    • Thursday, September 19: PDAs and CFLs; Deterministic (DPDA) and Deterministic CFLs (DCFLs); Turing Machines

Week 6: Turing Machines

  • Read
  • Do Week 6 Homework Free Form due Tuesday October 1 before class
  • Class Meetings
    • Tuesday, September 24: Quiz HW5; Turing machines as recognizers; instananeous descriptions; halting and decidability; Recursive and Recursively Enumerable languages
    • Thursday, September 26:  Turing machine programming; Turing machines as  enumerators and function computers;

Week 7: Universal TM and beyond algorithms and RE; Exam

  • Read
  • Do Week 7 Homework Free Form due Tuesday October 8 before class
  • Class Meetings
    • Tuesday, October 1: Quiz HW6; TM encoding, Universal TM, a non-recursive language; the diagonal language (not RE), Random” languages (musings);
    • Thursday, October 3:  Exam 1 (August 22 – September 26).

Week 8: Properties of Language Classes

  • Read
  • Do Week 8 Homework Free Form due Tuesday October 15 before class
  • Class Meetings
    • Tuesday, October 8: Closure Properties and decision properties of RLs, CFLs, Recursive languages
    • Thursday, October 10:  Fall break

Week 9: Computational Complexity, P and NP, NP Completeness

  • Read
  • Do Week 9 Homework Free Form due Tuesday October 22 before class
  • Class Meetings
    • Tuesday, October 15: Algorithm efficiency (Recursive languages); Reductions
    • Thursday, October 17: Intractability, P and NP; Polynomial Reductions; NP hard and complete problems; SAT; Learnability

Week 10: finish NP Completeness; Properties of RE Languages

  • Read
  • Watch
  • Do Week 10 Homework Free Form due Tuesday October 29 before class
  • Class Meetings
    • Tuesday, October 22: Quiz HW9; Cook’s Theorem; randomized algorithms, primality testing;
    • Thursday, October 24:   Closure properties of RE languages, (un)decidability; Decision Properties of RE languages, Rice’s Theorem

Week 11: Applications of Languages, including AI

  • Read
  • Do Week 11 Homework Free Form due Tuesday November 5 before class
  • Class Meetings
    • Tuesday, October 29: Quiz HW10; Applications of language classes, including AI and Formal Languages
    • Thursday, October 31: AI and Formal Languages
  • Project proposal due (submit to Brightspace) Saturday, November 2 11:59 pm

Week 12: Projects; Exam

  • Review readings from above
  • Do Week 12 Homework Free Form due Tuesday November 12 before class
  • Class Meetings
    • Tuesday, November 5: Quiz HW11; Open discussion on projects
    • Thursday, November 7: Exam 2 (October 1 – October 31).
  • Project proposal revision, as necessary, based on feedback (submit to Brightspace) Saturday, November 9 11:59 pm

Week 13: Projects

  • Review
  • Do Work on projects
  • Class Meetings
    • Tuesday, November 12: Quiz HW12; Turing complete platforms (Kyle Moore)
    • Thursday, November 14: work on projects

Week 14: Projects

  • Review readings from above
  • Do Work on projects
  • Class Meetings
    • Tuesday, November 19: LLMs and Turing Completeness (Jesse Roberts)
    • Thursday, November 21: work on projects

Thanksgiving Break: November 23 – December 1

Week 15: Projects, Review

  • Review readings from above
  • Do Project Presentations, Review
  • Class Meetings
    • Tuesday, December 3: Bullet Presentations on Projects
    • Thursday, December 5: Bullet Presentations on Projects (last day of classes)
  • Submit Project Report to Brightspace by Thursday December 5 at 11:59 pm

Final Exam: Tuesday, December 10 9:00 am – 12:00 pm (Comprehensive) (https://registrar.vanderbilt.edu/documents/Fall_2024_exam_schedule.pdf).