Theory of Automata, Formal Languages, and Computation
CS 3252 and CS 5252
Spring 2023

Time and Place: MWF 12:20 PM to 1:10 PM, FGH 244

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

Instructor Office hours: are by appointment on Zoom ( https://vanderbilt.zoom.us/j/95364540137). Email me for an appointment.

TA: Kyle Moore

TA Office Hours: FGH 226 (turn left out of the classroom, it is the second door from the end of the hall on the right).

Instructor Notes and Slides: Slides and Instructor Notes are available on Top Hat (Join Code: ).

Textbook: Most of what you need to know will be in lectures, slides, and instructor notes. Slides with skeletal content and Instructor Notes will be available online in advance of lectures. Nonetheless, it may be important that you consult other resources for elaboration of concepts. And some of you will want or need to do so. There is much content on the Web from which you can draw, but additionally I recommend that you have one of the textbooks in the classic lineage of Hopcroft and Ullman. However, other reference texts will probably work well too. You should just need one.

• 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, 3^rd Edition by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addison Wesley, 2007.

It is your responsibility to obtain a reference text – I have not ordered one from the bookstore, in part because I prefer the earlier out-of-print versions and some/many of you will find the slides, lectures, instructor notes, and Web resources sufficient.

Motivation: Why study automata theory, formal languages, and the theory of computation (ALC)? It is not an area of active research, and it’s not regarded as an applied area either, though some of the material is bread and butter, nuts and bolts computing – so pervasive that its invisible to many. That is, it’s a foundational course. Happily, I think, we study ALC in its raw form because its engaging and fun for those interested in computation. In its abstractions you will find exercises in pure computational theory and computational thinking. Like a humanities class that you take as a computing student, if you are strongly inclined towards the vocational thrusts of computing, and you still take this course, you should take on faith that some-to-much of what you learn will come in handy later. I say “take on faith” because the links between theory and application probably won’t be as overt in this course as you would see in an algorithms course like CS 3250. There are, however, conceptual links between ALC and algorithms of course, programming languages, and artificial intelligence, which we’ll touch upon.

I took “this class” in 1979 from a PhD student, Dov Harel, and I thought it was beautiful – I thought that the pumping lemma was a metaphor for life, at least life as a student. The field hasn’t changed much, or at all (foundations don’t change much). It is a “theory course”, but its not brain surgery, so pay attention and study (I shoot for 9 hours a week commitment of your time, including in-class time) and you should be fine.

Maybe you’ll have a reaction to ALC something like mine (as well as other reactions perhaps) – it’s adoration of computing as a field that offers greater wisdom, not one that simply manifests as mastery of the latest gadgetry, but stems largely from an appreciation of computing’s earliest core abstractions.

Course Organization: Attendance in class is required. Sometimes we might use Zoom to facilitate small group discussions. Throughout each lecture there will be questions on TopHat, and participation and correctness of your answers will be factored into your grade.

We will use Piazza for discussion and announcements.

We will use Brightspace for homework and exam submissions.

There will be three in-class exams during the semester and a final exam. Our final exam is scheduled for Monday, May 1 at 9:00 am CENTRAL TIME.

Homework: There is regular homework, which is available on Top Hat (Join Code: 794430). 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 exactly those questions, or close approximations, that you uploaded answers for. You must submit the open format pdf BEFORE you take the quiz portion of the homework. You can take the “quiz” component on Brightspace (under Quizzes) as many times as you wish, but the % grade that you receive for the homework will be

((% correct on 1^st quiz try) + (2 * (% correct on last quiz try))) / 3

I will consult the free-form answer under Assignments, which is required too, to check your work. I 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 freeform version as “showing your work” for the quiz version that will actually count as your grade.

The due dates and times for assignments on the schedule below are when both the free-form and final quiz attempts are due – plan accordingly.

Lectures, slides, and instructor notes will typically be enough to answer homework problems, but sometimes you may have to look at material elsewhere, typically a textbook or an online resource.

Grading:

• In-Class (Top-Hat) Questions: 5%
• Exam 1: 10%
• Exam 2: 10%
• Exam 3: 10%
• Final Exam: 15%
• Homework: 50%

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, or with others on the exams (nothing, except your own brain);
• you MAY consult with texts, notes, slides, 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;
• you may NOT consult with others on the quiz portion of any homework. You may NOT consult with texts, notes, slides, etc while you are actually taking a quiz attempt, but you can consult sources (except other people) between attempts.

Schedule

Week 1: Course Overview and Introduction to Automata and Languages

• Week 1 Homework due Wednesday January 18 at 11:59 pm
• Monday, January 9: Overview
• Wednesday, January 11: Basics of proofs and languages
• Friday, January 13: Basics of proofs and languages

Week 2: Grammars

• Week 2 Homework due Wednesday January 25 at 11:59 pm
• Monday, January 16: MLK Day – no class
• Wednesday, January 18: Unrestricted and Context-Sensitive Grammars and Languages (HW1 due)
• Friday, January 20: Context-free grammars and languages

Week 3: Grammars

• Week 3 Homework due Wednesday February 1 at 11:59 pm
• Monday, January 23: Context-free grammars and languages, including ambiguity,  normal forms, and algorithms
• Wednesday, January 25: (HW2 due)
• Friday, January 27: Regular Grammars and Languages and introduction to finite automata

Week 4: Regular Languages and Exam

• Week 4 Homework due Wednesday February 8 at 11:59 pm
• Monday, January 30: Deterministic (DFA) and nondeterministic (NFA) finite automata
• Wednesday, February 1: Equivalence of regular grammars and FAs (HW3 due)
• Friday, February 3: Exam 1 (January 9 – January 27)

Week 5: Regular Languages

• Week 5 Homework due Wednesday February 15 at 11:59 pm
• Monday, February 6: NFAs with epsilon moves
• Wednesday, February 8: Regular Expressions and Regular Languages (HW4 due)
• Friday, February 10: DFA minimization

Week 6: Transition from Regular languages to CFLs

• Week 6 Homework due Wednesday February 22 at 11:59 pm
• Monday, February 13: The Pumping Lemma for and closure properties for regular languages
• Wednesday, February 15:  Pushdown Automata and Context-Free Languages (HW5 due Thursday of this week)
• Friday, February 17: Pushdown Automata and Context-Free Languages

Week 7: Applications and Properties of CFLs

• Week 7 Homework due Wednesday March 1 at 11:59 pm
• Monday, February 20: The Pumping Lemma for and closure properties of CFLs
• Wednesday, February 22:  Context-Free Language Translators and other Applications of CFLs and regular languages (HW6 due)
• Friday, February 24: CFL wrap-up

Week 8: Introduction to Turing Machines and Exam

• Week 8 Homework due Wednesday March 8 at 11:59 pm
• Monday, February 27: Turing machines
• Wednesday, March 1:  Turing machine programming (HW7 due)
• Friday, March 3: Exam 2 (Comprehensive, but focus on January 30 to February 24)

Week 9: AI and Formal Languages

• Week 9 Homework due Wednesday March 22 at 11:59 pm
• Monday, March 6: AI, machine learning, uncertainty, and probabilistic grammars
• Wednesday, March 8: AI relevance to formal languages (planning, grammar and operator induction) (HW8 due)
• Friday, March 10: AI relevance to formal languages (planning, grammar and operator induction); Return Exam 2

Spring Break (Saturday, March 11 – Sunday, 19)

Week 10: Turing Machines and languages

• Week 10 Homework due Wednesday March 29 at 11:59 pm
• Monday, March 20: TM Review, TM encoding, Universal TM, a non-recursive language
• Wednesday, March 22:  the diagonal language (not RE), linear-bounded TMs and CSLs, Chomsky Hierarchy (HW9 due)
• Friday, March 24: “Random” languages (musings), closure properties of languages

Week 11: Theory of Computation

• Week 11 Homework due Wednesday April 5 at 11:59 pm
• Monday, March 27: Halting problem, (Un)decidability
• Wednesday, March 29:  Reductions (HW10 due)
• Friday, March 31: (Un)decidability wrap up

Week 12:  Theory of Computation

• Weeks 12 Homework due Wednesday April 12 at 11:59 pm
• Monday, April 3: (In)tractability, P and NP
• Wednesday, April 5: Polynomial Reductions (HW11 due)
  • watch video on polynomial-time reduction to SAT and Cook’s Theorem
• Friday, April 7: NP-complete problems

Week 13: Theory of Computation

• Week 13 Homework due Wednesday April 19 at 11:59 pm
• Monday, April 10: Intractability wrap up, review for Exam 3
• Wednesday, April 12:  In person  and online Q&A (HW12 due)
• Friday, April 14: Exam 3 (Comprehensive, but Focus on February 27 – April 10)

Week 14: Theory of Computation

• Weeks 14 Homework due Monday April 24 at 11:59 pm
• Monday, April 17: chatGPT day
• Wednesday, April 19:  Kyle Moore on Turing completeness with examples (HW13 due)
  • watch selected videos on Prime testing in lesson 6 on  basics and lesson 7 on randomized approaches.
• Friday, April 21: chatGPT day

Week 15: Summation

• Monday, April 24: Week 14 quiz in class; Return Exam 3; Final Exam guide; course evals

Final Exam: Monday, May 1 9:00 am – 12:00 pm (Comprehensive) (https://registrar.vanderbilt.edu/documents/Spring_2023_exam_schedule.pdf).