Discrete
II: Theory of Computation
Fall 2018 |
email:
charles.e.hughes@knights.ucf.edu
Structure: TR 1330-1445 (1:30PM -
2: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: TR1515-1630
(3:15PM - 4:45PM)
GTA: Amirfarhad Nilizadeh (af.nilizadeh@knights.ucf.edu)
Office Hours: MF
10:00AM-11:45AM; 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
Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot4210/Fall2018
Notes URL: http://www.cs.ucf.edu/courses/cot4210/Fall2018/Notes/COT4210Notes.pdf
Quizzes and Assignments:
Approximately 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 ;-)
Important Dates: Exam#1 --
September 27; Withdraw
Deadline -- October 26; Exam#2 -- October 25; Final --
Tuesday, December 4,
1300-1550 (1:00PM-3:50PM)
Evaluation (Tentative):
Mid Terms -- 100 points each
Final Exam -- 175 points
Quizzes and Assignments -- 75 points
Bonus -- 50 points added to the weighting of 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%
Weeks#1: (8/21, 8/23)
-- Notes pp. 2-69 (Chapters 0
and 1 of
Sipser); Syllabus
- Ground rules
- Sets, sequences,
relations and
functions (review)
- Ordinals, cardinals and infinities
- Graphs
- Languages
- Set/Language recognizers and generators
- Introduction to computability:
historical and motivation perspective
- Basic notions of automata
theory, formal languages,
computability and complexity
- Brief
introduction to Chomsky
Hierarchy (sets context for much of course)
- Proof
techniques
- Complexity theory: basic
goals; big question is P=NP?
- Discussions
about non-determinism versus determinism
- 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)
- 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.
Formal definition and examples
State transition diagrams versus state transition tables
- More about sequential circuits and
automata
- Non-deterministic Finite State
Auomaton (NFA)
- Closure Properties (Complement, Union,
Intersection, Exclusive Union)
- Some
hand-written notes for this week
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/24).
Due: One Minute before Midnight Friday,
8/24
Assignment #2
See page 44 of Notes
Sample assignment
with no answers
Sample assignment
with answers
Due: Thursday, 8/30 at 1:30PM (Key)
Week#2: (8/28,
8/30)
-- Notes pp. 70-101 (Chapter 1
of Sipser)
- Notion of output, not just checking
(will follow up later)
- Non-determinism (NFA)
Closure under concatenation, Kleene *
Choosing the right model for various closure properties
Formal definition and examples
- The epsilon (lambda) closure of a set of states
- Equivalence of DFAs and NFAs (subset of all states
construction)
- Regular Expressions (closure of
primitive sets under union, concatenation and star
- Every language defined by a Regular Expression is
accepted by an NFA
- Every language accepted by a DFA is defined by a Regular
Expression (ripping states out)
- Approach#1: Rij(k) construction from DFA or NFA
- Approach #2: State Ripping similar to text Generalized
NFA (GNFA)
- Approach#3: Languages defined by Regular Equations (not
in text)
and NFAs without lambda transitions
- Some hand-written notes for this week
Assignment #3
See page 83 of Notes
Sample assignment with no
answers
Sample assignment
with answers
Due: Thursday 9/6 by 1:30PM (Key)
Week#3: (9/4, 9/6) --
Notes pp. 102-122
(Chapter
1 of Sipser); Samples
- Existence of
minimal state machine for any Regular Language
- Minimizing the states of a DFA (compatible vs
incompatible, aka indistinguishable vs
distinguishable states)
- Minimization example using notion of
incompatible/distinguishable
states
- Decidable Properties -- membership,
emptiness, everything, finiteness, equivalence
- Right model for closure of Regular Languages under
Intersection, Complement, and Reversal
- Closure of Regular Languages under
Substitution, Homomorphism, and Quotient
- Meta approach to closure based on
Substitution within Class and Intersection with Regular
- Closure of Regular Languages
under Prefix, Postfix,
Substring
- Classic non-regular languages {0n1n | n is greater than or
equal to 0}
- Pumping Lemma for Regular
Languages
- Proofs that certain languages
are not regular using Pumping Lemma
- Some hand-written notes for this
week
Assignment #4
See
page 114-115 of Notes
Sample
assignment with no answers
Sample assignment
with answers
Due: 9/13 by 1:30PM (Key); (Key
for 4.1) redone -- first one had a loop on 0 at D; should be 1 on D
Week#4: (9/11. 9/13)
- Notes
pp. 123-156 (Chapter
1 of Sipser); Samples
- Right-invariant
equivalence relationships and
Myhill-Nerode Theorem
- Proofs that certain languages
are not regular using Myhill-Nerode Theorem
- More
proofs that certain
languages
are not
regular using Pumping Lemma and Myhill-Nerode
- Transducers (automata with
output); Mealy and Moore Models
- Post, Thue rewriting systems
- Basic notion of grammars and
languages generated by grammars
- Chomsky hierarchy (Type 3
through Type 0 grammars and languages) -- see page 36 of Notes
- Notions of derivation and the
language generated by a grammar
- Regular (right linear, Type 3)
grammars
- Every language generated by a
regular grammar is regular
- Every regular language is
generated by a type 3 grammar
- The right and left linear
grammars generate equivalent classes of languages
- Can extend regular grammars to include strings rather
than single
characters
- Grammars and closure
properties
(union, concatenation, Kleene *)
- Reachable
states from some
given state
- Reaching states to some given
state
- Min and Max closure of Regular
Languages
- Some handwritten notes for this week
- End
of
Exam#1 Material
- Exam#1 Topics pp. 152-156 in
Notes
- Prior
Exam#1
-- Complete this for
discussion on 9/25 (key)
- Another
Prior Exam#1 -- Complete this for
discussion on 9/25 (key)
- Review
9/24 in HEC-101 from 10:00 to 12:00
Assignment #5
See
page 136 of Notes
Sample
assignment with no answers
Sample assignment
with answers
Due: 9/20 by 1:30PM (Key)
Week#5: (9/18,
9/20)
-- Notes pp. 157-171 (Relevant but not covered in
Chapter
1 of Sipser); pp.
157-171, Chapter 2 of Sipser
- Context free grammars
and
context free languages
- Sample grammars: {a^n
b^n}; {w
w(reversed)}; {w | #a(w) = #b(w)}
- Derivations
(leftmost/rightmost)
- Parsing (parse trees;
top
down/bottom up)
- Notion of ambiguity
(inherent
versus due to a specific grammar)
- Definition of ambiguity
-- some
string leads to two or more
- Parse trees
- Leftmost derivations
- Rightmost derivations
- Parsing problems (left
recursion
bad for top-down; right recusion bad for bottom-up)
- DCFLs (unambiguous CFLs)
versus
DCFGs (unambiguous CFGs)
- LR(k) languages versus grammars; LL(k) languages versus grammars
- LR(1) languages =
DCFLs; LR(k)
grammars properly contained in DCFGs
- LL(k) languages properly contained in LL(k+1)
languages
- LL(k) grammars
properly
contained in DCFGs
- In the limit as k goes to
infinity LL(k) languages = DCFLs
- Removing left or right recursion to accommodate top-down
or
bottom-up
- Examples of syntax directed parsing
- Some handwritten notes for
this week
Week#6: (9/25, 9/27)
-- 9/24:
GTA Review Monday, HEC-101, 10:00 to 12:00; 9/25: In-Class Review; 9/27:
Exam
- Exam#1 Topics pp. 152-156 in Notes
- Review and go over sample questions
- MidTerm
1 (Chapter 1; Notes pp. 1-156; Assignments
1-5; Handwritten notes through week 4)
Week#7: (10/2, 10/4)
-- Notes
pp. 172-201, Chapter 2 of Sipser
- Chomsky Normal Form (CNF)
- Chomsky Normal
Form (CNF)
and
the algorithm to convert a CFG to a CNF
- Eliminate lambda rules and
accommodate for nullable non-terminals
- Eliminate unit rules (chains
of non-terminals)
- Eliminate non-productive
non-terminals (no terminal string can be generated from them)
- Eliminate unreachable
non-terminals (cannot get to them from S)
- On rhs's of length >1,
replace each terminal with symbol that derives it directly
- Recursively change rhs of length k,
k>2, to two rules, one with rhs of length 2 and the other of length
k-1
- Cocke-Kasami-Younger
(CKY)
polynomial time CFG
parser
- Pumping Lemma for CFLs
- Constructive proof of Pumping
Lemma
for CFLs
- Non-CFLs {a^n b^n c^n }, {ww | w is a string over
Sigma* }
- Closure properties for CFLs
(intersection with regular, substitution)
- Non-closure (intersection and
complement)
- Intersection of {a^n b^n c^m}
and {a^m b^n c^n}
- Complement
- Complement of {ww | w is a
string over Sigma* } is a CFL
- Solvable Decision Problems
about CFLs
and CFGs
- Solvable Decision Problems for
CFL, L
- Is w in L?
- Is L empty (non-empty)?
- Is L finite (infinite)?
- Some handwritten notes
for this week
-
Assignment #6
See
page 192 of Notes
Sample assignment with no
answers
Sample assignment
with answers
Due: 10/11 by 11:59 PM (Key) Comments
Week#8: (10/9, 10/11) --
Notes pp. 202-225; Chapter
2 of Sipser
- Pushdown automata (PDA)
non-determinstic vs deterministic
- Notion of instantaneous description (ID)
- Equivalence of a variety of PDA
formalizations
- Bottom of stack marker versus
none at start
- Ability to push none or one,
versus many characters on stack
- Recognition by accepting
state, by empty stack and by both
- Chomsky Normal Form (CNF) and
the algorithm to convert a CFG to a CNF
- Shorthand notation for PDA
- Examples PDAs
- Top down parsing of a CFL by
PDA
- Bottom up parsing of CFL by PDA
- Using just pop and push
operations in
a PDA
- Converting PDA to CFG
- Example
to show PDA language is a CFL by two different methods
- Greiback Normal Form
(GNF) and
linear parsing (with great guessing)
- Max and Min non-closure
- Using substitution and
intersection with regular to get many more,
e.g., prefix, suffix , substring and
quotient with regularNon-determinism in PDAs
- Some handwritten notes
for this
week
- Context Sensitive Grammars
(CSG) and
Languages (CSL)
- Phrase Structured Grammars
(CSG) and
Languagess (re)
- This ends the material for
Exam#2
- Exam#2 Topics pp. 223-225 in
Notes
- Midterm
Exam#1 Key
- Earlier
Semester's
Exam#2
-- Complete this for
discussion on 10/23 (key)
- Another
Sample Exam#2 -- Complete this for
discussion on 10/23(key)
- Some
handwritten notes for this week
- Some
more handwritten notes for this week
Assignment #7
See
page 220 of Notes
Sample
assignment with no answers
Sample assignment
with answers
Due: 10/23 by 11:59 PM (Key)
Week#9: (10/16,
10/18) -- Notes
pp. 213-297 (some is just for your reading);
Chapter
2 of Sipser
- Some clean up of topics in
Exam#2
- Solved/Unsolved,
Solvable/Unsolvable,
Enumerable (semi-decidable)/Non-Enumerable
- Hilbert 10th
- Cantor and diagonalization --
countable versus uncountable
- Countability of
machines/programs in
any model of computation
- Counting argument that there
are
undecidable problems
- Halting Problem defined
- Notations for convergence and
non-convergence
- Halting Problem --
undecidabibility
using diagolization
- Turing Machines and Variants
of Turing
Machines
- Turing Machines as
enumerators/recognizers
- Register Machines
- Factor Replacement Systems
(FRS) as
simple models of
computation
- The necessity of order with
FRSs
- Discussion of
determinism versus
non-determinism in models of computation
- Some
handwritten notes for this week
Week#10:
(10/23, 10/25) -- 10/22:
GTA Review Monday, HEC-101, 10:00 to 12:00;
10/23 In-Class Review; 10/25 (Midterm2);
Notes pp. 223-225;
- Help Session on Monday,
10/22 from 10 to noon at HEC-101
- In Class Review Session on Tuesday, 10/23
- Closure Review Sheet
(Key)
- MidTerm 2 on Thursday, 10/25
- Note:
10/26 is
the
Withdraw Deadline
Week#11: (10/30, 11/1) -- Notes
pp. 298-338; Chapters 4, 5 of Sipser
- Primitive (incomplete) and mu recursive (complete)
functions
- Numbering machines
- Universal Machine
- The Halting Problem -- classic undecidable but
recognizable
(semi-decidable, enumerable) problem
- Diagonalization proof for Halting Problem
- Set of Procedures can be
enumerated by
a 1-1 onto function
- Halt is semi-decidable
- The set of algorithms (TOTAL)
is
non-re
- Diagonalization proof for
non-re
nature of set of algorithms
- Enumeration Theorem
(enumeration of RE
sets)
- Reducibility as a technique to
show
undecidability
- Reducibility as a technique to
show
non-re-ness
- Reducing Halt to TOTAL
- Using reducibility to show
properties
of HasZero= { f | for some x, f(x) = 0 }
- Using reducibility to show
properties
of Zero = { f | for all
x, f(x) =0 }
- RE sets and their complex
hierarchy
- Many-one reducibility and
equivalence
- Notion of (many-one)
re-complete sets
(HALT is one such set)
- One-one reducibility and
one-one
degrees
- Turing reducibility and Turing
degrees
- Notion of RE Completeness
- Showing K0 = HALT is RE
Complete (in
RE and as hard as any other RE problem)
- The sets K is RE-complete
- Showing HasZero is RE Complete
(in RE
and HALT reduces to it)
- Rice's Theorem (weak and
strong forms)
- Proofs of Rice's Theorem
(textual and
visual)
- Applying Rice's
- Some
handwritten notes for this week
Assignment #8
See page 350 of Notes
Sample
assignment with no answers
Sample assignment
with answers
Due: 11/13 by 11:59PM (Key)
Week#12: (11/6,
11/8) -- Notes pp. 339-398; Chapters 4, 5 of Sipser
- Examples of applying Rice's
Theorem
(all three forms)
- STP predicate
(STP(f,x,t) iff
f(x)
converges in t steps or
fewer)
- VALUE(f,x,t) = f(x) if
STP(f,x,t),
else 0
- Note that STP and VALUE are
actually
primitive recursive
- Finally, proof that re and
semi-decidable are same
- If
S and its complement
are RE,
then S is decidable
- Quantification as a tool to
identify
upper bound complexity
- Picture of relationships of
REC, RE,
RE Complete, Co-RE, non-RE/non-co-RE, non-Recursive
- Post Correspondence Problem
(PCP)
- Applications of PCP
(Undecidability of
Ambiguity of CFLs and
Non-emptiness of Intersection of CFLs)
- Application of PCP to
Undecidability
of Non-emptiness of CSLs
- This can be done by a CSG that produces strings iff PCP
has a
solution
- It can also be shown by fact that intersection of two
CFLs is a
CSL
- Is L = Sigma* is undecidable
(comes
from complement of terminating traces being a CFL)?
- Is L = L2? undecidable for CFL since can
reduce Is L
= Sigma*? to Is L = L2?
- There is a more complex proof that we cannot decide is
there is
an n such that L = Ln
- More Unsolvable Decision
Problems for
CFL, L
- Is L = L', where L' is some other CFL? Just set L' =
Sigma*
- Is L intersect L' empty (non-empty); straight from PCP
reduction to non-empty intersection
- Is L intersect L' finite (infinite); if PCP mapping
gets one
overlap then there are an infinite number
- Midterm
Exam#2
Key
- Some
more handwritten notes for this week
- A few more notes from this week
Assignment
#9
Due: 11/20 by 11:59 PM (Key)
Week#13: (11/13,
11/15) -- Notes pp. 399-444 Chapters
5 and 6 of Sipser
- Introduction to Complexity Theory
- Verifiers versus solvers
- NP as verifiable in
deterministic polynomial time
- P as solvable in deterministic
polynomial time
- NP as solvable in
non-deterministic polynomial time
- Million dollar question: P = NP ?
- Some NP problems that do not
appear to be in P: SubsetSum, Partition
- Concepts of NP-Complete and
NP-Hard
- Canonical NP-Complete problem:
SAT (Satisfiability)
- Construction that maps every
problem solvable in non-deterministic polynomial time on TM to SAT
- SAT reduction to 3SAT
- 3SAT as a second NP-Complete
problem
- 3SAT reduction to SubsetSum
reduction
- SubsetSum equivalence (within
a
polynomial factor) to Partition
- 3SAT reduction to 0-1 Integer
Linear
Programming
- Vertex Cover
- Independent Set
- K-Color
- Register
Allocation
- Some
handwritten written notes for this week
Assignment
#10
Due: 11/29 by 11:59PM (Key)
Week#14:
(11/20)
-- Chapter
7 of Sipser; Final Exam Review
- Go over SumSome = { f |
range of f has three distinct values, x,y,z where z=x+y}
- Go over above with
quantification, reduction and Rice's
- Go over Finite Range = { f |
range of f is finite }
- Go over above with
quantification, reduction and Rice's
- Go over probelms on Pages 26 and
9 of Final
Review
- Some
handwritten notes for this week
Week#15:
(11/27, 11/29) Notes pp.
445-479;
Final Exam
Reviews (Tuesday and Thursday at regular room and time)
- Scheduling on multiprocessor
systems
- Questions from Notes pp. 364-367
- Sample Final
- Final Exam Topics (Notes
pp. 474-479)
- Closure Review
- Closure Review Key
- Final
Exam Sample without key
- Final Exam Review with
Sample
Exam Key
- Second
Final
Exam Sample without Key
- Second
Final Exam
Sample with Key
- Final Review
- Additional Help Session on Monday (see below)
- Following material will
not be on
exam and not even be discussed (Notes pp. 480-547)
- Details of Equivalence
of
Computational Models
- Hamiltonian Circuit
- Travelling Salesman
- Tiling (undecidable in
plane;
NP-Complete in polynomial size limited plane)
Review
Sessions: This whole week and Monday, December 3, 5:00PM to 7:00PM, in HEC-101
Final Exam; Tuesday,
December 4, 1300 - 1550 (1:00PM - 3:50PM); BA1-119
© UCF Last Updated December 3, 2018