MA/CSSE 474 – Theory of Computation

Summer, 2015 (201540) [online] Schedule Overview updated Mon Aug 3 at 3:59:45 PM

Most of the schedule and assignments initially posted here are from a previous term;
   this page will be updated as we proceed through the term.
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 Jun 8
  • Important Summer Note: The "Schedule" part of this page is irrelevant in summer 2015; the actual schedule is on Moodle. This page is provided because it contains links to my PowerPoint slides and other resources that may be useful to you.
  • 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/summer2014/macsse474/.
  • You may want to get JFLAP, software
    that lets you draw and execute various kinds of automata. Not required for the course, but many students have found it to be helpful. JFLAP Tutorial
  • Recommendation: Make note of
    textbook errata file, and reference
    it as you read the textbook.
  • Turnins: when and where?
    Reading quizzes (No submissions in the 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 the due date.
    Electronic submissions only.
    Drop box on Moodle.
    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 Jun 9
  • Read the Course Syllabus/Policies.
  • 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.
  • Post a message to the Introduce Yourself discussion forum on Piazza, and respond to someone else's post.
  • Reading quiz 2 (MSWord, pdf) is due today Not required for summer, but you should do it for your own practice and check your answers
  • By Wednesday, you should at least look at non-required HW 0.
    If any problems seem non-trivial to you, consider doing them soon for practice.
  • Non-required HW 0
  • hw00-problems
  • Placeholder for 201620
  • Roll call
  • Professor and Course introduction, online materials
  • What is ToC?
  • Languages and Strings
  • String concatenation, replication, reverse
  • Detailed induction proof of (wx)R = xRwR
1

3

Thu Jun 11
  • 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.
  
  • Problems from Reading Quiz 1
  • defining Languages
  • Sets and Relations
  • Closure of a set under a relation
1

4

Fri Jun 12
  • 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.
  • Summer:The number in parentheses after each HW number is the number of grace days allowed for that.
    The syllabus contains details of how summer grace days work. .
  • HW 1 (7)
  • hw01-problems
  • 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 Jun 15
  • Sections 5.2-5.3 (pp 60-66) More on Deterministic FSMs
  
  • Formal definition of DFSM
2

6

Tue Jun 16
  • Section 5.4 (pp 66-79) Non-deterministic FSMs
  • Nondeterminism
  • NDFSMs
  • Convert from NDFSM to equivalent DFSM
2

7

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

8

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

9

Mon Jun 22
  • 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 Jun 23

  
  • Summer: No in-class exams. This exam info may help you to see whether you are "on track" in terms of understanding course material.
  • 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
  • You may prepare and use double-sided sheet of paper.
    Feel free to compare your paper with other
    students' papers as you prepare it.
  • No electronic devices or headphones/earbuds
3

11

Thu Jun 25
  • 6.2 (pp 133-146) Kleene's Theorem
  • 6.3-6.4 (pp 147-150) Practical aspects of regular expressions
  • Summer: Last grace day for HW 3 (11:55 PM)
  • Regular Expressions and languages they define
  • Kleene's Theorem
  • Regular expression → NDFSM
3

12

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

13

Mon Jun 29
  • 8.4-8.6 (pp 169-182) Pumping theorem, functions on Regular languages
  • Summer: Last grace day for HW 4 (11:55 PM)
  • Practical regular expressions
  • How many (regular) languages?
  • Closure properties
  • Pumping Theorem intro
  • Note on summer resource mismatch: Last time this course was offered as a regular course, sessions 13-15 were cancelled due to snow. So what was then Session 16 should have been Session 13, etc. I am in the process of moving things to where they should have been, and I will eventually rename the PowerPoint slide documents. For now, the links point to correct things, even though the session numbers are incorrect
  • Slides / PPT
  • Class Notes
4

14

Tue Jun 30
  • 9.1-9.2 (pp 187-195) Algorithms and Decisions
  • Summer: Wednesday is the last grace day for HW 5 (11:55 PM)
  • More Pumping Theorem examples
4

15

Thu Jul 2
  • Chapter 10 Summary of Regular Languages (1.5 pages)
  • HW 6 (5)
  • HW 06 problem statements
  • This is the first substantial assignment.
    It contains many (14) problems,
    the first hard problem (#10),
    and a problem (#14) which, while straightforward,
    is long and somewhat tedious.
  • Because of the difficulty of HW6 and because of the holiday, only one assignment is due this week.
  • HW 06 Survey results Winter 2013-14
  • Using closure properties to prove a language (non-)regular
  • Regular languages closed under various functions?
4

16

Fri Jul 3

    
  • Summer: Break for July 4
  
5

17

Mon Jul 6
  • 11.1-11.2 Intro to Context-free languages
  
  • More Pumping Theorem examples
  • Summer resource mismatch follow-up: (see note on Seesion 13). I have not yet done the "session movement" beyond this point.
  • Slides / PPT
  • Class Notes
5

18

Tue Jul 7
  • 11.3-11.4 Working with CFGs
  • Using Closure properties to prove a language (non-)regular
  • Regular languages closed under various functions?
5

19

Thu Jul 9
  • 11.5 - 11.7.2 Correct grammars, derivations, ambiguity
  
  • Regular language decision problems
  • CFG intro
5

20

Fri Jul 10
  • 11.8 Normal forms
  • Chapter 7 Regular grammars
  • 12.1 - 12.2.2 PDA intro
  • CFG Formal Definition
  • Regular Grammars
  • Working with CFGs
  • Structure
6

21

Mon Jul 20
  • Sections 12.3-12.4 Equivalence of PDAs and CFGs, Halting
    
6

22

Tue Jul 21
  • Review for exam 2 (Not summer!)
  •  
  • Summer:
  • Sections 13.1-13.4 CF and non-CF languages, pumping, closure
  • See this note on Example 13.3
  • Exam 2 in class. (Not summer!)
    Will cover Sections 5.1-5.8, 6.1-6.4, 8.1-8.6, 9.1-9.2 and HW 1-8
  •  
  • Summer:
  • Ambiguity
  • Normal forms (Chomsky-Greibach) and simplification
6

23

Thu Jul 23
  • Chapter 14 CFL Algorithms and Decision Problems
  • 16 (skim these three pages) (Chapter 15 material is covered in the compilers course, CSSE 404)
  
  • Pushdown Automata intro
  • PDA examples
6

24

Fri Jul 24

  
  • Summer: Saturday is the last grace day for HW 9 (11:55 PM)
  • HW 10 (5)
    Summer An extra grace day because of Monday's exam (this assignment is considerably larger and harder than HW9)
  • HW 10 problem statements
  • Nondeterminism in PDAs
  • From a CFG, can produce equivalent PDA
  • Top-down parser
  • Bottom-up parser
7

25

Mon Jul 27

    
  • Summer Midterm exam (through ProctorU)
  • Read this info about ProctorU and sign up for an exam time (it will be free if you sign up at least 72 hours before your exam)
  • Midterm exam specification Summer 2014. Last updated July 18 at 9 AM)
  
7

26

Tue Jul 28
  • Section 17.1
  • Summer: Wednesday is the last grace day for HW 10 (11:55 PM)
  • HW 11 (5)
    Summer An extra grace day because of Monday's exam (Probably the largest assignment of the course)
  • HW 11 problem statements
  • Bottom-up parsing
  • Showing that languages are/are not C-F
  • Pumping Theorem
7

27

Thu Jul 30
  • Sections 17.2-17.4 Turing machine "programming"
  
  • Pumping Theorem examples
  • Misc CFL properties
  • CFL Closure Properties
7

28

Fri Jul 31
  • Sections 17.5-17.7 Alternative TM defs,
    Encoding a TM, the universal TM
  • CFL Decision Problems
  • Turing Machine Intro
8

29

Mon Aug 3
  • Chapter 18 Church-Turing Thesis (what is "computable"?)
  
  • Turing Machine subroutines (Macro langiuage)
  • Acceptance by a TM
  • The sets D and SD
8

30

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

31

Thu Aug 6
  • Chapter 20 Decidable and Semidecidable languages
  
  • Encoding Turing Machines as Strings.
  • Universal Turing Machine.
  • Church-Turing Thesis
8

32

Fri Aug 7
  • Chapter 21.1-21.3 Proofs of decidability and undecidability
  • Halting Problem intro
  • Decidable, SD, and non-SD languages
9

33

Mon Aug 10
  • Sections 21.5-21.7 More on (un)decidability questions
  
  • Enumerability
  • Reduction and Undecidability proofs
9

34

Tue Aug 11
  • Sections 21.4-21.7 More on (un)decidability questions
  • Summer: Last grace day for HW 14 (11:55 PM)
  • HW 15 (3) In summer 2014, instructor will have limited internet access from late Friday morning until sometime Sunday evening. In case you have questions on a problem or two and do not get good enough answers from other students on Piazza, I will try to answer them Sunday evening and allow everyone to submit for full credit until 11:55 PM Monday (Moodle server time).
  • HW 15 problem statements
  • Exam 3 in-class(not summer)
    Will cover Sections 11.1-11.8, 12.1-12.4, 12.6 13.1-13.5, 13.8, 14.1-14.3, 17.1-17.7, 18.1-18.2,19.1-19.3, HW 9-13
9

35

Thu Aug 13

    
  • Undecidability proofs
9

36

Fri Aug 14

  
  • HW 16 (3)
    Summer 2014: Not to be turned in.
    Do these problems as practice for the final exam,
    You can check your answers against the solutions that I will post.
    This is the last assignment that has been updated for Summer, 2014
  • More undecidable languages
  • Reductions with a twist
10

37

Mon Aug 17

  
  • Summer: Last (extended) grace day for HW 15 (11:55 PM)
    For the reasons for the odd time, see the note on Session 32, where HW 15 is assigned.
  • More decidability proofs
  • Rice's Theorem
10

38

Tue Aug 18
  • Chapter 27 Analysis and Complexity
  • Sections 28.1-28.3 P and NP
  
  • Show that some languages are not SD
  • Undecidable properties of CFLs
10

39

Thu Aug 20
  • (Summer 2014)Final Exam
  • Begin the exam Today, August 14 between midnight and 9 PM EDT.
  • Sign up for a time on ProctorU.com (72 hours in advance if you don't want to pay for it)
  • Rules same as last time, except:
    • you can bring one single-sided handwritten sheet of notes.
    • You will have 2.5 hours for the exam (will not begin until after ProctorU preliminaries)
    • You can take one or two breaks during the exam. It will consist of three different Moodle quizzes, and you can take breaks between them.
    • As before, you can submit each part multiple times if necessary. But you must do them in order, and once you have seen part j+1 you may not redo part j (this allows for "spoilers" in later parts).
  • Final exam specification Summer 2014.
    Last updated August 11 at 6 AM (corrected the exam date).
  • A quick overview of Computational Complexity, P, and NP.
10

40

Fri Aug 21

  
  • Practice problems
11

41

Mon Aug 24
  • Re-read sections from the book that you did not get the first time.
  • Do lots of problems
  • Add to your "bring to the exam" sheets some details that you understand but might not remember.
  
  • Final exam Wednesday at 8:00 AM.
  • You can bring 4 sheets of paper plus the "Turing machine macros referncce" handout.
  • Last Name A-M: G315, O-Y G317.