MA/CSSE 474 – Theory of Computation

Winter, 2015-16 (201620) Schedule Overview updated Wed Feb 24 at 2:17:09 PM

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

Exam dates are correct for Winter 2015-16; topics may change.You can put the exams in your calendar.
Planned HW due dates up through HW10 are also correct, but the later assignments themselves are not yet updated,
  and there may be some changes as we get closer to the dates.
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

Week Session Preparation HW Due Topics Resources
1

1

Mon Nov 30
  • UNDER CONSTRUCTION"This schedule will be updated as the course goes along; Schedule and assignments have been updated for days 1-10. 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.
    What is here for days 11-40 is mostly what was in place at the end of the 2014 474 course. Will be updated as we go along.
  • Read the email I sent before the term began.
  • Unless I specify otherwise, readings are from
    Automata, Computability, and Complexity
    by Elaine Rich.
  • Read Appendix A: Sections A.1-A.6.
    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/winter2016/macsse474/.
  • You may want to get JFLAP, software
    that lets you draw and execute various kinds of automata.
  • Recommendation: Make note of
    textbook errata file, and reference
    it as you read the textbook.
  • Reading quiz 1 (MSWord, pdf) is due today (yes, Monday)
    at the beginning of class!
    Solution is on Moodle.
  • HW will usually be due on Mondays and Thursdays at 11:55 PM.
  • Turnins: when and where?
    Reading quizzes:
    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.
    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
1

2

Tue Dec 1
  • Read the Course Syllabus/Policies.
  • (optional) 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.
  • 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 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 ε.
  • Sections 3.1-3.2 (pages 21-27) Language recognition, encoding.
    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) by Wednesday at noon. *
    Optional Q&A session Tuesday 10th hour in O-157
    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)
  • For Wednesday: No HW required. But you should at least look at non-required HW 0 (it covers some course background material; tha is why it is not required)
  • 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 Dec 3
  • 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.
  • 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.
  • 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 Dec 4
  • 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.
  • 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. I enhanced several of the slides by addoing shaded boxes that contain some things that I would say in class or write on the board if we did do them in class.
  • Solutionto today's in-class quiz.
2

5

Mon Dec 7
  • 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)
  • hw02-problems
  • 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 Dec 8
  • Section 5.4 (pp 66-79) Non-deterministic FSMs
  
  • Nondeterminism
  • NDFSMs
  • Convert form NDFSM to equivalent DFSM
2

7

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

8

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

9

Mon Dec 14
  • Section 6.1 (pp 127-132) Intro to regular expressions
  • You may want to read Appendix C after class.
  • NDFSM-->DFSM Proof
  • (if time) Regular expression intro
3

10

Tue Dec 15

    
3

11

Thu Dec 17
  • 6.2 (pp 133-146) Kleene's Theorem
  • 6.3-6.4 (pp 147-150) Practical aspects of regular expressions
  • If you have not looked at problems 2 and 3 from HW5, you should do it today, so you have a chance to ask questions.
  • 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 Dec 18
  • 8.1-8.3 (pp 162-169) Regular languages and closure properties
  • HW 5
  • There is no separate HW 5 problem statements document, because none of the HW5 problems are from the textbook
  • Due to the break, you can use a late "day" until 11:55 PM Tuesday, Dec 22. However, I will not guarantee much help from me oe the TAs after Dec 18.
  • On Tuesday, Dec 15 at 7:30 AM, I updated the assignment document in two ways:
    Changed point values for some problems, and clarified what you are expected to do for problems 2 and 3.
  • Exam discussion
  • Kleene's Theorem continued
  • DFSM → Regular Expression
4

13

Mon Jan 4
  • 8.4-8.6 (pp 169-182) Pumping theorem, functions on Regular languages
  
  • DFSM → Regular Expression (continued)
4

14

Tue Jan 5

  
  • If L is regular, then LR is regular.
  • Practical regular expressions (from Appendix O)
4

15

Thu Jan 7
  • 9.1-9.2 (pp 187-195) Algorithms and Decisions
  
  • How many regular languages?
  • Ways of showing a language to be regular.
  • Showing a language to be non-regular
  • Pumping Theorem
4

16

Fri Jan 8
  • Chapter 10 Summary of Regular Languages (1.5 pages)
  • HW 7 Due Friday instead of Thursday to allow you to catch up after the break. I recommend that you do it by Thursday.
    Has been updated for Winter, 2015-16
  • 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 iscussion of it and an example were begun in Session 12, and continued in Session 13.
  • Pumping Theorem examples
  • Decision Procedures related to regular languages.
  
5

17

Mon Jan 11
  • 11.1-11.2 Intro to Context-free languages
  • Pumping Theorem and Closure
  • Regular languages closed under various functions?
5

18

Tue Jan 12
  • 11.3-11.4 Working with CFGs
  
  • Decision Problems about Regular languages.
  • Many in-class exercises.
5

19

Thu Jan 14
  • 11.5 - 11.7.2 Correct grammars, derivations, ambiguity
  • Chapter 7 Regular grammars
  
  • Rewite systems and grammars
  • CFG intro
  • Derivations
  • CFG's to generate some specific languages
  • Regular grammars (Chapter 7)
5

20

Fri Jan 15
  • 11.8 Normal forms
  • 12.1 - 12.2.2 PDA intro
  • HW 9. Due on Friday instead of Thursday since there will be no HW due Monday, and since this assignment is larger than some.
    Has been updated for Winter, 2015-16
  • HW 09 problem statements
  • Working with CFGs
  • Derivation Trees
  • Structure
6

21

Mon Jan 18
  • As you prepare for the exam, write down questions that you have, so you can ask them in today's class
  
  • Answers to your questions about the exam material
6

22

Tue Jan 19
  • Review for exam 2
  
  • 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

Thu Jan 21
  • Sections 12.3-12.4 Equivalence of PDAs and CFGs, Halting
  
  • More on Parse Trees
  • Ambiguity
6

24

Fri Jan 22
  • Normal forms (Chomsky and Greibach) and simplification
  • Pushdown Automata intro
  • PDA examples
7

25

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

Tue Jan 26
  • Section 17.1
  
  • Bottom-up parsing
  • Showing that languages are/are not C-F
  • Pumping Theorem derivation
7

27

Thu Jan 28
  • Sections 17.2-17.4 Turing machine "programming"
  • Pumping Theorem examples
7

28

Fri Jan 29
  • 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

Mon Feb 1
  • 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

Tue Feb 2
  • Chapter 19 Halting - an undecidable problem
  
  • Language recognition vs. function computation
  • Multiple Tapes.
8

31

Thu Feb 4
  • Chapter 20 Decidable and Semidecidable languages
  • Multiple Tracks
  • Multiple Tapes.
8

32

Fri Feb 5

    
  • 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

Mon Feb 8
  • Sections 21.5-21.7 More on (un)decidability questions
  
  • 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

Tue Feb 9
  • Sections 21.4-21.7 More on (un)decidability questions
  
  • 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
    You are welcome to come to an earlier section than your scheduled section; coming to a later section will result in a 5-point penalty.
    Snow is predicted. If you live off-campus, plan to arrive an hour early.
9

35

Thu Feb 11

  
  • HW 15
    Has been updated for Winter, 2015-16 (including problem 7, added on 2/5/2016 and updated 2/10/16). A hint for problem 3c was added 2/10/2016.
  • HW 15 problem statements Did not add problem 7 here, since it is not from the textbook.
  • Halting Problem intro
  • Decidable, SD, and non-SD languages
9

36

Fri Feb 12

    
  • Class canceled due to instructor illness
10

37

Mon Feb 15

  
  • (1/2 class meeting) Decideability and enumerability
10

38

Tue Feb 16
  • Chapter 27 Analysis and Complexity
  • Sections 28.1-28.3 P and NP
  
  • Overview of reduction.
  • Use reduction to show another language is undecidable
10

39

Thu Feb 18
  • NOT REQUIRED to be turned in, but practice for the final exam.
  • HW 17
    Has been updated for Winter, 2015-16
  • Reduction and more Undecidability proofs
  • Reductions with a twist
10

40

Fri Feb 19

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

41

Mon Feb 22
  • Re-read sections from the book that you did not get the first time.
  • Do lots of problems
  • Final exam Thursday at 8:00 AM in the GM room.
  • Question and Answer session: Wednesday 3:30 in G313.
    Students will set the agenda based on questions that you ask.
    I will try to moderate as the students who are present to solve the problems together.
  • Because the GM room has an unusual layout, I will probably assign seats for this exam.
    Watch for the assignment in your email. Or it may be on the screen when you arrive.
  • 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.
  • In addition to a provided definition and formula" sheet provided at the exam, I will give you a piece of paper in class at Session 29; you can hand-write whatever you want on the front side and bring it to the exam. You may not provide your own paper
    I will also provide the "Turing machine macros reference" handout.
  • 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 15-17, lectures 30-40.
  • That material is about 20% of the course, so it should constitute about 20% of the course exam grade. This translates to about 60% of the final exam.
  • The actual percentage will probably be a little bit less.