MA/CSSE 474 – Theory of Computation

Summer, 2016 (201640) Schedule Overview updated Sun Aug 14 at 5:38:56 AM

This page will be updated as we proceed through the term (many updates will happen June 1-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

Fri Jun 3
  • UNDER CONSTRUCTION" This schedule will be updated as the course goes along
     
  • 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/summer2016/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.
     
  • Homework will usually be due on Mondays and Thursdays at 11:55 PM.
     
  • 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 this, 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.
     
  • 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 on due date.
    Electronic submissions only.
    Drop box on Moodle.
    Scanners in F217 and Library; Rose ID card gets you into F217.
    If off-campus, you can buy a new USB scanner for about $60.00.
    Submit each assignment as a single 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

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

Mon Jun 6
  • Read the Syllabus/Policies on Moodle. Ask quesions on Piazza if something is not clear.
     
  • 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.
  • HW 1 over Chapters 1-2 and mathematical induction. Due at 11:55 PM
     
  • hw01-problems
  • 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.
     
  • Solution
  • Roll call
  • 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
1

3

Tue Jun 7
  • 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

Thu Jun 9
  • 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
     
  • As discussed on Piazza, HW2 due date is moved to Friday.
     
  • Summer: Last day to use late days and submit HW 1.
  • 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)
  • Summer: Virtual Office Hours (VOH) optional 8:00 PM. I'll post the link on Piazza.
     
  • 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 a FSM
     
  • Solution to today's in-class quiz.
2

5

Fri Jun 10
  • 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
  • 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.
     
  • 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
  • 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

Mon Jun 13
  • Sections 5.5-5.6(pp 79-82) Practical FSMs
  • Summer: VOH (optional) 8:00 AM.
     
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

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

8

Thu Jun 16
  • Section 6.1 (pp 127-132) Intro to regular expressions
  • 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 late days and submit HW 3.
  • Summer: VOH (optional) 8:00 PM.
     
  • More on minimization
  • DFSM Canonical form
3

9

Fri Jun 17
  • Section 6.2 (pp 133-146) Kleene's Theorem
     
  • Sections 6.3-6.4 (pp 147-150) Practical aspects of regular expressions
  • NDFSM-->DFSM Proof
  • (if time) Regular expression intro
3

10

Mon Jun 20
  • 8.1-8.3 (pp 162-169) Regular languages and closure properties
  • (Summer 2016): HW 5
     
  • 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
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 5.
     
  • Summer: Last day to use late days and submit HW 4.
  • Summer: VOH (optional) 8:00 AM.
     
  • 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.
  • 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)
  • Summer: VOH (optional) 8:00 AM. I'll post the link on Piazza.
     
  • No exam 1 in summer: Closed book and notes.
     
  • No electronic devices or headphones/earbuds
     
  • Today's announcements
     
  • Exam 1 from winter term, 2013-14
     
  • Exam 1 solution from winter term, 2013-14
     
  • Notations and Definitions that I gave 201620 students with Exam 1
     
3

11

Tue Jun 21
  • 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
3

12

Thu Jun 23

  
  • Summer: Last day to use late days and submit HW 5.
  • Summer: VOH (optional) 8:00 PM.
     
  • Not Summer: Exam discussion
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Fri Jun 24
  • 9.1-9.2 (pp 187-195) Algorithms and Decisions
  • DFSM → Regular Expression (continued)
4

14

Mon Jun 27
  • Chapter 10 Summary of Regular Languages (1.5 pages)
  • HW 7 over the last part of Chapter 6.
     
  • 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, while not hard, 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.
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 7.
     
  • Summer: Last day to use late days and submit HW 6.
  • Summer: VOH (optional) 8:00 AM.
     
  • If L is regular, then LR is regular.
  • Practical regular expressions (from Appendix O)
4

15

Tue Jun 28
  • 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

Thu Jun 30
  • 11.3-11.4 Working with CFGs
  • Summer: Last day to use late days and submit HW 7.
  • Summer: VOH (optional) 8:00 PM.
     
  • Pumping Theorem examples
  • Decision Procedures related to regular languages.
5

17

Fri Jul 1

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

  
  • Summer 2016 Holiday. Nothing due.
  • HW 9 is much longer than most assignments; and students in past terms that there are many hard problems.
    I am giving you extra time for it. Start soon if you have not already done so.
     
  • Not on this day in Summer, 2016
  • Decision Problems about Regular languages.
  • Many in-class exercises.
5

19

Tue Jul 5
  • 11.5 - 11.7.2 Correct grammars, derivations, ambiguity
  • Chapter 7 Regular grammars
  • Summer: Last day to use late days and submit HW 8.
  • Rewite systems and grammars
  • CFG intro
  • Derivations
  • CFG's to generate some specific languages
  • Regular grammars (Chapter 7)
5

20

Thu Jul 7
  • 11.8 Normal forms
  • 12.1 - 12.2.2 PDA intro
  • Recommendation: If you are not going anywhere for the break, why not go ahead and get HW 10 and HW 11 out of the way so you can focus more on exam preparation the following week?
  • Summer: VOH (optional) 8:00 PM.
     
  • Working with CFGs
  • Derivation Trees
  • Structure
6

21

Fri Jul 8
  • As you prepare for the exam, write down questions that you have, so you can ask them in today's class
  • HW 9 over the end of Chapter 8, and Chapter 9.
    Because of the break, Saturday and Sunday will not count as late days. You can use late days and submit until Wednesday.
     
  • 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.
     
  • 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 18
  • Review for exam 2 (Summer: Review for midterm exam)
  • Summer 2016: 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

Tue Jul 19
  • Sections 12.3-12.4 Equivalence of PDAs and CFGs; Halting
  • Wednesday is the last day to submit HW 10 for credit.
  • Summer 2016: Midterm exam will cover:
    • Assigned reading from Appendix A, Chapters 1-10, !!.1-11.6
    • HW 1-10
  • Will be on Moodle. Most likely 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.
  • Summer: Our exam will most likely be on Thursday.
  • More on Parse Trees
  • Ambiguity
6

24

Thu Jul 21
  • Summer 2016: Midterm exam this evening:
  • 9:00-11:00 PM Indiana time.
  • Normal forms (Chomsky and Greibach) and simplification
  • Pushdown Automata intro
  • PDA examples
7

25

Fri 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

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

27

Tue Jul 26
  • Sections 17.2-17.4 Turing machine "programming"
  
  • Pumping Theorem examples
7

28

Thu Jul 28
  • 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 29
  • 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

Mon Aug 1
  • Chapter 19 Halting - an undecidable problem
  • Because HW 13 is a long assignment, it will be due on Wednesday, not Monday. If you have not already made good progress on it, be sure to start today.
  • Language recognition vs. function computation
  • Multiple Tapes.
8

31

Tue Aug 2
  • Chapter 20 Decidable and Semidecidable languages
  • Multiple Tracks
  • Multiple Tapes.
8

32

Thu Aug 4

    
  • 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 5
  • Sections 21.5-21.7 More on (un)decidability questions
  • HW 14 is not due until Monday. There is a reason for that! Start early.
  • 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

Mon Aug 8
  • Sections 21.4-21.7 More on (un)decidability questions
  • Summer: Next exam is the final on August 31.
  • 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 9

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

36

Thu Aug 11

    
  • Class canceled due to instructor illness
10

37

Fri Aug 12

  
  • HW 15
    Has been updated for Summer, 2016
     
  • HW 15 problem statements
     
  • Summer, 2016: Due Monday, August 15.
  • HW 15 Topics: Multi-tape TMs, SD a proper subset of D, TMs for graphs of functions, Universal TM construction, Church-Turing Thesis, TM encodongs.
     
  • Drop Box    Survey    Solution
     
  • (1/2 class meeting) Decideability and enumerability
10

38

Mon Aug 15
  • Chapter 27 Analysis and Complexity
  • Sections 28.1-28.3 P and NP
  • HW 16
    Has been updated for Summer, 2016
     
  • HW 16 problem statements
     
  • Summer, 2016: Due Friday, August 19
     
  • HW 16 Topics: Semidecision, Decidability and undecidability, Closure properties, lexicographic enumeration, TM for enumerating a specific language, subset properties,
     
  • Overview of reduction.
  • Use reduction to show that another language is undecidable
10

39

Tue Aug 16

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

40

Thu Aug 18

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

41

Fri Aug 19
  • Re-read sections from the book that you did not get the first time.
  • Do lots of problems
  • HW 17
    Has been updated for Summer, 2016
     
  • Summer, 2016: Not to be submitted. Do it before the final exam, and check your answers using the solution that I will place on Moodle. Ask questions on Piazza if you wish.
     
  • Summer, 2016: Final exam August 31 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 exams:
    In Summer, 2016, 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.