MA/CSSE 474 – Theory of Computation

Spring, 2017-18 (201830) Schedule Overview updated Thu May 17 at 8:52:30 AM

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

View Late day balances

Claude's Schedule (changes each week)


Session quick links:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

Week Session Preparation HW Due Topics Resources
1

1

Mon Mar 5
  • UNDER CONSTRUCTION"This schedule will be updated as the course goes along; Slides, notes pages, and announcements will be added for each class day (usually on that day). There may be minor shifting of topics and reading assignments, depending on how far we get in class each day.
     
  • Read the email I sent before the term began.
     
  • Unless I specify otherwise, all readings are from Automata, Computability, and Complexity by Elaine Rich.
    It appears that the less-expensive international edition has the same contents as the American edition.
     
  • Read Appendix A: Sections A.1-A.6.
    See the quiz info in the HW Due column
      * Based on your reading, identify topics that you need to review in detail before the course begins (or early in the course)
  • Bookmark this page in your browser so you can find it quickly
     
  • Sign up for this course on Piazza:
    http://piazza.com/rose-hulman/spring2018/macsse474/.
  • Reading quiz 1 (MSWord, pdf) is due today (yes, Monday) at the beginning of class!
     
  • HW will usually be due on Mondays and Thursdays at 11:55 PM.
     
  • (today and every day) Before class begins, do the items in the preparation column on this schedule.
     
  • Non-required HW 0 In some previous years, I required students to do these problems, but a few years ago, I decided that students whose prerequisite background is strong may not need to take the time to write up their solutions. You should at least take a look at the problems. This is a REAL assignment, but it is one that you do not have to turn in. If there are any (and it is very likely that there will be some) problems that appear to not be very easy for you, you should actually do them by the end of the first week, get help if needed, and compare your answers to the posted solutions. A few of these problems may actually appear in required homework at some point.
     
  • HW0 problem details
  • HW0 solution
     
  • Turnins: when and where?
    Reading quizzes:
    Due at beginning of class.
    Hard copy only.
    Print and write answers by hand, or
    answer electronically and then print.
    Please 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.
    Submit each assignment as a single document,
    preferably less than 2 MB.
  • 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
  • Today's announcements
  • Class Notes
     
  • 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.
     
  • Email that I sent to students before the course began.
     
  • Induction proof writeup Similar to how it could be written if it was a 474 assignment.
     
  • You may want to get JFLAP, software
    that lets you draw and execute various kinds of automata.
      JFLAP Tutorial
     
  • Recommendation: Make note of textbook errata file, and reference it as you read the textbook.
     
  • Graders:
    CG Coleman Gibson gibsonjc
    KG Kieran Groble grobleke
    QZ Qinmao (Fred) Zhang zhangq2
1

2

Tue Mar 6
  • Read the Course Syllabus/Policies.
     
  • (optional) Instructor intro video on Moodle. Note: This is 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.
     
  • Read my solutions to the reading quiz 1 questions (posted on Moodle Monday at noon)).
     
  • 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, write down any questions that you may have. This material, much of which should be review from the DISCO courses, is fundamental to everything that we will do in this course. For many more examples of formal languages, See Grimaldi, section 6.1. (pages 309-318). Note that Grimaldi uses λ to represent the empty string, while Rich uses ε.
     
  • Sections 3.1-3.2 (pages 21-27) Language recognition, encoding. This is also very important material.
  • Reading quiz 2 (MSWord, pdf) is due today at the beginning of class!
    or bring it to my office (or my box in the CSSE workroom, F233) by Wednesday at noon.
     
  • Optional Q&A session Tuesday 10th hour, G310
    Agenda:
    1. Answer your questions about anything from Appendix A or from the first Preparation quiz.
    2. If time remains, do additional Mathematical Induction example(s)
    3. No new topics wil be covered.

     
  • If you have not looked at the non-turnin HW0 yet, today may be good day to do so, since nothing is due on Wednesday.
  • Non-required HW 0
  • hw00-problems
  • 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

Thu Mar 8
  • 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.
     
  • The importance of Chapter 4: This chapter introduces many ideas that we will explore in detail throughout the course. Key terms and ideas: decision procedure, nondeterministic, a function on a language, whether a set of languages is closed under a function. You should be ready to do some of the HW2 problems after reading this chapter.
     
  • Section 4.1 (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.
     
  • Read my solutions to the reading quizzes 1 and 2 (posted on Moodle).
  • HW 1 over Chapters 1-2 and mathematical induction. Due at 11:55 PM
    Has been updated for Spring, 2018
     
  • hw01-problems
     
  • Be sure to read this sample induction proof writeup before you do the induction problems in this assignment.
     
  • For extra credit, complete the survey associated with each HW assignment. It is best if you complete it within 24 hours after doing the problems, while they are fresh on your mind. If you want the extra credit, it must be completed by the end of the day after the late day period.
     
  • HW 1 on Moodle:  Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 1 survey. See how much time past students spent on the assignment, and which problems they thought were hardest.
     
  • Solutions for each assignment will be available after the last day students can use a late day for that assignment.
    For HW1 in Spring, 2018, that will be March 10.
     
  • 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

Fri Mar 9
  • 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 over a given alphabet) and whose range is also a set of languages. So the function takes a language as its input parameter and returns a language.
     
  • The first part of Chapter 5: These sections formalize and provide mathematical notations for the notion of computation by a deterministic finite state machine that we saw informally in Session 1.
     
  • Chapter 5 intro, Section 5.1 (pages 54-60) Formal definition of DFSM.
  • 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)
  • 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. If you need logic review, these may help. 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.
2

5

Mon Mar 12
  • Sections 5.2-5.3 (pp 60-66) More on Deterministic FSMs
  • HW 2 (due at 11:55 PM, as are all HW assignemts, unless I specify otherwise)
    Has been updated for Spring, 2018
     
  • HW 2 Topics: language recognition, intuition about PDAs, semidecision problem, functions on languages, design simple DFSMs, language counting problems.
     
  • hw02-problems As with the HW1 problems document, this contains the problem descriprions from the textbook, so that it is not necessary for you to have the (huge) book with you when you do the problems. The HW2 assignment document may include additional instructor comments, clarifications, and previous terms' Q&A from Piazza that are not found here.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 2 survey. See how much time thosestudents spent on the assignment, and which problems were hardest.
  • Equivalence of computation and language recognition decision problem (continued)
  • Formal definition of computation and acceptance DFSM
  • DFSM examples
  • (if time) Non-determinism introduction
2

6

Tue Mar 13
  • Section 5.4 (pp 66-79) Non-deterministic FSMs
  
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

Thu Mar 15
  • Sections 5.5-5.6(pp 79-82) Practical FSMs
  • DFSM Minimization
  • Equivalence classes of a language
  • Myhill-Nerode Theorem
2

8

Fri Mar 16
  • Sections 5.7-5.8 (pp 82-96) Minimization and Canonical Form
  
  • More on minimization
  • DFSM Canonical form
3

9

Mon Mar 19
  • Section 6.1 (pp 127-132) Intro to regular expressions
  • You may want to read Appendix C after class.
  • HW 4
    Has been updated for Spring, 2018
     
  • Due to the exam on Tuesday:
    • This small assignment is due at 5:00 PM instead of 11:55 PM.
    • No late days may be used for this assignment.
    • As usual, you may earn a late day by submitting by 11:55 PM Sunday.
    • Solutions will appear on Moodle at 5:05 PM Monday, so that you will have an opportunity to look at them and ask questions on Piazza before the exam.

     
  • 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.
  • NDFSM-->DFSM Proof
  • (if time) Regular expression intro
3

10

Tue Mar 20

  
  • Exam is Closed book and notes, but I will provide a notes page.
     
  • Notations and Definitions page that I gave 201620 students with Exam 1. Is there anything else you would like to see there? If so, let me know by noon of the Saturday before the exam.
     
  • During the exam, students may not use electronic devices or headphones/earbuds
    .
  • If you have not looked at problems 2 and 3 from HW5, you should do so today, so you have a chance to ask questions.
3

11

Thu Mar 22
  • 6.2 (pp 133-146) Kleene's Theorem
  • 6.3-6.4 (pp 147-150) Practical aspects of regular expressions
  • HW 5
    Has been updated for Spring, 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
     
  • Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 5.
  • Exam discussion
  • Regular Expressions and languages they define
  • Kleene's Theorem
  • Proof: Regular expression → NDFSM
  • (if time) Begin DFSM → regular expression proof and algorithm
3

12

Fri Mar 23
  • 8.1-8.3 (pp 162-169) Regular languages and closure properties
  
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Mon Mar 26
  • 8.4-8.6 (pp 169-182) Pumping theorem, functions on Regular languages
  • DFSM → Regular Expression (example)
  • Practical regular expressions (from Appendix O)
  • How many regular languages?
  • Ways of showing a language to be regular.
  • Closure properties of regular languages.
4

14

Tue Mar 27
  • 9.1-9.2 (pp 187-195) Algorithms and Decisions
  
  • Showing a language to be non-regular
  • Pumping Theorem
4

15

Thu Mar 29

  
  • HW 7
    Has been updated for Spring, 2018
  • HW 07 problem statements
  • 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.
  • HW 7 Topics: reg. exp → FSM, FSM → reg. exp, logic description → reg. exp.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 7.
     
  • Pumping Theorem examples
4

16

Fri Mar 30
  • Chapter 10 Summary of Regular Languages (1.5 pages)
  
  • More regular or not exaamples
  • Regular languages closed under various functions?
  • Decision Procedures related to regular languages.
  • In-class exercises
5

17

Mon Apr 2
  • Chapter 7 Regular grammars
  • 11.1-11.2 Intro to Context-free languages
  • Grammar intro
  • Regular Grammars
  • Context-free Grammars
  • Derivations
5

18

Tue Apr 3
  • 11.3-11.4 Working with CFGs
  
  • As you prepare for the exam, write down questions that you have, so you can ask them in today's class
  • Working with CFGs
  • Derivation Trees
  • Structure
  • CFG's to generate some specific languages
5

19

Thu Apr 5
  • Review for exam 2
  
  • Exam 2 in class.
    Will cover Sections 5.7-5.8, 6.1-6.4, 8.1-8.6, 10
    (be sure to consider the T/F problems in Problem 8.21)
    and HW 5-8
5

20

Fri Apr 6
  • 11.5 - 11.7.2 Correct grammars, derivations, ambiguity
  • HW 9.
    Has been updated for Spring, 2018
     
  • Due to the break, the late day for HW9 is extended until 11:55 PM Monday, April 9.
    Turn it in by then; use one late day.
  • 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.
     
  • Useless nonterminals
6

21

Mon Apr 16
  • 11.8 Normal forms
  • 12.1 - 12.2.2 PDA intro
  
  • Ambiguity; removing ambiguity
6

22

Tue Apr 17

  
  • HW 10. Due on Tuesday because of the break. We'll be back to the regular schedule for HW 11, which is a normal-length assignment.
    Has been updated for Spring, 2018
     
  • HW 10 problem statements
     
  • HW 10 Topics: CFG simplification, grammars for specific languages, a grammar for arithmetic expressions.
     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 10.
     
  • More on removing ambiguity
  • Normal forms (Chomsky and Greibach) and simplification
  • Push-down automata: formal definition
6

23

Thu Apr 19
  • Sections 12.3-12.4 Equivalence of PDAs and CFGs, Halting
  • Push-down automata examples
  • Explore the role of nondeterminism
6

24

Fri Apr 20

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

25

Mon Apr 23
  • Chapter 14 CFL Algorithms and Decision Problems
  • 16 (skim these three pages) (Chapter 15 material is covered in the compilers course, CSSE 404)
  • Bottom-up parser
  • Pumping Theorem intro
7

26

Tue Apr 24
  • Section 17.1
  
  • Pumpung Theorem examples
  • CFL closure
7

27

Thu Apr 26
  • Sections 17.2-17.4 Turing machine "programming"
  • Misc CFL properties
  • CFL Closure Properties
  • CFL Decision Problems
7

28

Fri Apr 27
  • Sections 17.5-17.7 Alternative TM defs,
    Encoding a TM, the universal TM
  
  • Turing Machine Intro, notation
  • Turing Machine Examples
8

29

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

30

Tue May 1
  • Chapter 19 Halting - an undecidable problem
  
  • Exam 3 in-class
    Will cover Sections 8.6, 9.1-9.2, 10, 11.1-11.7, 11.1-11.8, 12.1-12.4, 12.6 13.1-13.5, 13.8, 14.1-14.3, 16,
    HW 9-14a,
    Lectures 17-27
8

31

Thu May 3
  • Chapter 20 Decidable and Semidecidable languages
  
  • Exam discussion
  • Language recognition vs. function computation
8

32

Fri May 4

    
  • No class meeting today
9

33

Mon May 7
  • Sections 21.5-21.7 More on (un)decidability questions
  
  • Multiple Tapes.
  • 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

34

Tue May 8
  • Sections 21.4-21.7 More on (un)decidability questions
  • Universal TM
  • Church-Turing Thesis
  • Halting Problem Background
9

35

Thu May 10

    
  • Halting Problem
  • Decidable, SD, and non-SD languages
  • Enumerability and Decidability
9

36

Fri May 11

    
  • Intro to Reduction
10

37

Mon May 14

  
  • HW 15
    Has been updated for Spring, 2018
  • HW 15 problem statements Did not include problem 6 here, since it is not from the textbook.
     
  • 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
     
  • Student survey results from a previous term's HW 15.
    Note that what are now problems 1-6 were problems 2-7 when this survey was administered.
  • Use reduction to show another language is undecidable
10

38

Tue May 15

  
  • Reduction and more Undecidability proofs
  • Reduction practice
10

39

Thu May 17
  • NOT REQUIRED to be turned in, but practice for the final exam.
  • HW 17
  • Reductions with a twist
  • Rice's Theorem
  • Show that some languages are not SD
10

40

Fri May 18

  
  • No regular class meeting.
  • Senior Exams in CSSE conference room. According to the schedule I sent by email. See the notes below, day 41.
11

41

Mon May 21
  • Re-read sections from the book that you did not understand the first time.
  • Do lots of problems, including some "not-to-turn-in" problems fro the HW.
  • Final exam Tuesday at 8:00 AM, third floor of Crapo.
  • My best guess is that this exam will be about 3 times as long as one of my 50-minute exams.
    You will have almost 5 times as long to do it, so there should be less time pressure.
  • I will provide at the exam: "definition and formula" sheet,
    It includes the "Turing machine macros reference".
  • Final Exam will cover material from the whole course.
  • But there will be more emphasis on things that were not covered by the in-class exams:
    Chapters 17.3-17.7, 18, 19, 20, 21; HW 14b-17, lectures 28-39.
  • That material is about 25% of the course, so it should constitute about 25% of the total exam grade for the course. This translates to about 70% of the final exam.
  • The actual percentage will probably be a little bit less.