MA/CSSE 474 – Theory of Computation

Summer, 2019 (201940) Schedule Overview updated Wed Aug 14 at 6:52:29 PM

This page will be updated as we proceed through the term

Virtual Office Hours. Mondays 8:00-8:50 PM, Thursdays 10:00-10:50 AM

View Late day balances  


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
0

0

Thu May 30
  • UNDER CONSTRUCTION" This schedule page will be updated as the course goes along.
    (as of 5/28/2019): Updated for Summer 2019: Syllabus, Days 0 and 1, Homework 0 and 1. I expect to finish all of week 1 before 5:00 PM Friday.
    Many changes to this page will happen before the course begins and soon after it begins.
     
  • Not everything in this column for days 0 and 1 really has to be done by May 30, but I do recommend that you do them no later than Saturday noon, then start HW1
  • Unless I specify otherwise, all readings are from Automata, Computability, and Complexity by Elaine Rich
     
  • Before the course begins:
     
  • Read the Syllabus
     
  • Read and do some activities related to Appendix A: Sections A.1-A.6
     
  • 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
     
  • Bookmark this page in your browser so you can find it quickly
     
  • Sign up for this course on Piazza:
    http://piazza.com/rose-hulman/summer2019/macsse474/
    Set your email preferences so you get email when someone posts a question, announcement, or follow-up.
     
  • 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.
     
  • Homework will usually be due on Tuesdays and Fridays at 11:55 PM Indiana time.
     
  • Before the course begins:
     
  • (today and every day) Do the items in the preparation column on this schedule.
     
  • Look over the HW1 problems and estimate how much time you will need to spend on them.
    I suggest doing some of them before the end of Friday.
     
  • Non-required HW 0 I used to require 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, 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 problems
     
  • HW0 Solution is on Moodle.
     
  • Turnins: when and where?
    Reading quizzes (not in summer):
    Due at beginning of class.
    Hard copy only.
    Print and answer by hand, or
    answer electronically and print.
    Print 2-sided to conserve paper.
    Staple.
    Homework problems:
    Due at 11:55 PM Indiana time on due date.
    Electronic submissions only.
    Drop box on Moodle.
    Scanners in F217 and Library; Rose ID card gets you into F217.
    If you intend to scan or take phone pictures, do not write on both sides of the page. The back page tends to "bleed through" into the image.
    Phone pictures are okay if they are readable, right-side-up, in-order, and reasonably small file size.
    Submit each assignment as a single document (for example insert pictures into a MSWord or PDF document)
    Before you submit, check the document to make sure it readable and that nothing got cut off.

     
  • Summer: Important note on timing
    The summer homework schedule is based around the summer course and holiday calendar. The dates for reading assignments, topics, and slides for given days are based on the last time the course was taught on-campus. You should read the textbook sections and the PowerPoint slides in the order given here, but not necessarily on the days indicated. Sometimes a summer HW due date may be earlier than the "session day" when its material is covered in the slides. So the rule for you is "when working on a homework assignment, read far enough in the textbook and slides to cover the material for the homework questions."
  • Many review topics from Appendix A. A few of these topics are quickly reviewed in the slides from the first few days of class (those slides also contain some new material).
  • List of terminology from Appendix A.
    If you see a term in this list that you can't define/use, you should read that part of Appendix A again.
     
  • Anonymous suggestion box
  • You may want to get JFLAP, software
    that lets you draw and execute various kinds of automata. It also has a "pumping theorem game".
     
  • Video: Instructor introduction (recorded Summer, 2018)
     
  • Video: Course introduction. See my note in the Preparation column.
1

1

Thu May 30
  • Recommendation: Make note of
    textbook errata file, and reference it as you read the textbook.
     
  • Chapter 1 (pp 2-7) Why study ToC? Read it quickly;
    there are no details that you need to retain (yet!).
     
  • Chapter 2 (pp 8-20) Languages and Strings.
    Read carefully, ask questions on Piazza if there is anything that you do not understand.
    This material is fundamental to all that we will do in this course.
    For many more examples of languages, see Grimaldi, section 6.1. (pages 309-318) . Note that Grimaldi uses λ to represent the
    empty string, while Rich uses ε.
  • Introduce yourself on the Moodle discussion forum (by Thursday) and respond to other students' introductions (by Saturday).
     
  • Reading quiz 1 (MSWord, pdf)
    Summer:You are not required to turn this in. Suggestion: do it by Friday and check your answers against the solution on Moodle. It is okay if you do this a little bit later.
     
  • Reading quiz 2 (MSWord, pdf)
    Summer: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 4) 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 considerably more time.
  • 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
  • Slides / PPT
    (PDFs are easier to browse to;
    slides include instructor notes and hidden slides    )
     
  • Slides Changed after class to include details of proof of "S is a subset of T".
     
  • Today's announcements
     
  • Class Notes
     
  • Video Strings, Languages, FSMs (10:23)
     
  • In case you need a basic review of induction:
     
  • Video Proof Example: Set equality and Mathematical induction.
    A proof that the language accepted by a DFSM is exactly the set of all binary strings that do not contain two consecutive 1's. After this you should be ready to tackle HW1.
     
  • Sample Induction Proof Writeup Similar to
    how it could be written if it was a 474 assignment.
1

2

Fri May 31
  • Read the Syllabus/Policies on Moodle. Ask questions on Piazza if something is not clear. Note that you have to click several links to see the entire syllabus.
     
  • Sections 3.1-3.2 (pages 21-27) Language recognition, encoding.
    Very important material for this course.
     
  • Section 3.3 (pages 28-34) 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.
  
  • What is ToC?
  • Problems from Reading Quiz 1
  • Languages and Strings
  • String concatenation, replication, reverse
  • Detailed induction proof of (wx)R = xRwR
1

3

Mon Jun 3
  • Section 4.1 (pages 36- 41) Decision Procedures.
    Another fundamental building block of the course.
     
  • Section 4.2 (pages 41-43) Determinism and Nondeterminism. The first "tricky" prevalent concept of this course.
     
  • Section 4.3 (pp 48-51) Functions on languages.
    I.e. a function whose domain is a
    set of languages (usually the set of all languages)
    and whose range is also a set of languages. So the function takes a language as its input
    parameter and returns a language.
     
  • 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.
  • If you have not already completed several HW 1 problems, you should do so today!
  • 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 4
  • Chapter 5 intro, Section 5.1 (pages 54-60) Formal definition of DFSM.
     
  • Sections 5.2-5.3 (pp 60-66) More on Deterministic FSMs
     
  • 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.
     
  • JFLAP Tutorial
     
  • HW 1 over Chapters 1-2 and mathematical induction.
    Due Tuesday at 11:55 PM
    Has been updated for Summer, 2019
     
  • 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.
    If you want the extra credit, must be completed by the end of the day after the late day period.
     
  • On Moodle:  Drop Box    Survey    Solution
     
  • Solutions for each assignment will be available after the last day students can use a late day for this assignment.
    For HW1 in Summer, 2019, that will be June 6.
     
  • The numbers from a previous term's HW 1 survey. See how long students spent on the assignment and which problems were hardest.
  • Summer: Wednesday is the last day to use a late day and submit HW 1.
     
  • Don't forget the HW1 Extra-credit survey on Moodle.
  • 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
  • Today's announcements
  • 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. 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: A quick demo of using the JFLAP software to draw and run a FSM.
     
2

5

Thu Jun 6
  • Section 5.4 (pp 66-79) Non-deterministic FSMs
     
  • For the very mathematically inclined: Read Appendix C. A formal proof of something I showed informally by example in the above video
  • Help for HW2, problem 4.4:
    Before you attempt 4.4c, you may want to look over these solutions to the non-required parts of Exercise 4.4, to firm up your understanding of what it means for a set of languages to be closed under an operation.
  • Summer: Wednesday is the last day to use a late day and submit HW 1. Alo the last day to submit the extra-credit HW1 survey.
     
  • Equivalence of computation and language recognition decision problem (continued)
  • Formal definition of computation and acceptance DFSM
  • DFSM examples
  • (if time) Non-determinism introduction
  • PPT / Slides
     
  • Today's announcements
     
  • Class Notes
     
  • About the above video: Given a NDFSM , show how to construct an equivalent DFSM. I originally had a link to a YouTube video that was subsequently removed. So I quickly recorded a replacement.
2

6

Fri Jun 7
  • Sections 5.5-5.6(pp 79-82) Practical FSMs
  • HW 2 (due at 11:55 PM, as are all HW assignemts, unless I specify otherwise)
    You may want to view the slides from Sessions 4 and 5 before doing this homework.
    Has been updated for Summer, 2019
     
  • HW 2 Topics: language recognition, intuition about PDAs, semidecision problem, functions on languages, design simple DFSMs, language counting problems.
     
  • hw02-problems
     
  • On Moodle: Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 2 survey. See how long students spent on the assignment and which problems were hardest.
  • Summer: Saturday is the last day to use a late day and submit HW 2.
     
  • Summer: Saturday is the last day to use a late day and submit HW 2.
     
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

Mon Jun 10
  • Sections 5.7-5.8 (pp 82-96) Minimization and Canonical Form
  
  • DFSM Minimization
  • Equivalence classes of a language
  • Myhill-Nerode Theorem
2

8

Tue Jun 11
  • Section 6.1 (pp 127-132) Intro to regular expressions
  • More on minimization
  • DFSM Canonical form
3

9

Thu Jun 13
  • Section 6.2 (pp 133-146) Kleene's Theorem
     
  • Sections 6.3-6.4 (pp 147-150) Practical aspects of regular expressions
  • Summer: Last day to use a late day and submit HW 3.
     
  • HW5 has two problems that are very challenging and may need a day or two of "sink-in time". Plan to start it early,
  • NDFSM-->DFSM Proof
  • (if time) Regular expression intro
3

10

Fri Jun 14
  • 8.1-8.3 (pp 162-169) Regular languages and closure properties
  • HW 4
    Has been updated for Summer, 2019
     
  • HW 4 Topics: NDFSM→DFSM, Equivalence classes of a language, DFSM state minimization.
     
  • HW 4 problem statements
     
  • On Moodle:   Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 4 survey.
     
  • Summer: Sunday, June 16 is the last day to use a late day and submit HW 4. For this assignment only, you can submit up to two days late and only use one late day.
     
  • Suggestion: If you have not looked at problems 2 and 3 from HW 5, you should do it today, so you have a chance to ask questions if you don't understand what is required.
     
  • Summer: This exam was in Winter 2015-16. We will have our midterm exam in week 5, but I left this info in the schedule because the info might be valuable for you.
  • No exam 1 in summer: Exam 1 in class.
    Will cover Sections A.1-A.6, 2.1-2.2, 3.1-3.2, 4.1-4.3, 5.1-5.7, Reading quizzes and HW 1-4
    Notes about specific kinds of problems to expect (Last updated Dec 12, 2013 at 8 AM)
3

11

Mon Jun 17
  • 8.4-8.6 (pp 169-182) Pumping theorem, functions on Regular languages
  • STRONG Suggestion: If you have not looked at problems 2 and 3 from HW 5, you should do it today, so you have a chance to ask questions.
     
  • Summer: Sunday, June 16 is the last day to use a late day and submit HW 4. For this assignment only, you can submit up to two days late and only use one late day.
  • 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 18

  
  • HW 5
    Has been updated for Summer, 2019
     
  • HW 5 Topics: Canonical form, intersection DFSM construction and proof, Equivalence classes for "prime numbers" language.
     
  • There is no separate HW 5 problem statements document, because none of the HW5 problems are from the textbook
     
  • Problems 2 and 3 are especially challenging. Start them as soon as you can.
     
  • On Moodle:   Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 5.
     
  • Not Summer: Exam discussion
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Thu Jun 20
  • 9.1-9.2 (pp 187-195) Algorithms and Decisions
  • Summer: Wednesday is the last day to use a late day and submit HW 5.
  • DFSM → Regular Expression (continued)
4

14

Fri Jun 21
  • Chapter 10 Summary of Regular Languages (1.5 pages)
  • If L is regular, then LR is regular.
  • Practical regular expressions (from Appendix O)
4

15

Mon Jun 24
  • 11.1-11.2 Intro to Context-free languages
  
  • How many regular languages?
  • Ways of showing a language to be regular.
  • Showing a language to be non-regular
  • Pumping Theorem
4

16

Tue Jun 25
  • 11.3-11.4 Working with CFGs
  • HW 7 over the last part of Chapter 6.
    Has been updated for Summer, 2019
     
  • HW 07 problem statements
     
  • HW 7 Topics: reg. exp → FSM, FSM → reg. exp, logic description → reg. exp.
     
  • Problem 3 (the 2nd problem to turn in), is not hard, but it is long and tedious. The approach I want you to use is not in the textbook. In-class discussion of it and an example were begun in Session 12, and continued in Session 13. More details are in the assignment document. You might also find this Commentary on the slides to be helpful.
     
  • On Moodle:   Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 7.
     
  • Pumping Theorem examples
  • Decision Procedures related to regular languages.
5

17

Thu Jun 27

  
  • Summer: Wednesday is the last day to use a late day and submit HW 7.
  • Pumping Theorem and Closure
  • Regular languages closed under various functions?
  • PPT / Slides
  • Today's announcements
  • Class Notes
  • Video: Pumping Theorem (a.k.a. Pumping Lemma).
    I think the textbook does quite a good job with this, but if a verbal explanantion helps you, this one is pretty good. Note that the lecturer uses some differernt names for what Elaine Rich calles w, k, and q. (1:16:41)
5

18

Fri Jun 28

  
  • Decision Problems about Regular languages.
  • Many in-class exercises.
5

19

Mon Jul 1
  • 11.5 - 11.7.2 Correct grammars, derivations, ambiguity
  • Chapter 7 Regular grammars
  • Midterm Exam. You may take it anytime on July 1 (Indiana time)
  • Will include course material through HW8. Nothing on Context-free grammars.
  • Exam overview document Includes exam timing, resources you can use, practice with Remote Proctor, some kinds of questions to expect, how to produce mathematical notation in your answers.
  • Detailed instructions for accessing exams via RPNow.
  • Notations, definitions, etc. You can print this page (2-sided if possible) to use for reference during the exam. No other written or printed resources are allowed.
  • Go to RPNow
  • Some exams from previous terms: Exam 1     Exam 2
  • Rewrite systems and grammars
  • CFG intro
  • Derivations
  • CFG's to generate some specific languages
  • Regular grammars (Chapter 7)
5

20

Tue Jul 2
  • 11.8 Normal forms
  • 12.1 - 12.2.2 PDA intro
  • HW 9 over the end of Chapter 8, and Chapter 9.
    Due Wednesday (due to the exam).
    Because some of you would rather start your holiday early and use the break to catch up on things, I will give several "grace days". You can submit this until Thursday, July 11, and still have it count as on-time.
    Warning: I will be traveling during the break and will have very infrequent internet access. If you want help from me, it is best to finish this by noon on July 3. After that I'll do my best to answer your questions, but it might take a couple of days.
    Has been updated for Summer, 2019
     
  • 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.
     
  • HW 9 is longer than most assignments, and past students have said that there are a few hard problems.
  • Working with CFGs
  • Derivation Trees
  • Structure
6

21

Mon Jul 15

  
  • Summer 2019: Thursday, July 11: Last day to submit HW9 without using a late day.
  • Summer 2019: Friday, July 12. Last day to use a late day and get credit for HW9.
  • Summer: Once again, our exam is in a different week:
  • (not summer) Answers to your questions about the exam material
6

22

Tue Jul 16

  
  • HW 10 (due Wednesday)
    Has been updated for Summer, 2019
     
  • HW 10 problem statements
     
  • HW 10 Topics: CFG simplification, grammars for specific languages, a grammar for arithmetic expressions.
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 10.
     
  • Summer 2019:Due on Wednesday instead of Tuesday so you don't have to work on it during the break.
  • Summer 2019: Once again, our exam is on a different day.
  • Exam 2 in class. (not summer)
    Will cover Sections 5.7-5.8, 6.1-6.4, 8.1-8.6, 9.1-9.2, 10 and HW 5-9 Summer 2019: Midterm exam does not include HW9 or Chapter 9.
6

23

Thu Jul 18
  • Sections 12.3-12.4 Equivalence of PDAs and CFGs; Halting
  • Summer 2019: Last day to use a late day and submit HW 10.
  • More on Parse Trees
  • Ambiguity
6

24

Fri Jul 19
  • WHy isn't HW11 due today? Because I think you'l need more time for it. You should do some of the problems this week.
  • Normal forms (Chomsky and Greibach) and simplification
  • Pushdown Automata intro
  • PDA examples
7

25

Mon 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)
  
  • Nondeterminism in PDAs
  • From a CFG, can produce equivalent PDA
  • Top-down parser
  • Bottom-up parser
7

26

Tue Jul 23
  • Section 17.1
  • Bottom-up parsing
  • Showing that languages are/are not C-F
  • Pumping Theorem derivation
7

27

Thu Jul 25
  • Sections 17.2-17.4 Turing machine "programming"
  • Summer 2019: Wednesday is the day to use a late day and submit HW 11.
  • Pumping Theorem examples
7

28

Fri Jul 26
  • Sections 17.5-17.7 Alternative TM defs,
    Encoding a TM, the universal TM
  • Misc CFL properties
  • CFL Closure Properties
  • CFL Decision Problems
  • Turing Machine Intro
8

29

Mon Jul 29
  • Chapter 18 Church-Turing Thesis (what is "computable"?)
  • Summer 2019: Saturday is the last day to use a late day and submit HW 12.
  • Turing Machine Examples
  • Formal definitions of TM computations
  • Acceptance by a TM
  • Turing Machine subroutines (Macro langiuage)
  • The sets D and SD
8

30

Tue Jul 30
  • Chapter 19 Halting - an undecidable problem
  • Summer 2019: HW13 is not due until Friday; there is a reason for that! It is a long and difficult assignment; start early.
  • Language recognition vs. function computation
  • Multiple Tapes.
8

31

Thu Aug 1
  • Chapter 20 Decidable and Semidecidable languages
  
  • Multiple Tracks
  • Multiple Tapes.
8

32

Fri Aug 2

  
  • Encoding Turing Machines as Strings.
  • Enumerating Turing Machines
  • A TM that takes one TM (description) as input and outputs another TM (description)
  • Universal Turing Machine.
9

33

Mon Aug 5
  • Sections 21.5-21.7 More on (un)decidability questions
  • Summer 2019: Saturday is the last day to submit HW13 for credit.
     
  • Answers to student questions about material for exam.
  • Church-Turing Thesis
9

34

Tue Aug 6
  • Sections 21.4-21.7 More on (un)decidability questions
  
9

35

Thu Aug 8

  
  • Summer 2019: Wednesday is the day to use a late day and submit HW 14.
  • Halting Problem intro
  • Decidable, SD, and non-SD languages
9

36

Fri Aug 9

    
10

37

Mon Aug 12

  
  • Summer 2019: Sunday is the last day to submit HW15 for credit.
     
  • Decideability and enumerability
10

38

Tue Aug 13
  • Chapter 27 Analysis and Complexity
  • Sections 28.1-28.3 P and NP
  • HW16 and HW17 are not to be turned in, but it is REQUIRED that you do them as practice for the final exam.
    Not having an exam week makes it impractical to have you submit them and get them graded.
    I have posted the solutions.
    Ask questions on Piazza if you wish.
     
  • HW 16
    Has been updated for Summer, 2019
     
  • HW 16 problem statements
     
  • HW 16 Topics: Semidecision, Decidability and undecidability, Closure properties, lexicographic enumeration, TM for enumerating a specific language, subset properties,
     
  • Solution
     
  • HW 17
    Has been updated for Summer, 2019
     
  • Solution
  • Overview of reduction.
  • Use reduction to show that another language is undecidable
10

39

Thu Aug 15

  
  • Reduction and more Undecidability proofs
  • Reductions with a twist
10

40

Fri Aug 16

  
  • Rice's Theorem
  • Show that some languages are not SD * Undecidable properties of CFLs
  • A quick overview of Computational Complexity, P, and NP.
  • Recent progress on P vs. NP at MIT(Nov 2017)
  • Practice problems
11

41

Mon Aug 19
  • Re-read sections from the book that you did not get the first time.
  • Do lots of problems
  • Summer, 2018: Final exam (2 hours) available August 17, 8:00PM until 11:55 PM August 18.
  • Final Exam will cover material from the whole course.
  • But there will be much more emphasis on things that were not covered by the midterm exam:
    In Summer, 2018, that is 11.7-11.8, 12.1-12.4, 13.1-13.5, 13.8, 14.1-14.3, 17.1-17.7, 18, 19, 20, 21; HW 11-16, lectures 21-40.