MA/CSSE 474 – Theory of Computation

Summer, 2021 (202140) Schedule Overview updated Tue Aug 10 at 12:59:58 PM

This page will be updated as we proceed through the summer.

View Late day balances

Instructor and TA Office Hours (may change each week)


Session quick links:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

Week Session Preparation HW Due Topics Resources
1

1

Thu Jun 3
  • UNDER CONSTRUCTION
    This schedule will be updated as the course goes along.
    (5/31/2021) I believe that everything in the schedule page for days 1-15 is up-to-date.
    Assignments 0, 1, and 2 have been updated.
    Due dates for Assignments 3-6 are correct, but the assignments themselves have not been updated.
    The only exam is Saturday, July 31, 2021.
    Sometimes I may postpone a due date to give you more time, but I will never make an assignment from days 1-15 due earlier than it says here.
     
  • Not everything in this column for day 1 really has to be done by June 4, but I do recommend that you do them no later than Saturday noon.
     
  • Bookmark this page in your browser so you can find it quickly
     
  • Read the Syllabus
     
  • Unless I specify otherwise, all readings are from Automata, Computability, and Complexity by Elaine Rich.
    It appears that the less-expensive international edition has the same contents as the American edition.
     
  • Summer 2021: Now the textbook is available in PDF form online and it is free for you to use it. You may want to download it so you can read it off-line.
     
  • Read Appendix A: Sections A.1-A.6 37 pages.
    See the quiz info in the HW Due column
     
  • Based on your reading, identify topics that you need to review in detail before the course begins (or early in the course)
     
  • See the quiz info in the HW Due column
     
  • Sign up for this course on Piazza:
    http://piazza.com/rose-hulman/summer2021/macsse4742021/.
    I suggest editing your email preferences to "real time" and "Follow all".
     
  • Instructor intro and course intro videos on Moodle. Note: The second one was one of the first instructional videos that I ever made, so the technical quality is pretty bad, but I hope the content will be helpful.
     
  • (today and every day) Do the items in the preparation column on this schedule.
     
  • Homework will usually be due on Mondays and Thursdays at 11:55 PM Terre Haute time.
     
  • Reading quiz 1 (MSWord, pdf). You are not required to do this for credit in the summer, but I strongly suggest that you do it and check your answers on Moodle. It is okay if you do this a little bit later than Day 1.
     
  • Non-required HW 0 (but recommended for many students). In some previous years, I required students to do these problems, but a few years ago, I decided that students whose prerequisite background is strong may not need to take the time to write up their solutions. You should at least take a look at the problems. This is a REAL assignment, but it is one that you do not have to turn in. If there are any (and it is very likely that there will be some) problems that appear to not be very easy for you, you should actually do them by the end of the first week, get help if needed, and compare your answers to the posted solutions. A few of these problems may actually appear in required homework at some point.
     
  • HW0 problem details
  • HW0 solution
     
  • Turnins: when and where?
    Homework problems:
    Due at 11:55 PM on due date.
    Electronic submissions only.
    Drop box on Moodle.
    Submit each assignment as a single document.
    Do not write on both sides of a paper that you plan to scan or photograph. Bleed-through happens!
    Before you submit, check document for readability, pages in order, nothing cut off.
    For most assignments there is also an extra-credit survey, worth up to 5 HW points.
  • Get the flavor of the course:
    • A mathematical look at Deterministic Finite State Machines (DFSM)
    • The language accepted by a DFSM
    • Example machine/language
    • Prove it by induction
1

2

Fri Jun 4
  • Read my solutions to the reading quiz 1 questions (available on Moodle Monday afternoon).
     
  • Chapter 1 (5 pages) Why study ToC? Read it quickly;
    there are no details that you need to retain (yet!).
     
  • Chapter 2 (10 pages) Languages and Strings.
    Read carefully, answer the quiz questions, write down any questions that you may have. This material, much of which should be review from the DISCO courses, is fundamental to everything that we will do in this course. For many more examples of formal languages, See Grimaldi, section 6.1. (pages 309-318). Note that Grimaldi(in the MA275-375 book) uses λ to represent the empty string, while Rich uses ε.
     
  • Sections 3.1-3.2 (5 pages) Language recognition, encoding. This is also very important material.
  • Reading quiz 2 (MSWord, pdf)
    You are not required to turn this in. Suggestion: do it by Saturday and check your answers against the solution on Moodle. It is okay if you do this a little bit later.
     
  • Skim the HW 1 documents (details in this column, Day 3) and plan when you'll work on this. It is unlikely that you can do it all in a single 3-hour session. You may need more time.
     
  • If you have not looked at the non-turnin HW0 yet, today may be good day to do so. Details are in Day 1 HW column.
     
  • Professor and Course introduction, online materials
  • What is ToC?
  • Problems from Reading Quiz 1
  • Languages and Strings
  • String concatenation, replication, reverse
  • Detailed induction proof of (wx)R = xRwR
  • PPT / Slides
  • Class Notes
     
  • Online intros to induction
     
  • Video: Reading Quiz 1 responses (9:26)
     
  • Video: How Not to Do Induction (8:05)
     
  • Video: Reverse-concatenation-Theorem (2:46)
     
  • About the slides and class notes: These slides and notes are from a previous time when the course was taught face-to-face. They are based on what was covered each day. For some of the videos that I recorded, there is a modified set of slides that goes with just that video topic. I hope to do the same with class notes, but that is unlikely to happen in summer 2021. So for now you'll have to live with the fact that the slides are in two places, and often the ones linked from the schedule page contain info that is not in the "customized for a video" slides.
1

3

Mon Jun 7
  • Section 3.3 (5 pages) Language Hierarchy.
    This gives a preview of the entire course, without the mathematical details. Read it, but don't spend a lot of time on it.
     
  • The importance of Chapter 4: This chapter introduces many ideas that we will explore in detail throughout the course. Key terms and ideas: decision procedure, nondeterministic, a function on a language, whether a set of languages is closed under a function. You should be ready to do some of the HW2 problems after reading this chapter.
     
  • Section 4.1 (4 pages) Decision Procedures.
    Another fundamental building block of the course.
  • Section 4.2 (6 pages) Determinism and Nondeterminism. The first "tricky" prevalent concept of this course.
     
  • Read my solutions to the reading quizzes 1 and 2 (posted on Moodle).
  • HW 1 over Chapters 1-2 and mathematical induction. Due at 11:55 PM
     
  • hw01-problems
     
  • Be sure to read this sample induction proof writeup before you do the induction problems in this assignment.
     
  • For extra credit, complete the survey associated with each HW assignment. It is best if you complete it within 24 hours after doing the problems, while they are fresh on your mind. If you want the extra credit, it must be completed by the end of the day after that assignment's late day date.
     
  • HW 1 on Moodle:
      Drop Box
      Extra Credit Survey   (2021: due by the end of June 9 if you do this optional survey)
      Solution Solutions for each assignment will be available after the late day deadline. For HW 1 in Summer 2021, the solution will be available June 9, since the late day deadline is June 8.
     
  • The numbers from a previous term's HW 1 survey. See how much time past students spent on the assignment, and which problems they thought were hardest.
     
  • defining Languages
  • Sets and Relations
  • Cardinalities of languages and sets of languages
  • Closure of a set under a relation
  • Functions on languages
  • (if time) decision problems
1

4

Tue Jun 8
  • Section 4.3 (3 pages) Functions on languages.
    I.e. a function whose domain is a set of languages (usually the set of all languages over a given alphabet) and whose range is also a set of languages. So the function takes a language as its input parameter and returns a language.
     
  • The first part of Chapter 5: These sections formalize and provide mathematical notations for the notion of computation by a deterministic finite state machine that we saw informally in Session 1.
     
  • Chapter 5 intro, Section 5.1 (5 pages) Formal definition of DFSM.
  • You should read all of the HW2 problems today to make sure that you understand what they are requiring you to do (ask if you don't!). You should do a few of the problems today.
     
  • Today is the last day to use a late day and submit HW1 for credit. In general this will happen on the calendar day after an assignment's due date.
     
  • Wednesday is the last day to submit the optional extra-credit HW1 survey.
  • Equivalence Relations
  • Operations on languages (concatenation, *, +, R)
  • Enumerators and recognizers
  • semidecision procedures vs.
  • Every language is countable; the set of all languages over Σ is not
  • Functions on Languages
  • Decision Problems intro
  • (There are many additional slides on Logic and Proof that will not be used in class)
  • PPT / Slides
  • Class Notes
     
  • Note: At the end of today's slides there are 23 slides on logic. Since this is review material, we will not view these in class. If you need logic review, these may help. I enhanced several of the slides by adding shaded boxes that contain some things that I would say in class or write on the board if we did do them in class.
     
  • Video: Canonical Languages (1:19)
    Some specific languages that we will use frequently in this course.
     
  • Video: Functions over Languages (5:22)
    Functions whose domain and range are subsets of the set of all languages.
     
  • Video: Decision Procedures (10:12)
    A procedure that answers a yes/no question about each language in a (usually infinite) set of languages.
     
  • Video: Video: Counting languages (6:07)
    How many languages over a given alphabet? How many regular languages?
     
2

5

Thu Jun 10
  • Sections 5.2-5.3 (5 pages) More on Deterministic FSMs
  • HW 2 (due at 11:55 PM, as are all HW assignemts, unless I specify otherwise)
     
  • HW 2 Topics: language recognition, intuition about PDAs, semidecision problem, functions on languages, design simple DFSMs, language counting problems.
     
  • hw02-problems As with the HW1 problems document, this contains the problem descriprions from the textbook, so that it is not necessary for you to have the (huge) book with you when you do the problems. The HW2 assignment document may include additional instructor comments, clarifications, and previous terms' Q&A from Piazza that are not found here.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 2 survey. See how much time thosestudents spent on the assignment, and which problems were hardest. Note that HW2 included problem 15, which is now problem 10 of HW3.
  • Equivalence of computation and language recognition decision problem (continued)
  • Formal definition of computation and acceptance DFSM
  • DFSM examples
  • (if time) Non-determinism introduction
2

6

Fri Jun 11
  • Section 5.4 (10 pages) Non-deterministic FSMs
  • Today is the last day to use a late day and submit HW2 for credit. In general this will happen on the calendar day after an assignment's due date.
     
  • Saturday is the last day to submit the optional extra-credit HW2 survey.
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

Mon Jun 14
  • Sections 5.5-5.6(4 pages) Practical FSMs
  • DFSM Minimization
  • Equivalence classes of a language
  • Myhill-Nerode Theorem
2

8

Tue Jun 15
  • Sections 5.7-5.8 (10 pages) Minimization and Canonical Form
  • Today is the last day to use a late day and submit HW3 for credit.
     
  • Wednesday is the last day to submit the optional extra-credit HW3 survey.
  • More on minimization
  • DFSM Canonical form
3

9

Thu Jun 17
  • Section 6.1 (5 pages) Intro to regular expressions
  • You may want to read Appendix C after class.
    
3

10

Fri Jun 18
  • 6.2 (11 pages) Kleene's Theorem
  • Today is the last day to use a late day and submit HW4 for credit.
     
  • Saturday is the last day to submit the optional extra-credit HW4 survey.
  
3

11

Mon Jun 21
  • 6.3-6.4 (5 pages) Practical aspects of regular expressions
  • HW 5
     
  • Summer, 2021: The beginning of this course has been very busy.
    To make this week be a little bit more relaxed, I am postponing the HW 5 due date until Thursday.
    Also, problems 2 and 3 are more challenging than most revious problems.
     
  • HW 5 Topics: Canonical form, intersection DFSM construction and proof, equivalence classes for "prime numbers" language, simple regular expressions examples.
     
  • HW 5 problem statements
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 5.
  • Regular Expressions and languages they define
  • Kleene's Theorem
  • Proof: Regular expression → NDFSM
  • (if time) Begin DFSM → regular expression proof and algorithm
3

12

Tue Jun 22
  • 8.1-8.3 (6 pages) Regular languages and closure properties
  • If you have not looked at problems 2 and 3 from HW5, you should do so today, so will you have a chance to ask questions.
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Thu Jun 24
  • 8.4-8.6 (9 pages) Pumping theorem, functions on Regular languages
  • Summer, 2021:
    Postponed due date for HW5. It's now due today.
  • DFSM → Regular Expression (example)
  • Practical regular expressions (from Appendix O)
  • How many regular languages?
  • Ways of showing a language to be regular.
  • Closure properties of regular languages.
4

14

Fri Jun 25

  
  • Today is the last day to use a late day and submit HW5 for credit.
     
  • Saturday is the last day to submit the optional extra-credit HW5 survey.
  
4

15

Mon Jun 28
  • 9.1-9.2 (7 pages) Algorithms and Decisions
  • Showing a language to be non-regular
  • Pumping Theorem
  • Pumping Theorem examples
4

16

Tue Jun 29
  • Chapter 10 Summary of Regular Languages (1.5 pages)
  • As of Summer, 2020, HW 7 no longer exists.
    I have eliminated some problems and moved some problems to different assignments.
  • More "regular or not?" examples
  • Regular languages closed under various functions?
  • Decision Procedures related to regular languages.
5

17

Thu Jul 1
  • Chapter 7 Regular grammars (5 pages)
  • 11.1-11.2 Intro to Context-free languages (7 pages)
  • Grammar intro
  • Regular Grammars
  • Context-free Grammars
  • Derivations
5

18

Fri Jul 2
  • 11.3-11.4 Working with CFGs (4 pages)
  
  • Working with CFGs
  • Derivation Trees
  • Structure
  • CFG's to generate some specific languages
5

19

Mon Jul 5
  • 11.5 - 11.7.3 Correct grammars, derivations, ambiguity (8 pages)
  • Summer 2020 and 2021: Because this day is officially a holiday, HW 9 is due on Tuesday.
  • Ambiguity; removing ambiguity (read about it on your own)
  
5

20

Tue Jul 6
  • Section 11.8 Simplifying grammars, normal forms (8 pages)
  • HW 9. (late day opportunity extended until Sunday, July 11)
     
  • HW 09 problem statements
     
  • HW 9 Topics: More functions on languages, closure under such functions, true-false questions about the sets of regular and non-regular languages, decision procedures about regular languages
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 9.
     
  • Useless nonterminals
  • Simplifying Grammars
  • Chomsky Normal Form
  • Greibach Normal Form (briefly mentioned in Section 11.8)
6

21

Thu Jul 8
  • 12.1 - 12.2.2 PDA intro (7 pages)
  
  • Push-down Automata
6

22

Fri Jul 9
  • Section 12.2.3 techniques for reducing nondeterminism (2 pages)
  • HW 10 is nominally due today, but because of the break you can have several free late days. Finish it by Sunday, July 18. If you have time during the break, I suggest that you begin working on HW 11 also. HW11 is a fairly long and challenging assignment.
     
  • HW 10.
     
  • HW 10 problem statements
     
  • HW 10 Topics: CFG simplification, grammars for specific languages, a grammar for arithmetic expressions.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 10.
     
  • Push-down automata examples
  • Explore the role of nondeterminism
6

23

Mon Jul 19
  • Sections 12.3, 12.3.1 (not 12.3.2), 12.4 Equivalence of PDAs and CFGs, Halting (6 pages)
  • Like most of the assignments in this course, you will do well to start HW11 early. If you have time during the break to do two or three problems, that will be a good thing.
  
6

24

Tue Jul 20

  
  • Nondeterminism.
  • From a CFG, can produce equivalent PDA
  • Top-down parser
7

25

Thu Jul 22
  • Chapter 14 CFL Algorithms and Decision Problems
  • 16 (skim these three pages) (Chapter 15 material is covered in the compilers course, CSSE 404)
  • HW 11   Like most of the assignments in this course, you will do well to start this one early.
    If you have time during the break to do two or three problems, that will be a good thing.
     
  • HW 11 problem statements
     
  • HW 11 Topics: Proof of grammar correctness, ambiguous grammars, derivation length, parse trees, CNF, simple PDAs.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 11.
     
  • Bottom-up parser
  • Pumping Theorem intro
7

26

Fri Jul 23

      
7

27

Mon Jul 26
  • Section 17.1
  • Sections 17.2-17.4 Turing machine "programming"
  • Pumping Theorem examples
  • CFL closure
  • Misc CFL properties
  • CFL Closure Properties
  • CFL Decision Problems
7

28

Tue Jul 27
  • Sections 17.5-17.7 Alternative TM defs,
    Encoding a TM, the universal TM
  
  • Turing Machine Intro, notation
  • Turing Machine Examples
8

29

Thu Jul 29
  • Chapter 18 Church-Turing Thesis (what is "computable"?)
  • Formal definitions of TM computations
  • Acceptance by a TM
  • Turing Machine subroutines (Macro langiuage)
  • The sets D and SD
8

30

Fri Jul 30
  • Chapter 19 Halting - an undecidable problem
  • Summer 2021: Exam will be on Saturday.
  • Exam 2 and solutions from some previous terms
  • This exam happens in different weeks in different terms, so the materail from old exams might not exactly match this term's.
  • This exam will cover everything that was covered by exam 1 plus HW 0-13, textbook sections A.1-A.6, 2.1-2.2, 3.1-3.2, 4.1-4.3, 5.1-5.7 6.2, chapters 7-10, 11.1-11.8, chapter 12, 13.1-13.5, 13.8 videos through day 27.
  
8

31

Mon Aug 2
  • Chapter 20 Decidable and Semidecidable languages
  
  • Language recognition vs. function computation
  • Universal TM
8

32

Tue Aug 3

  
  • Church-Turing Thesis
  • Dovetailing
9

33

Thu Aug 5
  • Sections 21.5-21.7 More on (un)decidability questions
  
  • Halting Problem Background
9

34

Fri Aug 6
  • Sections 21.4-21.7 More on (un)decidability questions
  • HW 15
  • HW 15 problem statements
     
  • HW 15 Topics: Multi-tape TMs, SD a proper subset of D, TMs for graphs of functions, Universal TM construction, Church-Turing Thesis, TM encodings.
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 15.
    Note that what are now problems 1-6 were problems 2-7 when this survey was administered.
  • Halting Problem
9

35

Mon Aug 9

    
  • Decidable, SD, and non-SD languages
  • Enumerability and Decidability
9

36

Tue Aug 10

  
  • Intro to Reduction
10

37

Thu Aug 12

    
  • Use reduction to show another language is undecidable
10

38

Fri Aug 13

    
  • Reduction and more Undecidability proofs
  • Reduction practice
  • Slides
  • Class Notes
  • I had hoped to make a video for Sections 21.3 and 21.6, but I am out of time and energy. You will need to read those 9 pages in oder to prepare for some of the problems in HW17.
10

39

Mon Aug 16

  
  • Reductions with a twist
  • Rice's Theorem
  • Show that some languages are not SD
10

40

Tue Aug 17

  
11

41

Thu Aug 19

        
11

42

Fri Aug 20
  • Re-read sections from the book that you did not understand the first time.
  • Summer, 2021 no final exam: Instead there was going to be a HW18 due on Friday, but due to Claude's health that won't be happening in Summer 2021.