MA/CSSE 474 – Theory of Computation

Spring, 2019-20 (202030) Schedule Overview updated Wed May 20 at 3:47:25 PM

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

View Early 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 9
  • 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 emails that 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.
     
  • Spring 2020: Now the textbook is online and free
     
  • Read Appendix A: Sections A.1-A.6 37 pages.
    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/spring201820/macsse474/.
    I suggest editing your email preferences to "real time" and "Follow all".
  • Reading quiz 1 (MSWord, pdf) is due today (yes, Monday) at the beginning of class!
    Solution will be available Monday afternoon.
     
  • 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 (but recommended for many students) 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 available in F217 and Library.
    Rose ID card gets you into F217.
    Submit each assignment as a single document.
    Do not write on both sides of a paper that you plan to scan or photograph.
  • 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.
     
  • 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
     
  • Graders:
    NG Nathan Greiner greinernc
    QL Qiuyun Li liq1/td>
    VL Valerie Liu liur5
    AM Andrew Meng menga
    SP Stella Prk parks8
    FS Fisher Shen shenx/td>
    HY Hao Yang yangh4
    YZ Yuqi Zhou zhouy9
1

2

Tue Mar 10
  • Read the Course Syllabus/Policies.
     
  • (optional) Instructor intro video on Moodle.
     
  • Read my solutions to the reading quiz 1 questions (available on Moodle Monday afternoon).
     
  • Chapter 1 (5 pages) Why study ToC? Read it quickly;
    there are no details that you need to retain (yet!).
     
  • Chapter 2 (10 pages) 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(in the MA275-375 book) uses λ to represent the empty string, while Rich uses ε.
     
  • Sections 3.1-3.2 (5 pages) Language recognition, encoding. This is also very important material.
  • Reading quiz 2 (MSWord, pdf) is due today (bring hard copy) at the beginning of class!
    Solution will be available Tuesday afternoon.
     
     
  • 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 12
  • Section 3.3 (5 pages) 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 (4 pages) Decision Procedures.
    Another fundamental building block of the course.
  • Section 4.2 (6 pages) 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
     
  • 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 due date.
     
  • HW 1 on Moodle:  Drop Box    Survey    Solution
    Solution will be available after the homework is due. FOr HW1 in 2020, that will be March 13.
     
  • 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 on Moodle after the due date for that assignment.
    For HW1 in Spring, 2020, that will be March 13.
     
  • 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 13
  • Section 4.3 (3 pages) 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 (5 pages) 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)
2

5

Mon Mar 23
  • Sections 5.2-5.3 (5 pages) More on Deterministic FSMs
  • HW 2 (due at 11:55 PM, as are all HW assignemts, unless I specify otherwise)
     
  • Spring, 2020: due date delayed until Tuesday
     
  • 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 24
  • Section 5.4 (10 pages) Non-deterministic FSMs
  
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

Thu Mar 26
  • Sections 5.5-5.6(4 pages) Practical FSMs
  • DFSM Minimization
  • Equivalence classes of a language
  • Myhill-Nerode Theorem
2

8

Fri Mar 27
  • Sections 5.7-5.8 (10 pages) Minimization and Canonical Form
  
  • More on minimization
  • DFSM Canonical form
3

9

Mon Mar 30
  • Section 6.1 (5 pages) Intro to regular expressions
  • You may want to read Appendix C after class.
  
3

10

Tue Mar 31
  • 6.2 (11 pages) Kleene's Theorem
  
  • NDFSM-->DFSM Proof (skip this for Spring 2020)
3

11

Thu Apr 2
  • 6.3-6.4 (5 pages) Practical aspects of regular expressions
  • HW 5
     
  • Spring, 2020: due date delayed until Saturday
     
  • 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.
  • 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 Apr 3
  • 8.1-8.3 (6 pages) Regular languages and closure properties
  
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Mon Apr 6
  • 8.4-8.6 (9 pages) Pumping theorem, functions on Regular languages
  • HW 6 Due at 5:00 PM
     
  • Spring, 2020: due date delayed until Thursday
     
  • HW 06 problem statements
     
  • HW 6 Topics: Regular expression basics, simplification
     
  • Due to the exam on Tuesday:
    • This small assignment is due at 5:00 PM instead of 11:55 PM.
    • As usual, you may earn a late day by submitting by 11:55 PM Sunday.
    • Solutions will appear on Moodle at 5:00 PM Monday, so that you will have an opportunity to look at them and ask questions on Piazza before the exam.

     
  • On Moodle: Drop Box    Survey    Solution
     
  • Student survey results from a previous term's HW 6.
     
  • 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 Apr 7
  • Get enough sleep so that you can think well during the exam.
  • Notations and Definitions page that I gave 201830 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.
     
  • Spring 2020: Exam will happen on this day (April 7), but
    1. It will be open book and notes
    2. I will be more flexible about what time you take it.
      Tentatively any 90 minutes that are entirely within 8:00 AM - 4:00 PM.
      Let me know soon if this is a problem for you.
    3. I will give you 90 minutes to take it (since #2 above will allow me to do that).
  • Exam 1 will happen today.
4

15

Thu Apr 9
  • 9.1-9.2 (7 pages) Algorithms and Decisions
  • HW 7
     
  • Spring, 2020: due date delayed until Monday
     
  • 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. It is the Rijk approach from the Kleene Theorem DFSM->RE video.
  • Problem 6 (6.18 from the textbook) is as much about reading logical statements as it is about languages. You may have to read it a few times in order to understand it. Once you do, the answer is simple.
  • 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.
     
  • Showing a language to be non-regular
  • Pumping Theorem
  • Pumping Theorem examples
4

16

Fri Apr 10
  • 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 13
  • Chapter 7 Regular grammars (5 pages)
  • 11.1-11.2 Intro to Context-free languages (7 pages)
  • Grammar intro
  • Regular Grammars
  • Context-free Grammars
  • Derivations
5

18

Tue Apr 14
  • 11.3-11.4 Working with CFGs (4 pages)
  
  • Working with CFGs
  • Derivation Trees
  • Structure
  • CFG's to generate some specific languages
5

19

Thu Apr 16
  • 11.5 - 11.7.3 Correct grammars, derivations, ambiguity (8 pages)
  • HW 9.
     
  • Spring, 2020: due date delayed until Tuesday, April 21
     
  • 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.
     
  • Ambiguity; removing ambiguity (read about it on your own)
  
5

20

Fri Apr 17
  • Section 11.8 Simplifying grammars, normal forms (8 pages)
  
  • Useless nonterminals
  • Simplifying Grammars
  • Chomsky Normal Form
  • Greibach Normal Form (briefly mentioned in Section 11.8)
6

21

Mon Apr 20
  • 12.1 - 12.2.2 PDA intro (7 pages)
  
  • Push-down Automata
6

22

Tue Apr 21
  • Section 12.2.3 techniques for reducing nondeterminism (2 pages)
  • Push-down automata examples
  • Explore the role of nondeterminism
6

23

Thu Apr 23
  • Sections 12.3, 12.3.1 (not 12.3.2), 12.4 Equivalence of PDAs and CFGs, Halting (6 pages)
  
6

24

Fri Apr 24

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

25

Mon Apr 27
  • 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 28

  
  • Spring, 2020: Exam 2 delayed until Monday, May 4
     
7

27

Thu Apr 30
  • Section 17.1
  • Sections 17.2-17.4 Turing machine "programming"
  • Pumping Theorem examples
  • CFL closure
  • Misc CFL properties
  • CFL Closure Properties
  • CFL Decision Problems
7

28

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

29

Mon May 4
  • 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 5
  • Chapter 19 Halting - an undecidable problem
    
8

31

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

32

Fri May 8

    
  • Universal TM
9

33

Mon May 11
  • Not covered Spring, 2020:
     
  • Sections 21.5-21.7 More on (un)decidability questions
  
  • Church-Turing Thesis
9

34

Tue May 12
  • Not covered Spring, 2020:
     
  • Sections 21.4-21.7 More on (un)decidability questions
  
  • Halting Problem Background
9

35

Thu May 14

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

36

Fri May 15

    
  • Not covered Spring, 2020:
     
  • Intro to Reduction
10

37

Mon May 18

  
  • HW 15
  • Spring, 2020: due date delayed until Wednesday, May 20
     
  • 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.
  • Not covered Spring, 2020:
  • Use reduction to show another language is undecidable
10

38

Tue May 19

  
  • Not covered Spring, 2020:
     
  • Reduction and more Undecidability proofs
  • Reduction practice
10

39

Thu May 21
  • NOT REQUIRED to be turned in, but practice for the final exam.
  • (May 8 decision) Spring, 2020: You will not be responsible for this material on the final exam.
    It's really too bad that we ran out of time before getting to this, because it is in many ways the core material from the course.
    But we played the hand that was dealt to us.
    This material also would have been the most difficult of the course.
     
  • HW 17
  • Not covered Spring, 2020:
     
  • Reductions with a twist
  • Rice's Theorem
  • Show that some languages are not SD
10

40

Fri May 22

    
11

41

Mon May 25
  • 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 from the HW.
  • (May 8 decision) Spring, 2020 final exam: Saturday May 23, 10:00AM-1:00PM Indiana time.
  • If you have extra-time accomodations, strart at 10 and end at 2:30 (50% extra time) or 4:00 (100% extra time).
  • Like the other exams, it will have a lot of T/F/IDK, multiple choice, short answer, and possibly other auto-graded problems. There will be a few essay questions and an optional Moodle drop box for submitting them.
  • Some of the problems will describe a language and ask you to classify it as finite, regular, context-free, decidable, or not decidable.
  • A good resource for studying, and for reference during the exam: "definition and formula" sheet,
    It includes the "Turing machine macros reference".
    Note that it includes some Chapter 21 material, which will not be in this exam.
  • Final Exam will cover material from the whole course.
  • But there will be more emphasis on things that were not covered by the previous exams:
    Chapters 12, 13, 14, 17.3-17.7, 18, 19, 20; HW 12-16.