Theory of Automata, Formal Languages, and Computation Fall 2023

Theory of Automata, Formal Languages, and Computation

CS 3252 and CS 5252
Fall 2023

Time and Place: MWF 2:30 PM to 3:20 PM, FGH 211

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

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

TA: Naima Samreen Ali (…) naima.samreen.ali@vanderbilt.edu

TA Office Hours: Wednesdays 11:30 am-1:00 pm and Fridays 4:00 pm to 5:30 pm

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 (join code: 956858) 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 four 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 Friday, December 15 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 (Naima) 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. Naima 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 programming project. In general, students can and should be learning from other students in this course. There may also be prompts from me and Naima 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 1-2 week project will follow Thanksgiving break (though you can start working earlier). 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 questions (e.g., formally characterizing the class of inherently ambiguous languages). 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.

Naima 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: 10%
  • Exam 2: 10%
  • Exam 3: 10%
  • Exam 4: 10%
  • Final Exam: 15%
  • Project: 10%
  • 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

  • [92, 100] A (a very few A+s may be given)
  • [90, 92) A-
  • [87, 90) B+
  • [82, 87) B
  • [80, 82) B-
  • [77, 80) C+
  • [72, 77) C
  • [70, 72) C-
  • [67, 70) D+
  • [62, 67) D
  • [60, 62) D-
  • [0, 60) F

Don’t assume that I will round up.

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 we would be interested to hear about it, perhaps on the free form submission;
  • you may NOT consult with AIs or other people on the quiz portion of any homework. 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 (under development)

Week 1 Overview and Basics

Week 2: Grammars and languages

  • Read
  • Do Week 2 Homework Free Form due Wednesday September 6 before class (See Top Hat)
  • Class meetings
    • Monday, August 28: Finish proofs
    • Wednesday, August 30:  Quiz HW1; Unrestricted grammars and languages; Context-Sensitive Grammars (CSGs) and Languages (CSLs); Context-free grammars (CFGs) and languages (CFLs), derivations
    • Friday, September 1: Context-free grammars and languages

Week 3: Grammars and languages

  • Read
  • Do Week 3 Homework Free Form due Wednesday September 13 before class (See Top Hat)
  • Class meetings
    • Monday, September 4: Context-free grammars and languages, including, parse trees, ambiguity,  normal forms, inherent ambiguity
    • Wednesday, September 6: Quiz HW2; rhe Pumping Lemma for CFLs; applications of CFGs and CFLs
    • Friday, September 8: Regular Grammars (RGs) and Languages (RLs), the Pumping Lemma for RLs, lexical analysis; Chomsky hierarchy

Week 4: Finite Automata and Regular Languages; Exam

  • Read
  • Do Week 4 Homework Free Form due Wednesday September 20 before class (See Top Hat)
  • Class meetings
    • Monday, September 11: Deterministic (DFA) and nondeterministic (NFA) finite automata
    • Wednesday, September 13: Quiz HW3; Equivalences of regular grammars, DFAs, and NFAs
    • Friday, September 15: Exam 1 (August 23 – September 8). See Key on Top Hat.

Week 5: Finite Automata and Regular Languages

  • Read
  • Do Week 5 Homework Free Form due Wednesday September 27 before class
  • Class Meetings
    • Monday, September 18: NFAs with epsilon moves; equivalence of NFAs with epsilon transitions and DFAs
    • Wednesday, September 20: Quiz HW4; Regular Expressions (REs) and Regular Languages
    • Friday, September 22: equivalences between FAs and REs; Pumping Lemma for RLs revisited

Week 6: Pushdown Automata and Context Free Languages

  • Read
  • Do Week 6 Homework Free Form due Wednesday October 4 before class
  • Class Meetings
    • Monday, September 25: DFA minimization; equivalence algorithm for RLs
    • Wednesday, September 27:  Quiz HW5; Pushdown Automata (PDAs) and CFLs
    • Friday, September 29: Deterministic (DPDA) and Deterministic CFLs (DCFLs)

Week 7: PDAs to Turing machines, recursively enumerable and recursive languages; Exam

  • Read
  • Do Week 7 Homework Free Form due Wednesday October 11 before class
  • Class Meetings
    • Monday, October 2: Turing machines (TMs)
    • Wednesday, October 4:  Quiz HW6;
    • Friday, October 6: Exam 2 (September 11 – September 29)

Week 8: Turing Machines and languages

  • Read
  • Do Week 8 Homework Free Form due Wednesday October 18 before class
  • Class Meetings
    • Monday, October 9: Turing machine variants; Turing machine programming; linear-bounded TMs and CSLs
    • Wednesday, October 11:  Quiz HW7; TM encoding, Universal TM, a non-recursive language
    • Friday, October 13: the diagonal language (not RE), Chomsky Hierarchy

Week 9: Some odd languages

  • Read
  • Do Week 9 Homework Free Form due Wednesday October 25 before class
  • Class Meetings
    • Monday, October 16: “Random” languages (musings); talking with AIs
    • Wednesday, October 18: Quiz HW8; Open Discussion
    • Friday, October 20: Fall break

Week 10: Theory of Computation: Properties of Recursive languages

  • Read
  • Do Week 10 Homework Free Form due Wednesday November 1 before class
  • Class Meetings
    • Monday, October 23: Closure Properties of RLs and CFLs
    • Wednesday, October 25:  Quiz HW9; Closure Properties of Recursive languages
    • Friday, October 27: Algorithm efficiency (Recursive languages); Reductions

Week 11: Theory of Computation: NP completeness

  • Read
  • Do Week 11 Homework Free Form due Wednesday November 8 before class
  • Class Meetings
    • Monday, October 30: Intractability, P and NP; Polynomial Reductions
    • Wednesday, November 1:  Quiz HW10; NP hard and complete problems; SAT
    • Friday, November 3: Exam 3 (October 2 – October 30)

Week 12:  Theory of Computation: Properties of Recursively Enumerable languages

Week 13: Theory of Computation; Undecidability; Exam

  • Read
  • Do Ideate/plan Post-break project
  • Class Meetings
    • Monday, November 13: (un)decidability
    • Wednesday, November 15:  Quiz HW12; Open discussion on post-break projects
      • Project proposal due (submit to Brightspace)
    • Friday, November 17: Exam 4 (October 30 – November 13)

Thanksgiving Break: November 18 – November 26

Week 14: AI and Formal Language Theory

Week 15: Projects, Review

  • Read Review
  • Do Projects, Review
  • Class Meetings
    • Monday, December 4: Bullet Presentations on Projects
    • Wednesday, December 6: Bullet Presentations on Projects

Final Exam: Friday, December 15 9:00 am – 12:00 pm (Comprehensive) (https://registrar.vanderbilt.edu/documents/Fall_2023_exam_schedule.pdf).