Discrete II: Theory of Computation
Fall 2019
 

U.C.F.

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


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

Structure: TR 1630-1745 (4:30PM - 5:45PM), BA1-119; 29 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: TR1400-1530 (2:00PM - 3:30PM)
TA: Stephen Powell, stephenmpowell@knights.ucf.edu
TA Office Hours: MW1500-1630 (3:00PM-4:30PM) in HEC-308
TA: Trevor Bland, tbland96@knights.ucf.edu
TA Office Hours: F1000-1200 (10:00AM-12:00PM) in 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
Youtube Channel: https://www.youtube.com/watch?v=TOsMcgIK95k

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

Quizzes and Assignments:  Around 10.

Exams: Midterm and 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: Midterm -- Thursday, October 17; Withdraw Deadline -- November 1; Final -- Thursday, December 5, 1600-1850 (4:00PM-6:50PM)

Evaluation (Tentative):
Mid Term -- 150 points each
Final Exam -- 200 points
Assignments -- 75 points
Bonus -- 75 points added to the weighting of your better 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/27) -- Notes pp. 2-38 (Chapters 0 and 1 of Sipser); 8/29 is a 7:30 football game, which results in class cancellation; Syllabus
  1. Ground rules
  2. For you to look at as part of a review of discrete math (see Preliminaries)
    1. Sets, sequences, relations and functions
    2. Ordinals, cardinals and infinities
    3. Graphs
    4. Languages
    5. Proof techniques
  3. Sets, sequences, alphabets and languages
  4. Foward passes (little detail but sets context for course)
    1. Set/Language recognizers and generators
    2. Basic notions of automata theory, formal languages, computability and complexity
    3. Brief introduction to Chomsky Hierarchy (sets context for much of course)
  5. Determinitic Finite (State) Automaton (DFA): what and why?
    Sequential circuits: Checkers for odd parity , 2's complement , 3 mod 5 ; pattern matchers: password checker, vending machine; lexical analyzers; simple game/simulation behaviors: stationary sentinel.
  6. 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)

Assignment #1

It is a survey that is online in webcourses. It will be graded, but that's five free points if you complete it on time (11:59PM Friday, 8/30).

Due: One Minute before Midnight Friday, 8/30

Assignment #2

See page 34 of Notes
For a starter, see page 33 of Notes and look carefully at hint
Due: Wednesday, 9/11 at 11:59PM (Key)


Week#2: (9/3, 9/5) -- Hurricane Dorian



Week#3: (9/10, 9/12) -- Notes pp. 39-73 (Chapter 1 of Sipser)
  1. Closure Properties (Complement, Union, Intersection, Difference, Exclusive Union)
  2. Discussions about non-determinism versus determinism
  3. Non-deterministic Finite State Auomaton (NFA)
  4. Non-determinism (NFA)
    Closure under concatenation, Kleene *
    Choosing the right model for various closure properties
    Formal definition and examples
  5. The epsilon (lambda) closure of a set of states
  6. Equivalence of DFAs and NFAs (subset of all states construction)
  7. Regular Expressions (closure of primitive sets under union, concatenation and star)
  8. Every language defined by a Regular Expression is accepted by an NFA
  9. Every language accepted by a DFA is defined by a Regular Expression
    1. Approach#1:  Rij(k) construction from DFA or NFA
    2. Approach#2: State Ripping similar to text Generalized NFA (GNFA)
    3. Approach#3: Languages defined by Regular Equations (not in text) and NFAs without lambda transitions (see  RegularEquations)
  10. Some hand-written notes for this week

Assignment #3

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

Due: Tuesday 9/17 by 11:59PM (Key)



Week#4: (9/17, 9/19) -- Notes pp. 74-117 (Chapter 1 of Sipser); Samples
  1. Continuation of Regular Equations
  2. Existence of minimal state machine for any Regular Language
  3. Minimizing the states of a DFA (compatible vs incompatible, aka indistinguishable vs distinguishable states)
  4. Minimization example using notion of incompatible/distinguishable states
  5. Right model for closure of Regular Languages under Intersection, Complement, and Reversal
  6. Closure of Regular Languages under Substitution, Homomorphism, and Quotient
  7. Meta approach to closure based on Substitution within Class and Intersection with Regular
  8. Closure of Regular Languages under Prefix, Postfix, Substring
  9. Classic non-regular languages {0n1n | n is greater than or equal to 0}
  10. Pumping Lemma for Regular Languages
  11. Proofs that certain languages are not regular using Pumping Lemma
  12. Right-invariant equivalence relationships and Myhill-Nerode Theorem
  13. Proofs that certain languages are not regular using Myhill-Nerode Theorem
  14. More proofs that certain languages are not regular using Pumping Lemma and Myhill-Nerode
  15. Some hand-written notes for this week
  16. Assignment #4

    See page 96-97 of Notes
    Sample assignment with no answers
    Sample assignment with answers

    Due: Tuesday 9/24 by 11:59PM (Key)


Week#5: (9/24, 9/26) - Notes pp. 119-142 (Chapter 1 and a bit of Chapter 2 of Sipser); Samples
  1. Reachable states from some given state
  2. Reaching states to some given state
  3. Min and Max closure of Regular Languages
  4. Transducers (automata with output); Mealy and Moore Models
  5. Decision and closure properties of regular languages
  6. Summary of results to-date on regular languages
  7. Basic notion of grammars and languages generated by grammars
  8. Chomsky hierarchy (Type 3 through Type 0 grammars and languages) -- see page 20 of Notes
  9. Notions of derivation and the language generated by a grammar
  10. Regular (right linear, Type 3) grammars
  11. Every language generated by a regular grammar is regular
  12. Every regular language is generated by a type 3 grammar
  13. The right and left linear grammars generate equivalent classes of languages
  14. Can extend regular grammars to include strings rather than single characters
  15. Grammars and closure properties (union, concatenation, Kleene *)
  16. Context free grammars and context free languages
  17. Sample grammars: {a^n b^n}; {w w(reversed)}; {w | #a(w) = #b(w)}
  18. Derivations (leftmost/rightmost)
  19. Parsing (parse trees; top down/bottom up)
  20. Parsing problems (left recursion bad for top-down; right recusion bad for bottom-up)
  21. DCFLs (unambiguous CFLs) versus DCFGs (unambiguous CFGs)
  22. Notion of ambiguity (inherent versus due to a specific grammar)
  23. Definition of ambiguity -- some string leads to two or more
    1. Parse trees
    2. Leftmost derivations
    3. Rightmost derivations
  24. Some handwritten notes for this week

    Assignment #5

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

    Due: Tuesday 10/1 by 11:59PM (Key)


Week#6: (10/1, 10/3) --  Notes pp. 143-191 ; Chapter 2 of Sipser
  1. 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
  2. Removing left or right recursion to accommodate top-down or bottom-up
  3. Examples of syntax directed parsing
  4. Chomsky Normal Form (CNF)
  5. Chomsky Normal Form (CNF) and the algorithm to convert a CFG to a CNF
  6. Eliminate lambda rules and accommodate for nullable non-terminals
  7. Eliminate unit rules (chains of non-terminals)
  8. Eliminate non-productive non-terminals (no terminal string can be generated from them)
  9. Eliminate unreachable non-terminals (cannot get to them from S)
  10. On rhs's of length >1, replace each terminal with symbol that derives it directly
  11. Recursively change rhs of length k, k>2, to two rules, one with rhs of length 2 and the other of length k-1
  12. Cocke-Kasami-Younger (CKY) polynomial time CFG parser
  13. Constructive proof of Pumping Lemma for CFLs
  14. Non-CFLs {a^n b^n c^n }, {ww | w is a string over Sigma* }
  15. Closure properties for CFLs (intersection with regular, substitution)
  16. Max and Min non-closure
  17. Using substitution and intersection with regular to get many more,
    e.g., prefix, suffix , substring and quotient with regularNon-determinism in PDAs
  18. Non-closure (intersection and complement)
    1. Intersection of {a^n b^n c^m} and {a^m b^n c^n}
    2. Complement
  19. Complement of {ww | w is a string over Sigma* } is a CFL
  20. Solvable Decision Problems about CFLs and CFGs
  21. Solvable Decision Problems for CFL, L
    1. Is w in L?
    2. Is L empty (non-empty)?
    3. Is L finite (infinite)?
  22. Closure Review Sheet (Key)
  23. This ends the material for Midterm
  24. Midterm Topics pp. 186-191 in Notes
  25. Some handwritten notes for this week

    Assignment #6

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

    Due: Tuesday 10/8 by 11:59 PM (Key)

    Assignment #7

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

    Due: Thursday 10/10 by 11:59 PM (Key)


Week#7: (10/8, 10/10) -- Notes pp. 192-201; Chapter 2 of Sipser 
  1. Pushdown automata (PDA) non-determinstic vs deterministic
  2. Notion of instantaneous description (ID)
  3. 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
  4. Shorthand notation for PDA
  5. Example PDAs
  6. Top down parsing of a CFL by PDA
  7. Bottom up parsing of CFL by PDA
  8. Using just pop and push operations in a PDA
  9. Converting PDA to CFG
  10. Example to show PDA language is a CFL by two different methods
  11. Closure Review Sheet (Key)
  12. Midterm Topics pp. 186-191 in Notes
  13. Sample Midterm (key)  -- Complete this for discussion on 10/15
  14. Midterm1 (key) and Midterm2 (key) from Last Year
  15. Sample Pumping Lemma Proof
  16. Some handwritten notes for this week


Week#8: (10/15, 10/17) -- 10/15 In-Class Review; 10/17 (Midterm); Notes pp. 186-191;
  1. In Class Review Session on Tuesday, 10/15
  2. Some Handwritten Notes on Midterm1 Review
  3. MidTerm on Thursday, 10/17
  4. Note: 11/1 is the Withdraw Deadline


Week#9: (10/22, 10/24) -- Notes pp. 209-251 (some is just for your reading); Chapter 2 of Sipser

  1. Solved/Unsolved, Solvable/Unsolvable, Enumerable (semi-decidable)/Non-Enumerable
  2. Hilbert 10th
  3. Cantor and diagonalization -- countable versus uncountable
  4. Countability of machines/programs in any model of computation
  5. Counting argument that there are undecidable problems
  6. Halting Problem defined
  7. Notations for convergence and non-convergence
  8. Halting Problem -- undecidabibility using diagolization
  9. Turing Machines and Variants of Turing Machines
  10. Turing Machines as enumerators/recognizers
  11. Register Machines
  12. A bit about how Register Machines can simulate Turing Machines
  13. Factor Replacement Systems (FRS) as simple models of computation
  14. The necessity of order with FRSs
  15. A bit about how FRS can simulate Register Machines
  16. Discussion of determinism versus non-determinism in models of computation
  17. Some handwritten notes for this week

Week#10: (10/29, 10/31) -- Notes pp. 252-315; Chapters 4, 5 of Sipser
  1. Notions of Instantaneous Descriptor for Register machines and FRSs
  2. Primitive (incomplete) and mu recursive (complete) functions
  3. Pairing Functions
  4. Ackermann's Function and Union/Find
  5. Numbering machines
  6. Universal Machine
  7. The Halting Problem -- classic undecidable but recognizable (semi-decidable, enumerable) problem
  8. Diagonalization proof for Halting Problem
  9. Set of Procedures can be enumerated by a 1-1 onto function
  10. Halt is semi-decidable
  11. The set of algorithms (TOTAL) is non-re
  12. Diagonalization proof for non-re nature of set of algorithms
  13. Enumeration Theorem (enumeration of RE sets)
  14. Reducibility as a technique to show undecidability
  15. Reducibility as a technique to show non-re-ness
  16. Reducing Halt to TOTAL
  17. Using reducibility to show properties of HasZero= { f | for some x, f(x) = 0 }
  18. Using reducibility to show properties of Zero = { f | for all x, f(x) =0 }
  19. RE sets and their complex hierarchy
  20. Many-one reducibility and equivalence
  21. Notion of (many-one) re-complete sets (HALT is one such set)
  22. One-one reducibility and one-one degrees
  23. Turing reducibility and Turing degrees
  24. Notion of RE Completeness
  25. Midterm Exam Key
  26. Some Handwritten Notes
  27. Note that Friday, November 1 is last day to withdraw


Week#11: (11/5, 11/7) -- Notes pp. 316-345; Chapters 4, 5 of Sipser
  1. Showing K0 = HALT is re-complete (in RE and as hard as any other RE problem)
  2. The set K is also re-complete
  3. HasZero is also re-complete (in RE and HALT reduces to it)
  4. Rice's Theorem (weak and strong forms)
  5. Proofs of Rice's Theorem (textual and visual)
  6. Applying Rice's
  7. Examples of applying Rice's Theorem (all three forms)
  8. STP predicate (STP(f,x,t) iff f(x) converges in t steps or fewer)
  9. VALUE(f,x,t) = f(x) if STP(f,x,t), else 0
  10. Note that STP and VALUE are actually primitive recursive
  11. Finally, proof that re and semi-decidable are same
  12. If S and its complement are RE, then S is decidable
  13. Quantification as a tool to identify upper bound complexity
  14. Picture of relationships of REC, RE, RE-Complete, Co-RE, non-RE/non-co-RE, non-Recursive
  15. Some handwritten notes for this week

    Assignment #8

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

    Due: 11/14 by 11:59PM (Key)



Week#12: (11/12, 11/14) -- Notes pp. 346-375; Chapters 4, 5 of Sipser 
  1. Quantification as a tool to identify upper bound complexity
  2. Picture of relationships of REC, RE, RE-Complete, Co-RE, non-RE/non-co-RE, non-Recursive
  3. Operations on pairs of sets, e.g., intersection of a non-empty recursive and an re set
  4. Semi-Thue Systems
  5. Simulating Turing Machines
  6. Grammars and RE Sets
  7. Post Correspondence Problem (PCP)
  8. Semi-Thue Word Problem and PCP
  9. Applications of PCP to Undecidability of Ambiguity of CFLs and Non-emptiness of Intersection of CFLs
  10. 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
  11. 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 if there is an n such that L = Ln
  12. 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
  13. Some handwritten notes for this week

Assignment #9

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

Due: 11/21 by 11:59 PM (Key)


Week#13:  (11/19, 11/21) --  Notes pp. 376-441More on  Chapters 5  and 6 of Sipser 
  1. Introduction to Complexity Theory
  2. Verifiers versus solvers
  3. NP as verifiable in deterministic polynomial time
  4. P as solvable in deterministic polynomial time
  5. NP as solvable in non-deterministic polynomial time
  6. Million dollar question: P = NP ?
  7. Some NP problems that do not appear to be in P: SubsetSum, Partition
  8. Concepts of NP-Complete and NP-Hard
  9. Canonical NP-Complete problem: SAT (Satisfiability)
  10. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
  11. SAT reduction to 3SAT
  12. 3SAT as a second NP-Complete problem
  13. 3SAT reduction to SubsetSum reduction
  14. SubsetSum equivalence (within a polynomial factor) to Partition
  15. 3SAT reduction to 0-1 Integer Linear Programming
  16. Vertex Cover
  17. Independent Set
  18. K-Color
  19. Some handwritten written notes for this week

    Assignment #10

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


    Due: 11/29 by 11:59PM (Key)



Week#14: (11/26) -- Notes pp. 436-457  Final Exam Reviews (Tuesday, 11/26, and Tuesday, 12/3)

  1. More on K-Color
  2. Register Allocation
  3. Scheduling on multiprocessor systems
  4. Catch up on any missing material
  5. Go over SumSome = { f | range of f has three distinct values, x,y,z where z=x+y}
  6. Go over above with quantification, reduction and Rice's
  7. Go over Finite Range = { f | range of f is finite }
  8. Go over above with quantification, reduction and Rice's
  9. Some handwritten notes for this week
  10. Go over problems on Final Review
  11. Questions from Notes pp. 341-344
  12. Final Exam Topics (Notes pp. 452-457)


Week#15:  (12/3) Notes pp. 452-457 Final Exam Reviews (Tuesday, 11/26, and Tuesday, 12/3)

  1. Final Exam Topics (Notes pp. 452-457)
  2. Final Exam Sample without key
  3. Final Exam Review with Sample Exam Key
  4. Final Review
  5. Following material will not be on exam and not even be discussed (See Supplemental)
    1. Details of Equivalence of Computational Models
    2. Hamiltonian Circuit
    3. Traveling Salesman
    4. Tiling (undecidable in plane; NP-Complete in polynomial size limited plane)

Review Sessions: This week and last week

Final Exam; Thursday, December 5, 1600 - 1850 (4:00PM - 6:50PM); BA1-119




UCF Last Updated December 3, 2019