---

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

---

Structure: TR 10:30-11:45, HEC-117; 28 class periods, each 75 minutes long.
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

Instructor: Charles Hughes; Harris Engineering Center 247C; 823-2762
Office Hours: TR 9:30-10:00; 13:15-14:45 (1:15PM to 2:45PM)
GTA: Sarah Buchanan, sbuchanan@knights.ucf.edu, HEC201; OH: MW 14:00-16:00 (2:00PM to 4: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/Spring2010
Notes URL: http://www.cs.ucf.edu/courses/cot4210/Spring2010/Notes/COT4210Notes.pdf 

Assignments: About 8 to 10.

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 ;-)

Exam Dates (Tentative): Exam#1 -- February 18; Withdraw Deadline -- March 5; Exam#2 -- April 1; Final -- Tuesday, April 27, 10:00-12:50; Spring Break -- March 6-14

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%, A- >=88%, B+ >= 85%, B >= 80%,  B- >=78%, C+ >= 75%, C >= 70%, C->=60%, 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
4. Chomsky Hierarchy (sets context for much of course)
   

Assignment #0

Send me and Sarah 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: 1/15 by midnight

Assignment #1

See Page 39 in Notes

Due: 1/21 by 10:30AM (Key) Comments

1. Chomsky Hierarchy (continued from week 1)
   Classes of languages
   Phrase Structured Languages =  (Recursively) Enumerable = Turing Recognizable = Semi-Decidable; Membership in an re language is undecidable
   Decidable = Recursive: This class cannot be generated by any definable class of grammars
   Context Sensitive Languages (CSL) are generated by Context Sensitive Grammars (CSG or Type1) and regognized by Linear Bounded Automata (LBA); Membership in a CSl is decidable
   Context Free Languages (CFL) are generated by Context Free Grammars (CFG or Type2) and recognized by Non-Deterministic Pushdown Automata (NPDA)
   Deterministic (unambiguous) Context Free Grammars are an undecidable subset of CSG, but all deterministic CSLs are generated by LR(1) grammars (one token lookahead)
   Regular Languages are generated by Regular (Right Linear) Grammars (Type3) and recognized by Finite State Automata (FSA, DFA or NFA)
   
2. Computability: basic goals and definitions (solved, solvable, semi-decidable and complements)
3. How computability concepts relate to each other
4. Complexity theory: basic goals; big question is P=NP?
5. 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 #2

See Page 58 in Notes

Due: 1/28 by 10:30AM (Key) Comments

1. 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
   Simple closure (union, intersection, exclusive or, negation)
2. Non-determinism (NFA)
   Closure under concatenation, Kleene *
   Formal definition and examples
3. Equivalence of DFAs and NFAs (subset of all states construction)
4. Reachable states from some given state
5. Reaching states to some given state
6. Closure of Regular Languages under Prefix, Postfix and Substring
7. Minimizing the states of a DFA (indistinguishable vs distinguishable states)

Assignment #3 

See Page 71 in Notes

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

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 84 in Notes

Due: 2/11 by 10:30AM (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
   
5. Derivations (leftmost/rightmost)
   
6. Parsing (parse trees; top down/bottom up)
   
7. Notion of ambiguity (inherent versus due to a specific grammar) (Not on Exam#1)
8. Classic non-regular languages {0ⁿ1ⁿ | n is greater than or equal to 0}
   
9. Pumping Lemma for Regular Languages
10. Proofs that certain languages are not regular using Pumping Lemma
11. Topics and Promises for MidTerm # 1
12. Sample Exam  -- Complete this for discussion on 2/15 and 2/16 (key)

1. Help Session in CL1-320 on 2/15 from 2:00 to 4:00
2. Review and go over sample questions
3. MidTerm 1  (Chapters 0, 1; Notes pp. 1-84; Assignments 1-4; Regular Equations; Pumping Lemma; Dr. Workman's Notes, pp. 1-33 and 40-46 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 85 in Notes

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

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

Week#9: (3/16, 3/18) -- Chapter 2 of Sipser; Dr. Workman's Notes pp. 64-77, 86, 87

1. Midterm Exam#1 Key
2. Complement of {ww | w is a string over Sigma* } is a CFL
   
3. Parse trees, leftmost and rightmost derivations, and ambiguity
4. 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 useless 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. Change rhs of length k, k>2, to two rules, one with rhs of length 2 and the other of length k-1
   
5. More on parse trees and relation of height to longest length of string produced
6. Cocke-Kasami-Younger polynomial time CFG parser (details on pp.  86,87 of Dr. Workman's Notes)
7. Proof of Pumping Lemma for CFLs
8. Pushdown automata (PDA) non-determinstic vs deterministic
9. Shorthand notation for PDA 

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

PDF

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

1. 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. Limitation of pop or push as only stack moves
   
4. Recognition by accepting state, by empty stack and by both
2. PDA equivalence to CFG
3. Greibach Normal Form
   
4. Top-down vs bottom-up acceptance
5. Topics and Promises for MidTerm # 2
6. Sample Exam -- This is mostly Assignment#6
7. Old Midterm (key)
   

1. Help Session on 3/29 from 2:00 to 3:50 in room HEC-101
   
2. Closure properties for CFLs (intersection with regular, substitution)
3. Using substitution and intersection with regular to get many more, e.g., prefix, suffix and quotient with regular
4. Review and go over sample questions
5. MidTerm 2

1. Turing Machines
2. Variants of Turing Machines
3. Turing Machines as enumerators/recognizers
4. The Halting Problem -- classic undecidable but recognizable (semi-decidable, enumerable) problem
5. Diagonalization proof for Halting Problem
6. Complement cannot be enumerated (recognized by a TM)
7. Reducibility as a technique to show undecidability
8. Rice's Theorem
   

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

   PDF

   Due: 4/15 by 10:30AM (Key) Comments

1. Many-one reducibility
2. Rice's Theorem
3. Undecidable problems in formal language theory
4. Linear bounded automata
5. Post Correspondence Problem (PCP)
6. Applications of PCP
7. Traces (computational histories)
8. Is L = Sigma*? Is L = L^2? Non-closure of L1/L2 (both CFLs)
9. Notion of re completeness
10. Introduction to Complexity Theory
11. Verifiers versus solvers
12. NP as verifiable in deterministic polynomial time
13. P as solvable in deterministic polynomial time
14. NP as solvable in non-deterministic polynomial time
15. Million dollar question: P = NP ?
16. Some NP problems that do not appear to be in P: SubsetSum, Hamiltonian Path, k-Clique
17. Concepts of NP-Complete and NP-Hard
18. Canonical NP-Complete problem: SAT (Satisfiability)
19. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT

Assignment #8 

Sample Final

Due: 4/22 by 10:30AM (Key) This is for discussion only.

Week#14: (4/20, 4/22) --  Notes pp. 168-185; Chapter 7 of Sipser 

1. NP-Hard
2. QSAT as an example of NP-Hard, possibly not NP
3. co-P and co-NP
4. P = co-P ; P contained in intersection of NP and co-NP
5. 3SAT as a second NP-Complete problem
6. 3SAT to SubsetSum reduction
7. Scheduling on multiprocessor systems
8. Midterm Exam#2 Key
9. Finish up undecidability results about grammars
   
10. Final Exam Topics
11. Sample Final (Key)

Review Session; Monday April 26; Time:2:00 to 4:00; Room: HEC-302
Final Exam; Tuesday April 27; 10:00 - 12:50 in HEC117