---

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

---

Structure: TR 1330-1745 (1:30PM - 2:45PM), MSB-359; 28 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 1515-1630 (3:15PM - 1:30PM)
GTA: Melanie Kaprocki; HEC-234 (Computer Vision Lab II); OH: M 1600-1730 (4:00PM - 5:30PM); F 1330-1500 (1:30PM - 3:00PM)
Text: Sipser, Introduction to the Theory of Computation 2nd Ed., Cengage Learning, 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/Fall2014
Notes URL: http://www.cs.ucf.edu/courses/cot4210/Fall2014/Notes/COT4210Notes.pdf

Assignments: 8 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 -- September 26; Withdraw Deadline -- October 27; Exam#2 -- October 31; Final -- Tuesday, December 9, 1300-1550 (1:00PM-3:50PM)

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. Basic notions of automata theory, formal languages, computability and complexity
3. Chomsky Hierarchy (sets context for much of course)
   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 CFG, but all deterministic CFLs 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)
4. Some history of the genesis of the theory of computation (Hilbert, Godel, Turing, Post, Kleene)
5. Languages (countable sets of strings); why there are problems that no program can address
6. Sets, sequences, relations and functions (review)
7. Computability: basic goals and definitions (solved, solvable, semi-decidable and complements)
8. How computability concepts relate to each other
9. Complexity theory: basic goals; big question is P=NP?

Assignment #1

See page 47 of Notes
Sample problems (of same genre) and solutions to make your life a bit easier

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

1. Discussions about non-determinism versus determinism; universal versus existential quantification; discrete versus continuous solution spaces
   
2. 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)
3. 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, difference, exclusive or, negation)
4. Non-determinism (NFA)
   Closure under concatenation, Kleene *
   Formal definition and examples

Assignment #2

See page 59 of Notes
Sample problems (of same genre) and solutions to make your life a bit easier

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

1. The epsilon (lambda) closure of a state of set of states
2. Equivalence of DFAs and NFAs (subset of all states construction)
3. Reachable states from some given state
4. Reaching states to some given state
5. Minimizing the states of a DFA (indistinguishable vs distinguishable states)
6. Minimization example using notion of distinguishable states
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. Generalized NFA (GNFA) -- Definition
10. Every language accepted by a DFA is defined by a Regular Expression (ripping states out)
11. Alternate approach through Rij(k) construction
12. Languages defined by Regular Equations (not in text) and NFAs without lambda transitions
13. Closure of Regular Languages under Reversal

Assignment #3 

See page 71 of Notes
Sample problems (of same genre) and solutions to make your life a bit easier

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

1. Reachable states from some given state
2. Reaching states to some given state
3. Closure of Regular Languages under Prefix, Postfix, Substring, Min and Max
4. Classic non-regular languages {0ⁿ1ⁿ | n is greater than or equal to 0}
5. Pumping Lemma for Regular Languages
6. Proofs that certain languages are not regular using Pumping Lemma
7. Basic notion of grammars and languages generated by grammars
8. Chomsky hierarchy (Type 3 through Type 0 grammars and languages)
9. Regular (right linear, Type 3) grammars

Assignment #4

See page 90 of Notes
Sample problems (of same genre) and solutions to make your life a bit easier

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

1. Every language generated by a regular grammar is regular
2. Every regular language is generated by a type 3 grammar
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. Right-invariant equivalence relationships and Myhill-Nerode Theorem
6. Proofs that certain languages are not regular using Myhill-Nerode Theorem
7. Right-invariant equivalence relationships and Myhill-Nerode Theorem
8. Existence of minimal state machine for any Regular Language
9. More proofs that certain languages are not regular using Pumping Lemma and Myhill-Nerode
10. Topics and Promises for MidTerm # 1
11. Sample Exam  -- Complete this for discussion on 9/23 (key)

1. Help Session in ENG1-224 on 9/22 from 4:00PM to 5:30PM
   
2. Review and go over sample questions
3. MidTerm 1  (Chapters 0, 1; Notes pp. 1-97; Assignments 1-4; Regular Equations; Pumping Lemma; Dr. Workman's Notes, pp. 1-57 that were covered in class)

1. Grammars and closure properties (union, concatenation, Kleene *)
2. Transducers (automata with output); Mealy and Moore Models
3. Closure under homomorphism and substitution
4. Constructions using NFAs to show closure under homomorphism and substitution
5. Closure under quotient, prefix, substring and suffix, using substitution and intersection
6. Constructions using regular expressions and NFAs
7. Difficulty with direct proof and right linear grammars
8. Review Chomsky hierarchy
9. Notion of instantaneous description for automata and grammars
10. Notions of derivation and the language generated by a grammar
    
11. Derivations (leftmost/rightmost
12. Parsing (parse trees; top down/bottom up)
13. Notion of ambiguity (inherent versus due to a specific grammar)
    
14. Context free grammars (CFGs) and languages (CFLs)
15. Sample grammars: {a^n b^n}; {w w(reversed)}; {w | #a(w) = #b(w)}
    
16. Closure properties for CFLs (union, concatenation, Kleene  *)
17. Non-CFLs {a^n b^n c^n }, {ww | w is a string over Sigma* }
18. 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

Assignment #5

See page 103 of Notes
Sample problems (of same genre) and solutions to make your life a bit easier

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

1. Pumping Lemma for CFLs (no proof)
2. Non-CFLs {a^n b^n c^n }, {ww | w is a string over Sigma* }
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. Recursively change rhs of length k, k>2, to two rules, one with rhs of length 2 and the other of length k-1
   
5. Sample of conversion to CNF
   
6. More on parse trees and relation of height to longest length of string produced
7. Every CFL is recognized by a PDA
   
8. Top-down vs bottom-up acceptance
9. Midterm Exam#1 Key

Week#9: (10/14, 10/16) -- Notes pp. 118-138; Chapter 2 of Sipser; Dr. Workman's Notes pp. 68-77, 86, 87

1. Pushdown automata (PDA) non-determinstic vs deterministic
2. 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
3. Cocke-Kasami-Younger polynomial time CFG parser (details on pp.  86,87 of Dr. Workman's Notes)
4. Closure properties for CFLs (intersection with regular, substitution)
5. Using substitution and intersection with regular to get many more, e.g., prefix, suffix and quotient with regular
6. Shorthand notation for PDA
7. Limitation of pop or push as only stack moves
8. Complete PDA equivalence to CFG by showing every language accepted by PDA is a CFL
9. Constructive proof of Pumping Lemma for CFLs

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

Assign#6:SampleMidterm2

Due: 10/23 by 1:30PM (Key) -- Just kidding; It does not have to be turned in.

1. Example to show PDA is a CFL by two different methods
   
2. Non closure of CFLs under complement and intersection, min and max
1. Consider the two operations on languages max and min, where
   max(L) = { x | x ∈ L and, for no non-null y does xy ∈ L } and
   min(L) = { x | x ∈ L and, for no proper prefix of x, y, does y ∈ L }
   Describe the languages produced by max and min. for each of the following:
   L1 = { aⁱ b^j c^k | k ≤ i or k ≤ j }
   max(L1) =     { aⁱ b^j c^k | k =max(i, j)  }   
   min(L1) =      { λ } (string of length 0)   
   L2 = { aⁱ b^j c^k | k > i or k > j }
   max(L2) =     {  } (empty)           
   min(L2) =      { aⁱ b^j c^k | k =min(i, j)+1  }   
   
3. Greibach Normal Form
4. Solvable Decision Problems for CFL, L
   
1. Is w in L?
2. Is L empty (non-empty)?
3. Is L finite (infinite)?
   
5. Unsolvable Decision Problems for CFL, L -- Later
   
1. Is L = Sigma*
2. Is L = L', where L' is some other CFL?
3. Is L intersect L' empty (non-empty)
   
6. Sample Exam2 is Assignment#6
   
7. Topics and Promises for MidTerm # 2
8. Solver/Unsolved, Solvable/Unsolvable, Enumerable (semi-decidable)/Non-Enumerable
9. Turing Machines
10. I need to leave at 2:15 on Thursday and Melanie will start review at that time
    
11. Note: 10/27 is the Withdraw Deadline

1. Help Session in ENG1-427 on Monday, 10/27, from 4:00 to 5:45
   
2. Variants of Turing Machines
3. Turing Machines as enumerators/recognizers
4. Factor Replacement Systems (FRS) as simple models of computation
5. Petri Nets as a model of synchronization; order their transitions and they are Turing-enabled
6. The necessity of order with FRSs
7. Clean up details of anything missed from previous week
8. Review and go over topics and sample questions
   
9. MidTerm 2 on Thursday, 10/30
   

1. The Halting Problem -- classic undecidable but recognizable (semi-decidable, enumerable) problem
2. Diagonalization proof for Halting Problem
3. STP predicate (STP(f,x,t) iff f(x) converges in t steps or fewer)
4. VALUE(f,x,t) = f(x) if STP(f,x,t), else 0
   
5. Reducibility as a technique to show undecidability
6. The set of Algorithms (TOTAL)
7. Total is not even re shown by diagonalization
8. Reducibility as a technique to show non-re-ness
9. Using reducibility to show properties of Zero = { f | for all x f(x) =0 }

Assignment #7

See page 206 of Notes
Sample problems (of same genre) and solutions to make your life a bit easier

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

1. Many-one reducibility and equivalence
   
2. Notion of (many-one) re-complete sets (HALT is one such set)
   
3. The sets K and K0 are equivalent and re-complete
4. STP predicate (STP(f,x,t) iff f(x) converges in t steps or fewer)
5. VALUE(f,x,t) = f(x) if STP(f,x,t), else 0
   
6. Finally, proof that re and semi-decidable are same
7. Proof that re and co-re iff recursive (decidable, solvable)
8. Rice's Theorem (weak and strong forms)
9. Applying Rice's
10. Quantification as a tool to identify upper bound complexity

Practice Assignment #8 

See page 234 of Notes

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

Week#14: (11/18, 11/20) --  Notes pp. 239-281; Chapters, 5 and 7 of Sipser (pp. 246-256 were informational only)

1. Undecidable problems in formal language theory
2. Post Correspondence Problem (PCP)
3. Applications of PCP (Undecidability of Ambiguity of CFLs and Non-emptiness of Intersection of CFLs)
4. Application of PCP to Undecidability of Non-emptiness of CSLs
5. Traces (computational histories)
6. Is L = Sigma*? Is L = L^2? Non-closure of L1/2 (both CFLs)
7. Midterm Exam#2 Key
8. Introduction to Complexity Theory
9. Verifiers versus solvers
10. NP as verifiable in deterministic polynomial time
11. P as solvable in deterministic polynomial time
12. NP as solvable in non-deterministic polynomial time
13. Million dollar question: P = NP ?
14. Some NP problems that do not appear to be in P: SubsetSum, Partition
15. Concepts of NP-Complete and NP-Hard
16. Canonical NP-Complete problem: SAT (Satisfiability)
17. Construction that maps every problem solvable in non-deterministic polynomial time on TM to SAT
18. 3SAT as a second NP-Complete problem
19. 3SAT to SubsetSum reduction
20. SubsetSum equivalence (within a polynomial factor) to Partition
21. 0-1 Integer Linear Programming
    

Week#15:  (11/25, Thanksgiving) --   Notes pp. 282-291; Chapter 7 of Sipser 

1. Scheduling on multiprocessor systems
2. NP-Hard
3. QSAT as an example of NP-Hard, possibly not NP, problem
4. co-NP
5. Final Exam Topics (Notes pp. 286-291)
6. Some Samples (Notes pp. 235-238)
7. Sample Final (Key)

Review Sessions: TBD

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