---

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

---

Structure: TR 13:30-14:45 (1;30PM - 2:45PM), HEC-117; 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: TR 15:15-16:45 (3:15PM - 4:45PM)
GTA: Raymond Ho HEC308; yiuyuho@cs.ucf.edu ; OH: MW 16:00 -1800 (4:00PM - 6:00PM)

Text: Sipser, Introduction to the Theory of Computation 2nd Ed., Course Technologies, 2005+Notes
Secondary References: Hopcroft, Motwani and Ullman, Introduction to Automata Theory, Languages and Computation 2nd Ed., Addison-Wesley, 2001.
Prerequisites: COT 3100; COP3503

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

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. 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 -- October 1; Withdraw Deadline -- October 16; Exam#2 -- November 5; Final -- Tuesday, December 8, 13:00-15:50

Evaluation (Tentative):
Mid Terms -- 100 points each
Final Exam -- 150 points
Assignments -- 100 points
Bonus -- 50 points added to your best exam
Total Available: 500
Grading will be  A >= 90%, B+ >= 87%, B >= 80%, C+ >= 77%, C >= 70%, D >= 50%, F < 50%

1. Introduction to computability: an historical perspective
2. Sets, sequences, relations and functions (review)
3. Basic notions of languages, computability and complexity

Assignment #0

Send me and Raymond an e-mail with subject COT4210 containing
(1) When and where did you take Discrete I or its equivalent?
(2) What times are you NOT free to make office hours?

Due: 8/28 by midnight

Assignment #1

See page 39 of Notes

Due: 9/3 by 1:30PM (Key) Pages 1-5

1. Computability: basic goals and definitions (solved, solvable, semi-decidable and complements)
2. How computability concepts relate to each other
3. Complexity theory: basic goals; big question is P=NP?
4. Determinitic Finite (State) Automaton (DFA): what and why?
   Sequential circuits; pattern matchers; lexical analyzers; simple game/simulation behaviors
   Formal definition and examples
   State diagrams versus state transition tables
   Simple closure *union, intersection, exclusive or, negation"
5. Non-determinism (NFA)
   Why: Closure under concatenation, Kleene *
   Formal definition and examples
   

Assignment #2

See page 64 of Notes

Due: 9/10 by 1:30PM (Key) Pages 6-9

1. Equivalence of DFAs and NFAs (subset of all states construction)
2. Closure of Regular Languages under union, concatenation, Kleene *
3. Reachable states from some given state
4. Reaching states to some given state
5. Closure of Regular Languages under Prefix, Postfix and Substring
6. Minimizing the states of a DFA (indistinguishable vs distinguishable states)

Assignment #3 

See pages 76 of Notes (See Notes, I reduced this to 3 questions)

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

1. Minimization example using notion of distinguishable states
2. Regular Expressions (closure of primitive sets under union, concatenation and star)
3. Every language defined by a Regular Expression is accepted by an NFA
4. Generalized NFA (GNFA) -- Definition
5. Every language accepted by a DFA is defined by a Regular Expression (ripping states out)
6. Alternate approach through Rij(k) construction
7. Closure of Regular Languages under Reversal
8. Languages defined by Regular Equations (not in text) and DFAs

Assignment #4

See page 77 of Notes

Due: 9/24 by 1:30PM (Key) Comments

1. Basic notion of grammars and languages generated by grammars
2. Chomsky hierarchy (Type 3 through Type 0 grammars and languages)
3. Regular (right linear, Type 3) grammars
4. Context free grammars (Not on Exam#1)
5. Notion of ambiguity (inherent versus due to a specific grammar) (Not on Exam#1)
6. Dr. Workman talking on parsers
   
7. Classic non-regular languages {0ⁿ1ⁿ | n is greater than or equal to 0}
   
8. Pumping Lemma for Regular Languages
9. Proofs that certain languages are not regular using Pumping Lemma
10. Topics and Promises for MidTerm # 1
11. Sample Exam  -- Complete this for discussion on 9/29 (key)

1. Raymond will do Help Session in HEC-101 on 9/28 from 4:00 to 6:00
2. Review and go over sample questions
3. There are more sample questions on pp. 86-89 of Notes.
   
4. MidTerm 1  (Chapters 0, 1; Notes pp. 1-80; Assignments 1-4; Regular Equations; Pumping Lemma, Myhill-Nerode; Dr. Workman's Notes, pp. 1-39 that were covered in class)

1. Right-invariant equivalence relationships and Myhill-Nerode Theorem
2. Existence of minimal state machine for any Regular Language
3. Proofs that certain languages are not regular using Pumping Lemma and Myhill-Nerode
4. Review Chomsky hierarchy
5. Notion of instantaneous description for automata and grammars
6. Notions of derivation and the language generated by a grammar
   
7. Every language generated by a regular grammar is regular
8. Every regular language is generated by a type 3 grammar
9. The right and left linear grammars generate equivalent classes of languages
10. Grammars and closure properties (union, concatenation, Kleene *)
11. Transducers (automata with output); Mealy and Moore Models

Assignment #5

See page 90 of Notes

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

1. Midterm Exam#1 Key
2. Closure under homomorphism and substitution
3. Closure under quotient, prefix, substring and suffix, using substitution and intersection
4. Constructions using regular expressions and NFAs
5. Difficulty with direct proof and right linear grammars
6. Complexity of various algorithms for finite automata and regular grammars
7. Transducers (automata with output); Mealy and Moore Models
8. Context free grammars (CFGs) and languages (CFLs)
9. Sample grammars
10. Pumping Lemma for CFLs (no proof)
11. Closure properties for CFLs (union, concatenation, Kleene  *)
12. Non-CFLs {a^n b^n c^n }, {ww | w is a string over Sigma* }
13. Non-closure (intersection and complement)
1. Intersection of {a^n b^n c^m} and {a^m b^n c^n}
2. Complement of {ww | w is a string over Sigma* } is a CFL
   
14. Note: 10/16 is the Withdraw Deadline

Week#9: (10/20, 10/22) -- Chapter 2 of Sipser; Dr. Workman's Notes pp. 68-83

1. Parse trees, leftmost and rightmost derivations, and ambiguity
2. Chomsky Normal Form (CNF) and the algorithm to convert a CFG to a CNF
1. Eliminate useless non-terminals (no terminal string can be generated from them)
2. Eliminate unreachable non-terminals (cannot get to them from S)
3. Eliminate lambda rules and accommodate for nullable non-terminals
4. Eliminate unit rules (chains of non-terminals)
5. On rhs's of length >1, replace each terminal with symbol that derive it directly
6. Change rhs of length k, k>2, to two rules, one with rhs of length 2 and the other of length k-1
   
3. More on parse trees and relation of height to longest length of string produced
4. Cocke-Kasami-Younger polynomial time CFG parser (details on pp.  77,79 of Dr. Workman's Notes
5. Pushdown automata (PDA) non-determinstic vs deterministic
6. Shorthand notation for PDA 
7. Equivalence of a variety of formalizations
   
1. Bottom of stack marker versus none at start
2. Ability to push none or one, versus many characters on stack
3. Limitation of pop or push as only stack moves
   
4. Recognition by accepting state, by empty stack and by both

Assignment #6 (also a prep for Exam#2)

It's a pdf

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

1. PDA equivalence to CFG
2. Greibach Normal Form
   
3. Top-down vs bottom-up acceptance
4. Proof of Pumping Lemma for CFLs
5. Closure properties for CFLs (intersection with regular, substitution)
6. Using substitution and intersection with regular to get many more, e.g., prefix, suffix and quotient with regular
7. Introduction to computability theory (a bit of history)
8. Topics and Promises for MidTerm # 2
9. Sample Exam -- This is mostly Assignment#6, a topic for discussion on 11/3
10. Supplementary questions (topics since Assignment#6) (key)
    

1. Raymond will do Help Session in ENGR2-302 on 11/2 from 4:00 to 5:50
2. Basic notions of what is computable/non-computable, what is recognizable/non-recognizable
3. Review and go over sample questions
4. Raymond will do second Help Session in TBD on 11/4 from 4:00 to 5:30
5. MidTerm 2

1. Hilbert 10th problem (over one variable; over many variables
2. Turing Machines
3. Variants of Turing Machines
4. Turing Machines as enumerators/recognizers
5. The Halting Problem -- classic undecidable but recognizable (semi-decidable, enumerable) problem
6. Diagonalization proof for Halting Problem
7. Complement cannot be enumerated (recognized by a TM)
8. Reducibility as a technique to show undecidability
9. Many-one reducibility

   Assignment #7 (also a postmortem from Exam#2)
   

   It's a pdf

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

1. Rice's Theorem
2. Undecidable problems in formal language theory
3. Traces (computational histories)
4. Linear bounded automata
5. Post Correspondence Problem (PCP)
6. Applications of PCP
7. Introduction to Complexity Theory
   

Assignment #8 

See page 155 of Notes

Due: 12/1 by 1:30PM (Key) Comments

Week#14: (11/24, Turkey Day) --  Notes pp. 179-195; Chapter 7 of Sipser 

1. Verifiers versus solvers
2. NP as verifiable in deterministic polynomial time
3. P as solvable in deterministic polynomial time
4. NP as solvable in non-deterministic polynomial time
5. co-P and co-NP
6. P = co-P ; P contained in intersection of NP and co-NP
7. Million dollar question: P = NP ?
8. Some NP problems that do not appear to be in P: SubsetSum, Hamiltonian Path, k-Clique
9. Concepts of NP-Complete and NP-Hard
10. Canonical NP-Complete problem: SAT (Satisfiability)
11. Start of construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
    

Week#15:  (12/1, 12/3) --   Notes pp. 179-195; Chapter 7 of Sipser 

1. Finish showing SAT is NP-Complete
2. 3SAT as a second NP-Complete problem
3. 3SAT to SubsetSum reduction
4. Scheduling on multiprocessor systems
5. Midterm Exam#2 Key
6. Finish up undecidability results about grammars
   
7. Final Exam Topics (in Notes, pages 202-209)
8. Sample Final (Key)

Raymond's Review Session; Monday December 7; 16:00 - 18:00 (4:00PM to 6:00PM); Room: ENGR2-302
Final Exam; Tuesday December 8; 13:00 - 15:50 (1:00PM - 3:50PM)