MA/CSSE 474 – Theory of Computation

Summer, 2020 (202040) Schedule Overview updated Sun Aug 16 at 2:52:45 PM

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

View Late day balances

Claude's Office Hours (changes 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 4
  • UNDER CONSTRUCTION
    This schedule will be updated as the course goes along.
    (6/1/2020) I believe that everything for days 1-5 is up-to-date, days 6-41 will be updated as we go along.
    The due dates for Assignments 1-7 are correct, but only the contents of assignments 1 and 2 have been updated.
    Exam 1 is day 14 (June 26 in summer 2020). Sometimes I may postpone a due date to give you more time, but I will never make assignment from days 1-17 due earlier than it says here.
  • Read the emails that I sent before the term began.
     
  • 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, then start HW1
     
  • 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 2020: Now the textbook is available in PDF form online and free. 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/summer2020/macsse474/.
    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.
     
  • 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 5
  • 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: 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 2020. So for now yu9'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 8
  • 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    Survey    Solution
    Solution will be available after the late day. For HW1 in Summer 2020, that will be June 10.
     
  • 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.
     
  • Solutions for each assignment will be available on Moodle after the due date for that assignment.
    For HW1 in Spring, 2020, that will be March 13.
     
  • 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 9
  • 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)
2

5

Thu Jun 11
  • 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 12
  • Section 5.4 (10 pages) Non-deterministic FSMs
  
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

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

8

Tue Jun 16
  • Sections 5.7-5.8 (10 pages) Minimization and Canonical Form
  
  • More on minimization
  • DFSM Canonical form
3

9

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

10

Fri Jun 19
  • 6.2 (11 pages) Kleene's Theorem
  
  • NDFSM-->DFSM Proof (skip this for Spring 2020)
3

11

Mon Jun 22
  • 6.3-6.4 (5 pages) Practical aspects of regular expressions
  • HW 5
     
  • Summer, 2020: Because of the exam on Friday, HW6 will not be due until next week, so I am giving you extra time for HW5. It will be due Wednesday at 5:00 PM, with late day until Thursday at 5:00 PM. I will make the solution available Thursday at 5:00.
     
  • HW 5 Topics: Canonical form, intersection DFSM construction and proof, equivalence classes for "prime numbers" language, simple regular expressions examples.
     
  • HW 5 problem statements
     
  • 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 23
  • 8.1-8.3 (6 pages) Regular languages and closure properties
  
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Thu Jun 25
  • 8.4-8.6 (9 pages) Pumping theorem, functions on Regular languages
  • Summer, 2020: Real due date for HW5 is today at 5:00 PM.
    The early time of day is so that students can still uas a late day and I can publish solutions several hours before the exam.
  • 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 26
  • Get enough sleep so that you can think well during the exam.
  • Notations and Definitions page that I gave 201830 students with Exam 1. Is there anything else you would like to see there? If so, let me know by noon of the Saturday before the exam.
     
  • Summer 2020: Exam will happen on this day (June 26)
    1. See Piazza post from 6/22 for details
    2. I will be somewhat flexible about what time you take it.
      Any 90 minutes that are entirely within 10:00 AM - 11:55 PM.
      Let me know soon if this is a problem for you.
    3. If you have accomodations that allow you extra time for exams, please get the letter from Patty Eaton to me by Wednesday, June 24.
  • Exam 1 will happen today.
4

15

Mon Jun 29
  • 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 30
  • 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.
  • In-class exercises
     
5

17

Thu Jul 2
  • 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 3
  • 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 6
  • 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 7
  • Section 11.8 Simplifying grammars, normal forms (8 pages)
  • Useless nonterminals
  • Simplifying Grammars
  • Chomsky Normal Form
  • Greibach Normal Form (briefly mentioned in Section 11.8)
6

21

Thu Jul 9
  • 12.1 - 12.2.2 PDA intro (7 pages)
  • Summer 2020: Because of the upcoming break, I will also delay HW10 due date by a day (due Friday)
  • Push-down Automata
6

22

Fri Jul 10
  • 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 19. 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.
     
  • One caveat on HW 10. If the COVID resurgence doesn't keep it from happening, my wife and I will be taking a shorter version of the trip I mentioned before the term started. We will leave July 10 and return July 21. I will not have Zoom office hours during that time. I will answer email and Piazza questions, but perhaps not as soon as I normally would. Your best bet is to get your HW10 questions answered during my office hours July 9.
     
  • 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 20
  • 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 21

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

25

Thu Jul 23
  • 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 24

      
7

27

Mon Jul 27
  • 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 28
  • Sections 17.5-17.7 Alternative TM defs,
    Encoding a TM, the universal TM
  • HW 12 This is a long assignment; start early!
    Because of Friday's exam, there is only one assignment due this week, so I delayed HW12 due date until Wednesday.
     
  • You should plan to NOT use a late day for this assignment, so you can spend Thursday evening reviewing for the exam and sleeping.
  • HW 12 problem statements
     
  • HW 12 Topics: design some PDAs, deterministic PDAs, equivalence of two accepting approaches, showing that a language is/is not context-free.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 12.
     
  • Turing Machine Intro, notation
  • Turing Machine Examples
8

29

Thu Jul 30
  • 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 31
  • Chapter 19 Halting - an undecidable problem
  • Summer 2020, 2021: Exam 2 will be on this date.
  • 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 6-12, textbook section 6.2, chapters 7-10, 11.1-11.8, chapter 12, 13.1-13.3, videos through day 26.
  
8

31

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

32

Tue Aug 4

    
  • Church-Turing Thesis
  • Dovetailing
9

33

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

34

Fri Aug 7
  • Sections 21.4-21.7 More on (un)decidability questions
  
  • Halting Problem
9

35

Mon Aug 10

  
  • 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.
  • Decidable, SD, and non-SD languages
  • Enumerability and Decidability
9

36

Tue Aug 11

    
  • Intro to Reduction
10

37

Thu Aug 13

    
  • Use reduction to show another language is undecidable
10

38

Fri Aug 14

  
  • 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 17

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

40

Tue Aug 18

    
11

41

Thu Aug 20

  
  • HW 17 This is a very challenging assignment, so I am giving you much more time for it than for typical assignments.
  • On Moodle: Drop Box    Survey    Solution
     
    
11

42

Fri Aug 21
  • Re-read sections from the book that you did not understand the first time.
  • Do lots of problems, including some "not-to-turn-in" problems from the HW.
  • Summer, 2020 final exam: Saturday August 22, 10:00AM-1:00PM Indiana time.
  • If you have extra-time accomodations, strart at 10 and end at 2:30 (50% extra time).
  • Like the other exams, it will have T/F/IDK, multiple choice, short answer, and possibly other auto-graded problems. There will be a few essay questions and an optional Moodle drop box for submitting them.
  • Some of the problems will describe a language and ask you to classify it as finite, regular, context-free, decidable, or not decidable.
  • A good resource for studying, and for reference during the exam: "definition and formula" sheet,
    It includes the "Turing machine macros reference".
    Note that it includes some Chapter 21 material, which will not be in this exam.
  • Final Exam will cover material from the whole course.
  • But there will be more emphasis on things that were not covered by the previous exams:
    Chapters 12, 13, 14, 17.3-17.7, 18, 19, 20, 21, (27, 28 were not covered this term)
    HW 12-17.