MA/CSSE 474 – Theory of Computation

Summer, 2018 (201840) Schedule Overview updated Mon Aug 13 at 8:14:39 AM

This page will be updated as we proceed through the term (many updates will happen May 29-June 4)

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

Fri Jun 1
  • UNDER CONSTRUCTION" This schedule page will be updated as the course goes along.
    (5/31/2018): Updated for Summer 2018: 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.
     
  • Unless I specify otherwise, all readings are from Automata, Computability, and Complexity by Elaine Rich
     
  • Before the course begins:
     
  • Read 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/summer2018/macsse474/
    Set your preferences so you get email when someone posts a question, announcement, or follow-up.
     
  • Instructor intro and course intro videos on Moodle. Note: These are among the first instructional videos that I ever made, so the technical quality is pretty bad, but I hope the content will be helpful.
     
  • 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.
    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 (fir example insert pictures into a MSWord document).
    preferably less than 5 MB.

     
  • 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.
     
  • You may want to get JFLAP, software
    that lets you draw and execute various kinds of automata.
     
  • Video: Instructor introduction
     
  • Video: Course introduction
1

1

Fri Jun 1
  • 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, answer the quiz questions, 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 Saturday) and respond to other students' introductions (by Sunday).
     
  • 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.
     
  • 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.
  • 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
  • Email that I sent to students before the course began.
     
  • 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)
     
  • 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

Mon Jun 4
  • Read the Syllabus/Policies on Moodle. Ask quesions 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

Tue Jun 5
  • 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.
  • HW 1 over Chapters 1-2 and mathematical induction.
    Due Wednesday at 11:55 PM
    Has been updated for Summer, 2018
     
  • hw01-problems
     
  • Be sure to read this sample induction proof writeup before you do the induction problems in htis 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, 2017, that will be June 9.
     
  • The numbers from a previous term's HW 1 survey. See how long students spent on the assignment and which problems 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

Thu Jun 7
  • 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
     
  • Summer: 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

Fri Jun 8
  • 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.
  
  • 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
     
  • Video: NDFSM → DFSM algorithm (8:00)
  • 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

Mon Jun 11
  • 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, 2018
     
  • 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.
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

Tue Jun 12
  • Sections 5.7-5.8 (pp 82-96) Minimization and Canonical Form
  • Summer: Last day to use a late day and submit HW 2.
     
  • DFSM Minimization
  • Equivalence classes of a language
  • Myhill-Nerode Theorem
2

8

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

9

Fri Jun 15
  • 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

Mon Jun 18
  • 8.1-8.3 (pp 162-169) Regular languages and closure properties
  • Summer: This exam was in Winter 2015-16. We will have our midterm exam in week 6, 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

Tue Jun 19
  • 8.4-8.6 (pp 169-182) Pumping theorem, functions on Regular languages
  • 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: Last day to use a late day and submit HW 4.
  • Regular Expressions and languages they define
  • Kleene's Theorem
  • Proof: Regular expression → NDFSM
  • (if time) Begin DFSM → regular expression proof and algorithm
3

12

Thu Jun 21

  
  • HW 5
    Has been updated for Summer, 2018
     
  • 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

Fri Jun 22
  • 9.1-9.2 (pp 187-195) Algorithms and Decisions
  • Summer: Last day to use late days and submit HW 5.
  • DFSM → Regular Expression (continued)
4

14

Mon Jun 25
  • 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

Tue Jun 26
  • 11.1-11.2 Intro to Context-free languages
  • Summer: Last day to use late days and submit HW 6.
  • How many regular languages?
  • Ways of showing a language to be regular.
  • Showing a language to be non-regular
  • Pumping Theorem
4

16

Thu Jun 28
  • 11.3-11.4 Working with CFGs
  • HW 7 over the last part of Chapter 6.
    Has been updated for Summer, 2018
     
  • 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

Fri Jun 29

  
  • Summer: 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

Mon Jul 2

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

19

Tue Jul 3
  • 11.5 - 11.7.2 Correct grammars, derivations, ambiguity
  • Chapter 7 Regular grammars
  • Summer 2018: Last day to submit HW 8 for credit.
     
  • See the note below about HW 9.
    Yuu have almost two weeks before it is due, but don't put it off until the end.
  • Rewrite systems and grammars
  • CFG intro
  • Derivations
  • CFG's to generate some specific languages
  • Regular grammars (Chapter 7)
5

20

Thu Jul 5
  • 11.8 Normal forms
  • 12.1 - 12.2.2 PDA intro
  • Nothing is due today. For several reasons:
    1. I expect that some of you are tired and need a break.
    2. You should get to enjoy the holiday on Wednesday.
    3. There is a break coming up so you have the option of doing it later.
    4. HW9 is longer and harder than some of the assignments.

     
  • HW 9 is longer than most assignments; and students in past terms have said that there are many hard problems. I want to let you know this a while before it is due (due the Monday after the break. Will be included on the midterm exam.
  • Working with CFGs
  • Derivation Trees
  • Structure
6

21

Fri Jul 6
  • As you prepare for the exam, write down questions that you have
  
  • Summer: Once again, our exam is in a different week: Week 6 (after the break).
  • Answers to your questions about the exam material
6

22

Mon Jul 16
  • Review for exam 2 (Summer: Review for midterm exam)
  • Recommendation: If you are not going anywhere for the break, why not go ahead and get HW 9 and part of HW 10 out of the way so you can focus more on exam preparation the following week?
  • Summer 2017: Once again, our exam is on a different day, Thursday.
  • 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
6

23

Tue Jul 17
  • Sections 12.3-12.4 Equivalence of PDAs and CFGs; Halting
  • HW 9 over the end of Chapter 8, and Chapter 9.
    Has been updated for Summer, 2018
     
  • 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.
     
  • More on Parse Trees
  • Ambiguity
6

24

Thu Jul 19
  • Summer 2018: Wednesday is the last day to submit HW 9 for credit.
     
  • Normal forms (Chomsky and Greibach) and simplification
  • Pushdown Automata intro
  • PDA examples
7

25

Fri Jul 20
  • Chapter 14 CFL Algorithms and Decision Problems
  • 16 (skim these three pages) (Chapter 15 material is covered in the compilers course, CSSE 404)
  • Summer 2018: Midterm exam will be available all day Friday (Indiana time). It is a two-hour exam.
  • I will be monitoring email periodically from 7 AM until 5 PM, but you may take it any time on Friday.
  • Midterm exam will cover:
    • Assigned readings from Appendix A and Chapters 1-10 (in the Preparation column for sessions 1-14)
    • HW 1-9
  • Will be on Moodle. We will use Remote Proctor.
  • You will have two hours to complete the exam.
  • Mostly True/False, multiple choice, and short-answer questions.
  • For simplicity in entering your short answers, you can write things like x^3 for exponents, yields for ⊢, delta for δ, Sigma* for Σ* (similar for other Greek letters such as epsilon).
  • Detailed description of the exam environment, allowed resources, etc.
     
  • This Moodle page contains links to all Midterm Exam documents.
  • Solutions to 2018 essay questions
  • Nondeterminism in PDAs
  • From a CFG, can produce equivalent PDA
  • Top-down parser
  • Bottom-up parser
7

26

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

27

Tue Jul 24
  • Sections 17.2-17.4 Turing machine "programming"
  • Summer 2018: Last day to use a late day and submit HW 10.
  • Pumping Theorem examples
7

28

Thu 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

Fri Jul 27
  • Chapter 18 Church-Turing Thesis (what is "computable"?)
  • Summer 2018: Last day to use a late day and submit HW 11.
  • Turing Machine Examples
  • Formal definitions of TM computations
  • Acceptance by a TM
  • Turing Machine subroutines (Macro langiuage)
  • The sets D and SD
8

30

Mon Jul 30
  • Chapter 19 Halting - an undecidable problem
  • Language recognition vs. function computation
  • Multiple Tapes.
8

31

Tue Jul 31
  • Chapter 20 Decidable and Semidecidable languages
  • Summer 2018: Last day to use a late day and submit HW 12.
  • Multiple Tracks
  • Multiple Tapes.
8

32

Thu Aug 2

  
  • HW13 is not due until Monday; there is a reason for that! It is a long and difficult assignment; start early.
  • 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

Fri Aug 3
  • Sections 21.5-21.7 More on (un)decidability questions
  
  • Answers to student questions about material for exam.
  • Church-Turing Thesis
9

34

Mon Aug 6
  • Sections 21.4-21.7 More on (un)decidability questions
  • HW 13
    This is a long assignment; start early!
    Has been updated for Summer, 2018
     
  • HW 13 problem statements
     
  • HW 13 Topics: Classify languages (regular, context-free, neither), Context-free pumping theorem, closure.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 13.
     
  • Summer 2018: Next exam is the final on August 30 at 1:00 PM.
  • Exam 3 in-class
    Will cover Sections 11.1-11.7, 11.1-11.8, 12.1-12.4, 12.6 13.1-13.5, 13.8, 14.1-14.3, 17.1-17.3, HW 10-14, Lectures 19-31
  
9

35

Tue Aug 7

  
  • Summer 2018: Last day to submit HW13 for credit.
     
  • Halting Problem intro
  • Decidable, SD, and non-SD languages
9

36

Thu Aug 9

    
10

37

Fri Aug 10

  
  • Summer 2018: Last day to submit HW14 for credit.
     
  • Decideability and enumerability
10

38

Mon Aug 13
  • Chapter 27 Analysis and Complexity
  • Sections 28.1-28.3 P and NP
  • Overview of reduction.
  • Use reduction to show that another language is undecidable
10

39

Tue Aug 14
  • Summer 2018: Last day to submit HW15 for credit.
     
  • Reduction and more Undecidability proofs
  • Reductions with a twist
10

40

Thu Aug 16
  • 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.
     
  • Summer 2018 only: The material from HW17 will not be covered on the final exam.
  • HW 16
    Has been updated for Summer, 2018
     
  • 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, 2018
     
  • Solution
  • 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

Fri Aug 17
  • 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.