Discrete II: Theory of Computation
Fall 2017
 

U.C.F.

Charles E. Hughes
Department of Computer Science
University of Central Florida


email: charles.e.hughes@knights.ucf.edu 

Structure: TR 1330-1445 (1:30PM - 2:45PM), CB2-105; 30 class periods, each 75 minutes long.
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Instructor: Charles Hughes; Harris Engineering Center 247C; 823-2762
Office Hours: TR1515-1630 (3:15PM - 4:30PM)
GTA: Anthony Wehrer (awehrer@knights.ucf.edu)
Office Hours: W 3:00PM-4:15PM; F 4:00PM-5:15PM; HEC-308
Text: Sipser, Introduction to the Theory of Computation 2nd/3rd Ed., Cengage Learning, 2005/2013+Notes
Secondary References: Hopcroft, Motwani and Ullman, Introduction to Automata Theory, Languages and Computation 3rd Ed., Prentice Hall, 2006.
Prerequisites: COT 3100; COP3503

Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot4210/Fall2017
Notes URL: http://www.cs.ucf.edu/courses/cot4210/Fall2017/Notes/COT4210Notes.pdf

Quizzes and Assignments: 10 or so.

Exams: 2 midterms and a final.

Material: I will draw heavily from Chapters 0-7 of Sipser. Some material will also come from Hopcroft et al.. You are responsible for material discussed in notes and in in-class discussions. Not all of this is addressed in either of these texts. I highly recommend attending class, interacting with me and listening very carefully when I say a topic is important to me; hint, hint about exam questions ;-)

Important Dates: Exam#1 -- Tentatively September 28; Withdraw Deadline -- October 30; Exam#2 -- Tentatively November 2; Final -- Tuesday, December 5, 1300-1550 (1:00PM-3:50PM)

Evaluation (Tentative):
Mid Terms -- 100 points each
Final Exam -- 175 points
Quizzes and Assignments -- 75 points
Bonus -- 50 points added to your best exam
Total Available: 500
Grading will be A ≥ 90%,A- ≥ 88%,B+ ≥ 85%,B ≥ 80%, B- ≥78%,C+ ≥ 75%,C ≥ 70%,C- ≥ 60%,D ≥ 50%,F < 50%


Weeks#1: (8/22, 8/24) -- Notes pp. 2-66 (Chapters 0 and 1 of Sipser); Syllabus
  1. Ground rules
  2. Sets, sequences, relations and functions (review)
  3. Ordinals, cardinals and infinities
  4. Graphs
  5. Languages
  6. Set/Language recognizers and generators
  7. Introduction to computability: historical and motivation perspective
  8. Basic notions of automata theory, formal languages, computability and complexity
  9. Brief introduction to Chomsky Hierarchy (sets context for much of course)
  10. Proof techniques
  11. Some history of the genesis of the theory of computation (Hilbert, Godel, Turing, Post, Kleene)
  12. Complexity theory: basic goals; big question is P=NP?
  13. Discussions about non-determinism versus determinism
  14. Formal definition of a Determinitic Finite (State) Automaton (DFA)
    A = (Finite State Set, Finite Input Alphabet, Transition Function, Start State, Final States), 
      where transtion function maps (Current State, Current Input Symbol) to Next State
    Can represent Transition Function by State Transition Table or State Transtion Diagram (preferred)
  15. Determinitic Finite (State) Automaton (DFA): what and why?
    Sequential circuits; pattern matchers; lexical analyzers; simple game/simulation behaviors
    Formal definition and examples
    State transition diagrams versus state transition tables
  16. Non-deterministic Finite State Auomaton (NFA)
  17. Some hand-written notes for this week

Assignment #1

See page 13 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: Midnight Friday, 8/25 (Key)

Assignment #2

See page 44 of Notes
Sample assignment with no answers
Sample assignment with answers
Due: Thursday, 8/31 at 1:30PM (Key)

Week#2: (8/27, FOOTBALL) -- Notes pp. 67-83 (Chapter 1 of Sipser)
  1. DFA closure (complement, union, intersection, difference, exclusive or)
  2. Non-determinism (NFA)
    Closure under concatenation, Kleene *
    Formal definition and examples
  3. The epsilon (lambda) closure of a set of states
  4. Equivalence of DFAs and NFAs (subset of all states construction)
  5. A little lost time for my being in lockdown :)
  6. Some hand-written notes for this week

Assignment #3

See page 83 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: 9/21 by 1:30PM (Key)

 


Week#3: (9/5, Irma #1) -- Notes pp. 84-103 (Chapter 1 of Sipser); Samples
  1. Regular Expressions (closure of primitive sets under union, concatenation and star)
  2. Every language defined by a Regular Expression is accepted by an NFA
  3. Every language accepted by a DFA is defined by a Regular Expression (ripping states out)
  4. Approach#1:  Rij(k) construction from DFA or NFA
  5. Approach #2: State Ripping similar to text Generalized NFA (GNFA)
  6. Approach#3: Languages defined by Regular Equations (not in text) and NFAs without lambda transitions
  7. Some handwritten notes for this week


Week#4: (Irma #2, Irma#3) -
  1. Stay safe
  2. Clean up Irma's mess


Week#5: (9/19, 9/21) --  Notes pp. 104-145 (Chapter 1 of Sipser); Samples
  1. Right-invariant equivalence relationships and Myhill-Nerode Theorem
  2. Existence of minimal state machine for any Regular Language
  3. Minimizing the states of a DFA (indistinguishable vs distinguishable states)
  4. Minimization example using notion of distinguishable states
  5. Additional minimization example using notion of distinguishable states
  6. Decidable Properties -- membership, emptiness, everything, finiteness, equivalence
  7. Right model for closure of Regular Languages under Intersection, Complement, and Reversal
  8. Closure of Regular Languages under Substitution, Homomorphism, and Quotient
  9. Meta approach to closure based on Substitution within Class and Intersection with Regular
  10. Closure of Regular Languages under Prefix, Postfix, Substring
  11. Reachable states from some given state
  12. Reaching states to some given state
  13. Min and Max
  14. Classic non-regular languages {0n1n | n is greater than or equal to 0}
  15. Pumping Lemma for Regular Languages
  16. Proofs that certain languages are not regular using Pumping Lemma
  17. Proofs that certain languages are not regular using Myhill-Nerode Theorem
  18. Classic non-regular languages {0n1n | n is greater than or equal to 0}
  19. Pumping Lemma for Regular Languages
  20. Proofs that certain languages are not regular using Pumping Lemma
  21. Proofs that certain languages are not regular using Myhill-Nerode Theorem
  22. More proofs that certain languages are not regular using Pumping Lemma and Myhill-Nerode
  23. Transducers (automata with output); Mealy and Moore Models
  24. End of Exam#1 Material
  25. Some handwritten notes for this week
  26. Exam#1 Topics pp. 140-145 in Notes
  27. Prior Exam#1  -- Complete this for discussion on 9/26 (key)
  28. Another Prior Exam#1 -- Complete this for discussion on 9/26 (key)
  29. Review 9/27, 3:00PM-5:00PM, HEC-101A

Assignment #4 

See page 114-115 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: 9/26 by 1:30PM (Key)

Assignment #5

See page 136 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: 9/28 by 1:30PM (Key)


Week#6: (9/26, 9/28) -- Notes pp. 145-171,187-192; Chapter 2 of Sipser;
Review 9/27, 3:00PM-5:00PM, HEC-101A
  1. Post, Thue rewriting systems
  2. Basic notion of grammars and languages generated by grammars
  3. Chomsky hierarchy (Type 3 through Type 0 grammars and languages) -- see page 36 of Notes
  4. Notions of derivation and the language generated by a grammar
  5. Regular (right linear, Type 3) grammars
  6. Every language generated by a regular grammar is regular
  7. Every regular language is generated by a type 3 grammar
  8. The right and left linear grammars generate equivalent classes of languages
  9. Can extend regular grammars to include strings rather than single characters
  10. Grammars and closure properties (union, concatenation, Kleene *)
  11. Context free grammars and context free languages
  12. Sample grammars: {a^n b^n}; {w w(reversed)}; {w | #a(w) = #b(w)}
  13. Derivations (leftmost/rightmost)
  14. Parsing (parse trees; top down/bottom up)
  15. Notion of ambiguity (inherent versus due to a specific grammar)
  16. Definition of ambiguity -- some string leads to two or more
    1. Parse trees
    2. Leftmost derivations
    3. Rightmost derivations
  17. Parsing problems (left recursion bad for top-down; right recusion bad for bottom-up)
  18. DCFLs (unambiguous CFLs) versus DCFGs (unambiguous CFGs)
  19. LR(k) languages versus grammars; LL(k) languages versus grammars
    1. LR(1) languages = DCFLs; LR(k) grammars properly contained in DCFGs
    2. LL(k) languages properly contained in LL(k+1) languages
    3. LL(k) grammars properly contained in DCFGs
    4. In the limit as k goes to infinity LL(k) languages = DCFLs
  20. Removing left or right recursion to accommodate top-down or bottom-up
  21. Chomsky Normal Form (CNF)
  22. Cocke-Kasami-Younger (CKY) polynomial time CFG parser
  23. Some handwritten notes for this week
  24. More Handwritten Notes
  25. Even More Handwritten Notes

Assignment #6

See page 192 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: 10/19 by 1:30PM (Key) Comments


Week#7: Notes pp. 140-144, 10/3 (Chapter 1 of Sipser, review), 10/5 (Midterm1) 
  1. Exam#1 Topics pp. 140-144 in Notes
  2. Review and go over sample questions
  3. MidTerm 1  (Chapter 1; Notes pp. 1-145; Assignments 1-5)


Week#8: (10/10, 10/12) -- Notes pp. 172-186,193-212; Chapter 2 of Sipser
  1. Chomsky Normal Form (CNF) and the algorithm to convert a CFG to a CNF
    1. Eliminate lambda rules and accommodate for nullable non-terminals
    2. Eliminate unit rules (chains of non-terminals)
    3. Eliminate non-productive non-terminals (no terminal string can be generated from them)
    4. Eliminate unreachable non-terminals (cannot get to them from S)
    5. On rhs's of length >1, replace each terminal with symbol that derives it directly
    6. Recursively change rhs of length k, k>2, to two rules, one with rhs of length 2 and the other of length k-1
  2. Pumping Lemma for CFLs
  3. Constructive proof of Pumping Lemma for CFLs
  4. Non-CFLs {a^n b^n c^n }, {ww | w is a string over Sigma* }
  5. Closure properties for CFLs (intersection with regular, substitution)
  6. Non-closure (intersection and complement)
    1. Intersection of {a^n b^n c^m} and {a^m b^n c^n}
    2. Complement
  7. Complement of {ww | w is a string over Sigma* } is a CFL
  8. Solvable Decision Problems about CFLs and CFGs
  9. Solvable Decision Problems for CFL, L
    1. Is w in L?
    2. Is L empty (non-empty)?
    3. Is L finite (infinite)?
  10. Pushdown automata (PDA) non-determinstic vs deterministic
  11. Notion of instantaneous description (ID)
  12. Equivalence of a variety of PDA formalizations
    1. Bottom of stack marker versus none at start
    2. Ability to push none or one, versus many characters on stack
    3. Recognition by accepting state, by empty stack and by both
    4. Chomsky Normal Form (CNF) and the algorithm to convert a CFG to a CNF
  13. Shorthand notation for PDA
  14. Some handwritten Notes for Week 8 and start of Week 9.


Week#9: (10/17, 10/19) -- Notes pp. 213-241; Chapter 2 of Sipser

  1. Examples PDAs
  2. Top down parsing of a CFL by PDA
  3. Bottom up parsing of CFL by PDA
  4. Using just pop and push operations in a PDA
  5. Converting PDA to CFG
  6. Example to show PDA language is a CFL by two different methods
  7. Greiback Normal Form (GNF) and linear parsing (with great guessing)
  8. Max and Min non-closure
  9. Using substitution and intersection with regular to get many more,
    e.g., prefix, suffix , substring and quotient with regularNon-determinism in PDAs
  10. Some handwritten notes for this week
  11. Context Sensitive Grammars (CSG) and Languages (CSL)
  12. Phrase Structured Grammars (CSG) and Languagess (re)
  13. This ends the material for Exam#2 (Page 225 of Notes)
  14. Midterm Exam#1 Key
  15. Solved/Unsolved, Solvable/Unsolvable, Enumerable (semi-decidable)/Non-Enumerable
  16. Hilbert 10th
  17. Cantor and diagonalization -- countable versus uncountable
  18. Countability of machines/programs in any model of computation
  19. Counting argument that there are undecidable problems
  20. Halting Problem defined
  21. Notations for convergence and non-convergence
  22. Halting Problem -- undecidabibility using diagolization
  23. Turing Machines and Variants of Turing Machines
  24. Some handwritten notes for this week

Assignment #7

See page 220 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: 10/26 by 1:30PM (Key)


Week#10: (10/24, 10/26) -- Notes pp. 242-315; Chapter 3 of Sipser
  1. Turing Machines as enumerators/recognizers
  2. Register Machines
  3. Factor Replacement Systems (FRS) as simple models of computation
  4. The necessity of order with FRSs
  5. Discussion of determinism versus non-determinism in models of computation
  6. Primitive (incomplete) and mu recursive (complete) functions
  7. Numbering machines
  8. Universal Machine
  9. The Halting Problem -- classic undecidable but recognizable (semi-decidable, enumerable) problem
  10. Diagonalization proof for Halting Problem
  11. Set of Procedures can be enumerated by a 1-1 onto function
  12. Halt is semi-decidable
  13. The set of algorithms (TOTAL) is non-re
  14. Diagonalization proof for non-re nature of set of algorithms
  15. Enumeration Theorem (enumeration of RE sets)
  16. Exam#2 Topics pp. 223-225 in Notes
  17. Last Semester's Exam#2  -- Complete this for discussion on 10/31 (key)
  18. Another Sample Exam#2 -- Complete this for discussion on 10/31 (key)
  19. Some handwritten notes for this week


Week#11: (10/30, 10/31, 11/2) -- Notes pp. 223-225; 10/30 Help Session in HEC-101A from 11:00AM to 1:00PM on Monday;10/31 In-Class Help Session; 11/2 (Midterm2)
  1. Help Session on Monday, 10/30,  HEC-101A; from 11:00AM-1:00PM
  2. In Class Review Session on Tuesday
  3. Closure Review Sheet (Key)
  4. MidTerm 2 on Thursday, 11/2


Week#12: (11/7, 11/9) -- Notes pp. 311-368; Chapters 4, 5 of Sipser 
  1. Note: 11/6 is the Withdraw Deadline
  2. Reducibility as a technique to show undecidability
  3. Reducibility as a technique to show non-re-ness
  4. Reducing Halt to TOTAL
  5. Using reducibility to show properties of HasZero= { f | for some x, f(x) = 0 }
  6. Using reducibility to show properties of Zero = { f | for all x, f(x) =0 }
  7. RE sets and their complex hierarchy
  8. Many-one reducibility and equivalence
  9. Notion of (many-one) re-complete sets (HALT is one such set)
  10. One-one reducibility and one-one degrees
  11. Turing reducibility and Turing degrees
  12. Notion of RE Completeness
  13. Showing K0 = HALT is RE Complete (in RE and as hard as any other RE problem)
  14. The sets K is RE-complete
  15. Showing HasZero is RE Complete (in RE and HALT reduces to it)
  16. Some handwritten notes for this week
  17. Rice's Theorem (weak and strong forms)
  18. Proofs of Rice's Theorem (textual and visual)
  19. Applying Rice's
  20. Examples of applying Rice's Theorem (all three forms)
  21. STP predicate (STP(f,x,t) iff f(x) converges in t steps or fewer)
  22. VALUE(f,x,t) = f(x) if STP(f,x,t), else 0
  23. Note that STP and VALUE are actually primitive recursive
  24. Quantification as a tool to identify upper bound complexity
  25. Finally, proof that re and semi-decidable are same
  26. If S and its complement are RE, then S is decidable
  27. Picture of relationships of REC, RE, RE Complete, Co-RE, non-RE/non-co-RE, non-Recursive
  28. Post Correspondence Problem (PCP)
  29. Some more handwritten notes for this week

Assignment #8

See page 350 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: 11/20 by 12:00PM (Key)

Assignment #9

See page 368 of Notes
Sample assignment with no answers
Sample assignment with answers

Due: 11/28 by 1:30PM (Key)


Week#13:  (11/14, 11/16) --  Notes pp. 369-444 Chapters 5  and 6 of Sipser 
  1. Applications of PCP (Undecidability of Ambiguity of CFLs and Non-emptiness of Intersection of CFLs)
  2. Application of PCP to Undecidability of Non-emptiness of CSLs
    1. This can be done by a CSG that produces strings iff PCP has a solution
    2. It can also be shown by fact that intersection of two CFLs is a CSL
  3. Is L = Sigma* is undecidable (comes from complement of terminating traces being a CFL)?
    1. Is L = L2? undecidable for CFL since can reduce Is L = Sigma*? to Is L = L2?
    2. There is a more complex proof that we cannot decide is there is an n such that L = Ln
  4. More Unsolvable Decision Problems for CFL, L
    1. Is L = L', where L' is some other CFL? Just set L' = Sigma*
    2. Is L intersect L' empty (non-empty); straight from PCP reduction to non-empty intersection
    3. Is L intersect L' finite (infinite); if PCP mapping gets one overlap then there are an infinite number
  5. Introduction to Complexity Theory
  6. Verifiers versus solvers
  7. NP as verifiable in deterministic polynomial time
  8. P as solvable in deterministic polynomial time
  9. NP as solvable in non-deterministic polynomial time
  10. Million dollar question: P = NP ?
  11. Some NP problems that do not appear to be in P: SubsetSum, Partition
  12. Concepts of NP-Complete and NP-Hard
  13. Canonical NP-Complete problem: SAT (Satisfiability)
  14. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
  15. SAT reduction to 3SAT
  16. 3SAT as a second NP-Complete problem
  17. 3SAT reduction to SubsetSum reduction
  18. SubsetSum equivalence (within a polynomial factor) to Partition
  19. 3SAT reduction to 0-1 Integer Linear Programming
  20. Midterm Exam#2 Key



Week#14: (11/21) --  Notes pp. 445-479; Chapter 7 of Sipser; Final Exam Review

  1. Vertex Cover
  2. Independent Set
  3. K-Color
  4. Register Allocation
  5. Scheduling on multiprocessor systems
  6. Questions from Notes pp. 364-367
  7. Sample Final
  8. Final Exam Topics (Notes pp. 474-479)
  9. Some handwritteb notes for this week

    Assignment #10

    See page 445 of Notes
    Sample assignment with no answers
    Sample assignment with answers


    Due: 11/30 by 1:30PM (Key)



Week#15:  (11/28, 11/30) Final Exam Reviews (Tuesday and Thursday at regular room and time)

  1. Closure Review
  2. Closure Review Key
  3. Final Exam Sample without key
  4. Final Exam Review with Sample Exam Key
  5. Second Final Exam Sample without Key
  6. Second Final Exam Sample with Key
  7. Final Review
  8. Additional Help Session on Monday, December 4, HEC-101A, 5:00PM to 7:00PM
  9. Following material will not be on exam and not even be discussed (Notes pp. 480-547)
  10. Details of Equivalence of Computational Models
  11. Hamiltonian Circuit
  12. Travelling Salesman
  13. Tiling (undecidable in plane; NP-Complete in polynomial size limited plane)

Review Sessions: This whole week and  Monday, December 4, HEC-101A, 5:00PM to 7:00PM

Final Exam; Tuesday, December 5, 1300 - 1550 (1:00PM - 3:50PM)



© UCF Last Updated December 2, 2017