---

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

---

Structure: TR 1030-1145 (10:30AM - 11:45AM), HPA1-116; 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: TR1315-1500 (1:15PM - 3:00PM)
GTA: Sina Lotfian; Harris Engineering Center 234, Desk 1; slotfian@knights.ucf.edu
Office Hours: WF 4:00PM - 6:00PM
Image of Sina so you recognize him
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/Spring2017
Notes URL: http://www.cs.ucf.edu/courses/cot4210/Spring2017/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 February 16; Withdraw Deadline -- March 22; Exam#2 -- Tentatively March 30; Final -- Tuesday, May 2, 1000-1250 (10:00AM-12: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%

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. Some hand-written notes for this week
    

Assignment #1

See page 13 of Notes
Sample assignment with answers

Due: Midnight Friday, 1/13 (Key)

Assignment #2

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

Due: Thursday, 1/19 at 10:30AM (Key)

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: 1/26 by 10:30AM (Key)

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. Right-invariant equivalence relationships and Myhill-Nerode Theorem
8. Existence of minimal state machine for any Regular Language
9. Minimizing the states of a DFA (indistinguishable vs distinguishable states)
10. Minimization example using notion of distinguishable states
11. Some handwritten notes for this week
    

Assignment #4 

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

Due: 2/6 by 11:59PM (Key)

1. Additional minimization example using notion of distinguishable states
2. Right model for closure of Regular Languages under Intersection, Complement, and Reversal
3. Closure of Regular Languages under Substitution, Homomorphism, and Quotient
4. Meta approach to closure based on Substitution and Intersection
5. Closure of Regular Languages under Prefix, Postfix, Substring
6. Classic non-regular languages {0ⁿ1ⁿ | n is greater than or equal to 0}
7. Pumping Lemma for Regular Languages
8. Proofs that certain languages are not regular using Pumping Lemma
9. Proofs that certain languages are not regular using Myhill-Nerode Theorem
10. More proofs that certain languages are not regular using Pumping Lemma and Myhill-Nerode
11. Transducers (automata with output); Mealy and Moore Models
12. Post, Thue rewriting systems
13. Basic notion of grammars and languages generated by grammars
14. Chomsky hierarchy (Type 3 through Type 0 grammars and languages) -- see page 36 of Notes
15. Notions of derivation and the language generated by a grammar
16. Regular (right linear, Type 3) grammars
17. Every language generated by a regular grammar is regular
18. Every regular language is generated by a type 3 grammar

Assignment #5

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

Due: 2/13 by 11:59PM (Key)

1. Every language generated by a regular grammar is regular (Formal prrof)
   
2. Every regular set (language) is generated by a type 3 grammar (Formal proof)
   
3. The right and left linear grammars generate equivalent classes of languages
4. Can extend regular grammars to include strings rather than single characters
5. Decidable Properties -- membership, emptiness, everything, finiteness, equivalence
6. Grammars and closure properties (union, concatenation, Kleene *)
7. Reachable states from some given state
8. Reaching states to some given state
9. Min and Max
10. End of Exam#1 Material
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. Exam#1 Topics pp. 152-156 in Notes
21. Last Semester's Exam#1  -- Complete this for discussion on 2/14 (key)
22. Another Sample Exam#1 -- Complete this for discussion on 2/14 (key)
23. Review in HEC-101C on Friday, February 10 from 6:00PM to 8:00PM.
    

1. Help Session TBD
2. Exam#1 Topics pp. 152-156 in Notes
3. Review and go over sample questions
4. MidTerm 1  (Chapters 0, 1; Notes pp. 1-156; Assignments 1-5)

1. More top-down versus bottom-up
2. Removing left or right recursion to accommodate top-down or bottom-up
3. 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
4. Cocke-Kasami-Younger (CKY) polynomial time CFG parser
5. Pumping Lemma for CFLs
   
6. Some handwritten notes for this week

Assignment #6

See page 187 of Notes

Due: 3/2 by 10:30AM (Key) Comments

1. Constructive proof of Pumping Lemma for CFLs
2. Non-CFLs {a^n b^n c^n }, {ww | w is a string over Sigma* }
3. Pushdown automata (PDA) non-determinstic vs deterministic
4. Notion of instantaneous description (ID)
5. 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
6. Shorthand notation for PDA
7. Non-determinism in PDAs
8. Examples PDAs
9. Top down parsing of a CFL by PDA
10. Bottom up parsing of CFL by PDA
11. Using just pop and push operations in a PDA
12. Converting PDA to CFG
13. Example to show PDA language is a CFL by two different methods
14. Greiback Normal Form (GNF) and linear parsing (with great guessing)
15. Some handwritten notes for this week
16. Midterm Exam#1 Key

Week#9: (3/7, 3/9) -- Notes pp. 213-241; Chapter 2 of Sipser

1. Closure properties for CFLs (intersection with regular, substitution)
2. Using substitution and intersection with regular to get many more,
   e.g., prefix, suffix , substring and quotient with regular
3. Non-closure (intersection and complement)
1. Intersection of {a^n b^n c^m} and {a^m b^n c^n}
2. Complement
   
4. Max and Min non-closure
5. Complement of {ww | w is a string over Sigma* } is a CFL
6. Solvable Decision Probelms about CFLs and CFGs
7. Solvable Decision Problems for CFL, L
   
1. Is w in L?
2. Is L empty (non-empty)?
3. Is L finite (infinite)?
8. Context Sensitive Grammars (CSG) and Languages (CSL)
9. Phrase Structured Grammars (CSG) and Languagess (re)
10. This ends the material for Exam#2 (Page 225 of Notes)
11. Solved/Unsolved, Solvable/Unsolvable, Enumerable (semi-decidable)/Non-Enumerable
12. Hilbert 10th
13. Cantor and diagonalization -- countable versus uncountable
14. Countability of machines/programs in any model of computation
15. Counting argument that there are undecidable problems
16. Halting Problem defined
17. Notations for convergence and non-convergence
18. Halting Problem -- undecidabibility using diagolization
    
19. Some handwritten notes for this week

Assignment #7

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

Due: 3/9 by 10:30AM (Key)

1. Turing Machines and Variants of Turing Machines
2. Turing Machines as enumerators/recognizers
3. Register Machines
4. Factor Replacement Systems (FRS) as simple models of computation
5. The necessity of order with FRSs
6. Discussion of determinism versus non-determinism in models of computation
7. Primitive (incomplete) and mu recursive (complete) functions
8. Numbering machines
9. Universal Machine
10. The Halting Problem -- classic undecidable but recognizable (semi-decidable, enumerable) problem
11. Diagonalization proof for Halting Problem
12. Exam#2 Topics pp. 223-225 in Notes
13. Last Semester's Exam#2  -- Complete this for discussion on 3/28 (key)
14. Another Sample Exam#2 -- Complete this for discussion on 3/28 (key)
15. Some handwritten notes for this week
16. Note: 3/22 is the Withdraw Deadline

1. In Class Review Session on Tuesday
2. Help Session on TBD ( I am trying to get a room for either Tues or Wed from 4 to6.)
   
3. MidTerm 2 on Thursday, 3/30

1. Set of Procedures can be enumerated by a 1-1 onto function
2. Halt is semi-decidable
3. The set of algorithms (TOTAL) is non-re
   
4. Diagonalization proof for non-re nature of set of algorithms
5. Enumeration Theorem (enumeration of RE sets)
   
6. Reducibility as a technique to show undecidability
7. Reducibility as a technique to show non-re-ness
8. Reducing Halt to TOTAL
   
9. Using reducibility to show properties of HasZero= { f | for some x, f(x) = 0 }
10. Notion of RE Completeness
    
11. Showing HALT us RE Complete (in RE and as hard as any other RE problem)
12. STP predicate (STP(f,x,t) iff f(x) converges in t steps or fewer)
13. VALUE(f,x,t) = f(x) if STP(f,x,t), else 0
14. Note that STP and VALUE are actually primitive recursive
    
15. Showing HasZero is RE Complete (in RE and HALT reduces to it)
    
16. Rice's Theorem (weak and strong forms)
17. Applying Rice's
18. Proof of Rice's Theorem
    
19. The sets K and K0 =HALT are equivalent and re-complete
20. RE sets
21. Using reducibility to show properties of Zero = { f | for all x, f(x) =0 }
22. Finally, proof that re and semi-decidable are same
23. Proof that re and co-re iff recursive (decidable, solvable)
24. Many-one reducibility and equivalence
    
25. Notion of (many-one) re-complete sets (HALT is one such set)
26. One-one reducibility and one-one degrees
27. Turing reducibility and Turing degrees
28. Quantification as a tool to identify upper bound complexity

Assignment #8

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

Due: 4/13 by 10:30AM (Key)

Assignment #9

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

Due: 4/20 by 10:30PM (Key)

1. Rewriting Systems -- Semi-Thue systems
2. Undecidability of Semi-Thue word problem (ST (Word))
3. Post Correspondence Problem (PCP)
4. ST(Word) reduced to PCP shows PCP unsolvable
   
5. Applications of PCP (Undecidability of Ambiguity of CFLs and Non-emptiness of Intersection of CFLs)
6. 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
7. Traces (computational histories of terminating computations)
1. While traces are context sensitive, their complements are context free
2. A legal trace must make no errors; a bad trace needs just one error
   
8. Quotients and intersections of CFLs
1. Can have one pseudo trace L1 that is right on even/odd pairs and another L2 on odd/even pairs
2. L1 and L2 are CFLs; Intersection of L1 and L2 is a valid trace (a CSL)
   
3. Quotient can be used to produce just those starting IDs for which machine terminates
4. Thus, quotient of two CFLs can get any and all RE (Phrase Structured) languages
5. The quotient result shows CFLs and CSLs are not closed under quotient
   
9. ST(Word) reduced to re membership
10. Lots of consequences of above
11. Is L = Sigma* is undecidable (comes from complement of terminating traces being a CFL)?
    
1. Is L = L²? undecidable for CFL since can reduce Is L = Sigma*? to Is L = L²?
2. There is a more complex proof that we cannot decide is there is an n such that L = Lⁿ
   
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 them there are an infinite number
   
13. If S and its complement are RE, then S is decidable
    
14. Introduction to Complexity Theory
15. Verifiers versus solvers
16. NP as verifiable in deterministic polynomial time
17. P as solvable in deterministic polynomial time
18. NP as solvable in non-deterministic polynomial time
19. Million dollar question: P = NP ?
20. Some NP problems that do not appear to be in P: SubsetSum, Partition
21. Concepts of NP-Complete and NP-Hard
22. Canonical NP-Complete problem: SAT (Satisfiability)
23. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
24. 3SAT as a second NP-Complete problem
25. 3SAT to SubsetSum reduction
26. SubsetSum equivalence (within a polynomial factor) to Partition
27. Midterm Exam#2 Key

Week#14: (4/18, 4/20) --  Notes pp. 444-479; Chapter 7 of Sipser; Final Exam Review

1. 0-1 Integer Linear Programming
2. Vertex Cover
3. Independent Set
4. K-Color
5. Register Allocation
6. Scheduling on multiprocessor systems
7. Questions from Notes pp. 364-367
   
8. Sample Final
9. Final Exam Topics (Notes pp. 474-479)
10. Sample Final 1 (Key)
11. Sample Final 2 (Key)
12. Context Free Grammar Practice (Key)
    
13. Final Exam Review
    

    Assignment #10 (OPTIONAL)
    

    See page 440 of Notes
    Sample assignment with no answers
    Sample assignment with answers
    
    
    Due: 4/27 by 10:30AM (Key)

Week#15:  (4/25, 4/28) Final Exam Reviews (Tuesday at regular room and time, and on Friday from 5:00 to 7:00PM in HEC-101 (by Sina))

1. Following material will not be on exam and not even be discussed (Notes pp. 500-547)
   
2. Details of Equivalence of Compuational Models
3. Hamiltonian Circuit
   
4. Travelling Salesman
5. Tiling (undecidable in plane; NP-Complete in polynomial size limited plane)
   

Review Sessions: TBD

Final Exam; Tuesday, May 2, 1000 - 1250 (10:00AM - 12:50PM)