MA/CSSE 474 – Theory of Computation

Summer, 2017 (201740) Schedule Overview updated Tue Sep 5 at 7:12:47 AM

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

View Late day balances  Who grades what?


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 Jun 1
  • UNDER CONSTRUCTION" This schedule will be updated as the course goes along.
    (5/19/2017): The only things that have been updated on this page since Summer 2017 are the links to Moodle pages that are in Session 0. Many changes to this page will happen beore 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 under HW Due
     
  • Bookmark this page in your browser so you can find it quickly
     
  • Sign up for this course on Piazza:
    http://piazza.com/rose-hulman/summer2017/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:
     
  • Examine the pre-course activity checklist on Moodle, and do the things on that list no later than the suggested dates.
     
  • (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 probl;ems, but a few years ago, I decided that students whose prerequisite background is strong may not need to take the itme to write it up. 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 there is a term 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

Thu Jun 1
  • Read my solutions to the reading quizzes 1 and 2 (posted on Moodle).
     
  • 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

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

Mon 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.
  
  • 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 6
  • 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 at 11:55 PM
    Has been updated for Summer, 2017
     
  • 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.
  • 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.
     
  • Solution to today's in-class quiz.
2

5

Thu 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 (30:00)
  • About the above video: Given a NDFSM , show how to construct an equivalent DFSM. Jerry Ullman is one of the "grandfathers" of automata theory. The book he wrote with John Hopcroft in 1968 (and its later editions) was the standard book on the subject for many years. Ullman is getting up there in years, so I recommend watching this video at 1.25 speed (click the "gear" icon on the YouTube screen). I think you'll find the first 30 minutes of this video to be very helpful.
2

6

Fri Jun 9
  • Sections 5.5-5.6(pp 79-82) Practical FSMs
  • Summer: Last day to use late days and submit HW 1.
    Don't forget the HW1 Extra-credit survey on Moodle.
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

Mon Jun 12
  • Sections 5.7-5.8 (pp 82-96) Minimization and Canonical Form
  • 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, 2017
     
  • HW 2 Topics: language recognition, intuition about PDAs, semidecision problem, functions on languages, design simple DFSMs, language counting problems.
     
  • hw02-problems
     
  • 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.
  • DFSM Minimization
  • Equivalence classes of a language
  • Myhill-Nerode Theorem
2

8

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

9

Thu 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 late days and submit HW 2.
     
  • HW 3
    Has been updated for Summer, 2017
     
  • HW 3 Topics: Design more complex DFSMs, design NDFSMs
     
  • hw03-problems
     
  • Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 3 survey.
  • NDFSM-->DFSM Proof
  • (if time) Regular expression intro
3

10

Fri Jun 16
  • 8.1-8.3 (pp 162-169) Regular languages and closure properties
  • Summer: Sunday, June 18, 2017 is the last day to use late days 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,
  • 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

Mon Jun 19
  • 8.4-8.6 (pp 169-182) Pumping theorem, functions on Regular languages
  • Regular Expressions and languages they define
  • Kleene's Theorem
  • Proof: Regular expression → NDFSM
  • (if time) Begin DFSM → regular expression proof and algorithm
  • PPT / Slides
     
  • Today's announcements
     
  • Class Notes
     
  • Video: Equivalence of DFSM and Regular Expression (21:28)
    For this particular algorithm, I like the approach of Hopcroft and Ullman better than that of Rich. This video demonstrates their algorithm. Their algorithm has a nice tie-in to a graph algorithm from Rose-Hulman's Design and Analysis of Algorithms class. This is another video by Jeffrey Ullman. The part of the video of interest starts at 12:47 and goes until 34:15. Of course you can watch the whole thing if you wish.
     
3

12

Tue Jun 20

  
  • 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.
     
  • Not Summer: Exam discussion
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Thu Jun 22
  • 9.1-9.2 (pp 187-195) Algorithms and Decisions
  • Summer: Last day to use late days and submit HW 4.
  • HW 5
    Has been updated for Summer, 2017
     
  • 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.
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 5.
     
  • DFSM → Regular Expression (continued)
4

14

Fri Jun 23
  • Chapter 10 Summary of Regular Languages (1.5 pages)
  • Summer: Sunday, June 25, 2017 is the last day to use late days and submit HW 5.
  • If L is regular, then LR is regular.
  • Practical regular expressions (from Appendix O)
4

15

Mon Jun 26
  • 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 27
  • 11.3-11.4 Working with CFGs
  
  • Pumping Theorem examples
  • Decision Procedures related to regular languages.
5

17

Thu Jun 29

  
  • Summer: Last day to use late days and submit HW 6.
  • Summer: Because of the holiday weekend, I delayed the due date for HW 7 until Saturday, so you have the option of catching up during the weekend if you prefer. If you want to have an easier weekend, pretend that it is due on the normal day, which would be today.
     
  • 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 30

  
  • HW 7 over the last part of Chapter 6. Due Saturday at 11:59.
    Has been updated for Summer, 2017
     
  • 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.
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 7.
     
  • Decision Problems about Regular languages.
  • Many in-class exercises.
5

19

Mon Jul 3
  • 11.5 - 11.7.2 Correct grammars, derivations, ambiguity
  • Chapter 7 Regular grammars
  • Summer 2017 Holiday. Nothing due.
  • Rewite systems and grammars
  • CFG intro
  • Derivations
  • CFG's to generate some specific languages
  • Regular grammars (Chapter 7)
  • PPT / Slides
  • Today's announcements
  • Class Notes
     
  • Video: CFG intro (6:44)
     
  • Video: CFG example grammars, derivation, and derivation tree (3:44)
     
  • Video: CFG example grammars, derivation, and derivation tree (3:44)
    A student had trouble accessing my first Moodle upload of this video, so I am trying again.
  • Video:Backus-Naur Form (BNF) (4:00)
     
5

20

Tue Jul 4
  • 11.8 Normal forms
  • 12.1 - 12.2.2 PDA intro
  • Summer: Last day to use late days and submit HW 7.
  • Summer 2017 Holiday. Nothing new is due.
     
  • 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. Start early.
     
  • Working with CFGs
  • Derivation Trees
  • Structure
6

21

Thu Jul 6
  • As you prepare for the exam, write down questions that you have
  • HW 8 Over Chapter 8
    Has been updated for Summer, 2017
     
  • HW 08 problem statements
     
  • Summer 2017:Just in case you prefer to have an easier week this week and do some "catching up" during the break week, I am giving five "grace days" for this assignment. You can turn it in until 11:55 PM Tuesday, July 11 without using any late days. After that you must use late days.
     
  • In order to count as an "early" day, you must submit by Monday, July 10.
     
  • HW 8 Topics: Languages: regular or not, pumping theorem, closure of regular languages under functions
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 8.
     
  • 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

Fri Jul 7
  • 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.
    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

Mon 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, 2017
    Because of the exam, you can only use one late day for this assignment.
     
  • 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
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 9.
     
  • More on Parse Trees
  • Ambiguity
6

24

Tue Jul 18
  • Summer 2017: Last day to submit HW9 for credit.
     
  • Summer 2017: You can take the Midterm exam on Wednesday or Thursday: On Moodle, using Remote Proctor (RPNow)
  • Normal forms (Chomsky and Greibach) and simplification
  • Pushdown Automata intro
  • PDA examples
7

25

Thu 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 2017: Midterm exam will cover:
    • Assigned readings from Appendix A, Chapters 1-10 (in the Preparation column for sessions 1-14)
    • HW 1-9
  • Will be on Moodle. We will use Remote Proctor.
  • 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, delta for δ, Sigma* for Σ* (similar for other Greek letters such as epsilon).
  • Detailed description of the exam environment, allowed resources, etc.
  • Nondeterminism in PDAs
  • From a CFG, can produce equivalent PDA
  • Top-down parser
  • Bottom-up parser
7

26

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

27

Mon Jul 24
  • Sections 17.2-17.4 Turing machine "programming"
  • Pumping Theorem examples
7

28

Tue Jul 25
  • 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

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

30

Fri Jul 28
  • Chapter 19 Halting - an undecidable problem
  • Summer 2017: Sunday is the ast day to submit HW11 for credit.
     
  • Language recognition vs. function computation
  • Multiple Tapes.
8

31

Mon Jul 31
  • Chapter 20 Decidable and Semidecidable languages
  • Multiple Tracks
  • Multiple Tapes.
8

32

Tue Aug 1

  
  • HW13 is not due yet, but 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

Thu Aug 3
  • Sections 21.5-21.7 More on (un)decidability questions
  • Summer 2017: Last day to submit HW12 for credit.
     
  • Answers to student questions about material for exam.
  • Church-Turing Thesis
  • No new slides or notes page for today. We'll continue with Session 32 slides and notes.
  • Today's announcements
9

34

Fri Aug 4
  • Sections 21.4-21.7 More on (un)decidability questions
  • Summer 2017: I moved HW 13 due date from yesterday to Monday.
  • Summer 2017: 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

Mon Aug 7

  
  • Halting Problem intro
  • Decidable, SD, and non-SD languages
9

36

Tue Aug 8

      
10

37

Thu Aug 10

  
  • Decideability and enumerability
10

38

Fri Aug 11
  • Chapter 27 Analysis and Complexity
  • Sections 28.1-28.3 P and NP
  • Summer 2017: Sunday is the last day to submit HW14 for credit.
     
  • Overview of reduction.
  • Use reduction to show that another language is undecidable
10

39

Mon Aug 14
  • Reduction and more Undecidability proofs
  • Reductions with a twist
10

40

Tue Aug 15

  
  • Rice's Theorem
  • Show that some languages are not SD * Undecidable properties of CFLs
  • Practice problems
11

41

Thu Aug 17
  • Re-read sections from the book that you did not get the first time.
  • Do lots of problems
  • Summer 2017: Last day to submit HW15 for credit.
     
  • HW16 and HW17 are NOT REQUIRED to be turned in, but do these problems as practice for the final exam.
    I will post solutions.
     
  • HW 16
    Has been updated for Summer, 2017
     
  • HW 16 problem statements
     
  • HW 16 Topics: Semidecision, Decidability and undecidability, Closure properties, lexicographic enumeration, TM for enumerating a specific language, subset properties,
     
  • HW 17
    Has been updated for Summer, 2017
     
  • Summer, 2017: Final exam August 30, 1:00-3:00 PM in room G310.
  • Final Exam will cover material from the whole course.
  • But there will be more emphasis on things that were not covered by the midterm exam:
    In Summer, 2017, 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-17, lectures 21-40.