þÿ<!DOCTYPE doctype PUBLIC "-//w3c//dtd html 4.0 transitional//en"><html> <head> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <meta name="GENERATOR" content="Mozilla/4.75 [en] (Windows NT 5.0; U) [Netscape]"> <meta name="Author" content="Charles E. Hughes"> <meta name="Description" content="Notes for Spring 2001 Concepts of Parallel and Distributed Processing course"> <meta name="KeyWords" content="Distributed Processing, Parallel Processing"> <title>COT5310: Formal Languages and Automata Theory -- Fall 2007</title></head> <body> <a name="Top"></a> <center> <table border="2" cellspacing="4" cellpadding="8"> <tbody> <tr> <td align="center"><b><font color="#000000"><font size="+1">Formal Languages and Automata<strong> Theory</strong></font></font></b><br> <b><font color="#000000"><font size="+1">Fall 2007</font></font></b></td> </tr> </tbody> </table>  </center> <center> <p><img src="Images/UCF-wm.gif" alt="U.C.F." nosave="" height="88" width="144" align="middle"></p> </center> <center> <h4><a href="http://www.cs.ucf.edu/%7eceh">Charles E. Hughes<br> </a><a href="http://www.eecs.ucf.edu">School of Electrical Engineering and Computer Science<br> </a><a href="http://www.ucf.edu">University of Central Florida</a></h4> </center> <center> <hr width="100%"> <a href="mailto:ceh@cs.ucf.edu"><img src="Images/mbox.gif" nosave="" height="25" width="21" align="middle"> </a><a href="mailto:ceh@cs.ucf.edu">email: ceh@cs.ucf.edu</a> <hr width="100%"> </center> <p><b>Structure</b>: MW 19:30-20:45 (7:30PM - 8:45PM), <font color="#000000">HEC-103</font>; 29 class periods, each 75 minutes long.<br> <font color="#ff0000"><b>Go To Week</b> <a href="#Week1">1</a>, <a href="#Week2">2</a>, <a href="#Week3">3</a>, <a href="#Week4">4</a>, <a href="#Week5">5</a>, <a href="#Week6">6</a>, <a href="#Week7">7</a>, <a href="#Week8">8</a>, <a href="#Week9">9</a>, <a href="#Week10">10</a>, <a href="#Week10">11</a>, <a href="#Week11">12</a>, <a href="#Week12">13</a>, <a href="#Week13">14</a>, <a href="#Week16">15</a>, <a href="#Week16">16</a> </font></p> <p><b>Instructor:</b> Charles Hughes; Harris Engineering Center 439C; 823-2762; <a href="mailto:ceh@cs.ucf.edu">ceh@cs.ucf.edu</a><br> <b><font color="#000000">Office Hours:</font></b> MW 17:00-18:15 (5:00PM - 6:15PM)<br> <b>GTA: Greg Tener, </b>TTh 18:30-19:30 (6:30PM - 7:30PM) in HEC 365</p> <p><b>Text: </b>There will be no required text. I will use extensive notes.<b> </b><b><br> Primary Reference</b>: Davis, Sigal and Weyuker, <i>Computability, Complexity and Languages 2nd Ed.</i>, Academic Press (Morgan Kaufmann), 1994.<br> <strong>Secondary References</strong>: Hopcroft, Motwani and Ullman, <em>Introduction to Automata Theory, Languages and Computation</em> <em>2nd Ed.</em>, Addison-Wesley, 2001.<br> Papadimitriou and Lewis, <em>Elements of the Theory of Computation</em>, Prentice-Hall, 1997.<br> <b>Prerequisites</b>: COP 4020 (Covers parsing and some semantic models); COT 4210 (covers regular and context free languages)</p> <p><strong>Web Pages</strong>:<br> Base URL: <a href="http://www.cs.ucf.edu/courses/cot5310/">http://www.cs.ucf.edu/courses/cot5310/</a><br> Notes URL: <a href="http://www.cs.ucf.edu/courses/cot5310/Notes/COT5310Notes.ppt">http://www.cs.ucf.edu/courses/cot5310/Notes/COT5310Notes.ppt</a>; or<br> <a href="http://www.cs.ucf.edu/courses/cot5310/Notes/COT5310Notes.pdf">http://www.cs.ucf.edu/courses/cot5310/Notes/COT5310Notes.pdf</a><br> Dr. Tiplea's Notes: <a href="Notes/COT5310Notes01.pdf">Computability</a>; <a href="Notes/COT5310Notes02.pdf">Decidability</a>; <a href="Notes/COT5310Notes03.pdf">Complexity</a></p> <p><b>Assignments</b>: 7 or so. At least one (the review on prerequisite formal languages and automata) is extensive.</p> <p><b>Exams</b>: 2 midterms and a final.</p> <p><b>Material</b>: I will draw heavily from Davis, Chapters 2-4, parts of 5, 6-8 and 11. Some material will also come from from Hopcroft. Class notes and in-class discussions are, however, comprehensive and cover models and undecidable problems that are not 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 ;-)</p> <p><b>Important Dates:</b> Labor Day, Sept. 3; Exam#1 -- Oct. 1; Withdraw Deadline -- Oct. 12; Exam#2 -- Nov. 7; Veterans Day, Nov. 12; Final -- Wednesday, Dec. 5, 19:00-21:50</p> <p><b>Evaluation (Tentative)</b>:<br> Mid Terms -- 100 points each<br> Final Exam -- 150 points<br> Assignments -- 100 points<br> Bonus -- 50 points added to your best exam<br> Total Available: 500<br> Grading will be  A &gt;= 90%, B+ &gt;= 87%, B &gt;= 80%, C+ &gt;= 77%, C &gt;= 70%, D &gt;= 50%, F &lt; 50%<br> <strong><font color="#FF0C33">NOTE: you must earn a B or better to have this count as a required course.</font></strong><br> <strong>For PhD students, there is no choice, as this is required,<br> MS students can make this an elective, by taking one of COP 5611 or COP 5021 in its place.</strong></p> <hr> <a name="Week1"></a><b>Weeks#1: (8/20, 8/22) -- </b><strong><a href="Notes/COT5310Notes.ppt">Notes</a> pp. 2-38 (Chapter 2 of Davis)</strong> <ol> <li><strong><a href="Notes/Philosophy.html">Philosophy and Goals</a> (Read this; it includes the rules of the game)</strong> <li><strong><a href="Notes/Expectations.html">Expectations</a> (This is what you should know <u>before</u> entering this class)</strong> <li><strong>A review of <a href="Review/Review.html">Formal Languages and Automata</a> by Dr. James Rogers, Earlam College, Indiana;<br> a solid text on this material is </strong><b><em>An Introduction to Formal Languages and Automata</em>, Peter Linz, 4th Edition, Jones &amp; Bartlett, Boston, 2006.</b> <li><strong>Introduction to computability: an historical perspective</strong> <li><strong>Basic terminology: solvable, solved, unsolvable, unsolved, re, non-re</strong> <li><strong>Diagonalization: There are undecidable problems</strong> <li><strong>Teasers</strong> <ul> <li>Does non-determinism always enhance or at worst not diminish the power of a formal system of computation? <li>Is polite C (no goto's or evil loop index modification) diminished if its only loop mechanism is the for-loop? <li>Can we create a programming language that is complete (includes all algorithms) and well-behaved (has no effective procedures that don't halt for some inputs)? </ul> </ol> <blockquote> <p><font color="#ff0000"><b>Assignment #1</b></font></p> <blockquote> <strong><font color="#0066ff"><a href="Assignments/F2007Assignment1_Review.pdf">Take Home Review Exam</a> (<a href="Assignments/F2007Assignment1_Review.doc">word version)</a></font><br> This is a review of COT 4210 material. It serves as a wake up call if you are not familiar with the material and as a gauge for me. Here is a useful review/introduction to regular equations for those who have not seen them before. &lt;<a href="Notes/RegularEquations.html">RegularEquations</a>&gt;</strong></blockquote> <p><b><font color="#ff0000">Due: 10/15 (</font><font color="#0066ff">Key</font><font color="#ff0000">)</font></b></p> </blockquote> <a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a> <hr size="4" width="100%"> <a name="Week2"></a><b>Week#2: (8/27, 8/29) -- Notes</b> <strong>pp. 39-69 </strong><b>(Chapters 2, 3 and 6 of Davis) </b> <ol> <li><strong>Hilbert's Tenth</strong> <li><strong>The need for divergent programs</strong> <li><strong><em>S</em> programs (this is the basic notation used in Davis)</strong> <li><strong>Partial and total computability (relative to <em>S</em>)</strong> <li><strong>Register machines (Shepherdson-Sturgis)</strong> <li><strong>Factor Replacement Systems </strong> <li><strong>Systems related to FRS (Petri Nets, Vector Addition, Abelian Semi-Groups)</strong> <li><strong><a href="Notes/FRS_Petri_VAS_Definitions.pdf">Formal definitions of FRS, Petri Nets and VAS</a>.</strong> </ol> <blockquote> <font color="#ff0000"><b>Operations of an ordered FRS with N rules<br> </b></font><font color="#ff0000"><b>Read x;<br> i=0;<br> while i&lt;N do {<br> i++;<br> if (a[i] divides x) {x = b[i]*x / a[i]; i = 0; }<br> }<br> Print exponent of 2 in x;</b></font>  <p><font color="#ff0000"><b>Assignment #2</b></font></p> <ol> <li type="a"><b>Present a Register Machine that computes FIB. Assume R1=x</b><b>; at termination, set R2=1 if x is a member of the Fibonacci sequence and 0 if not.</b> <li type="a"><b>Present a Factor Replacement System that computes FIB. Assume </b><b>starting number is 3^x 5; at termination, result is 2=2^1 if x is a member of the Fibonacci sequence; </b><b>1= 2^0 otherwise. Actually, it can be done without the 5, but that may make </b><b>it easier.</b> <li type="a"><strong>Prove that non-deterministic FRS's are <u>no more</u> powerful than non-deterministic VAS. This means you need only show that any non-deterministic FRS can be simulated by a non-deterministic VAS.</strong> </ol> <blockquote> <div v:shape="_x0000_s1026"> <div> Note: To do this most effectively, you need to first develop the notion of an instantaneous description (ID) of a FRS (that's a point in 1-space) and of a VAS (that s a point in n-space). You then need a mapping from an FRS ID to a corresponding VAS ID, and this mapping needs to be some function (many-one into), f. Next, there must be a mapping from the rules of the FRS to create those of the VAS, such that a single step of the FRS from x to y is mimicked by some finite number of steps of the VAS from f(x) to f(y), where f(y) is the first ID derived from f(x) that is a mapping from some ID of the VAS.</div> </div> </blockquote> <p><b><font color="#ff0000">Due: 9/10 (</font><font color="#0066ff"><a href="Assignments/COT5310hw2key.pdf">Key</a></font><font color="#ff0000">)</font></b></p> </blockquote> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="15"></a> </p> <hr width="100%"> <a name="Week3"></a><b>Week#3: (9/5)</b> <b>-- </b><b>Notes</b> <strong>pp. 70-102</strong><b> (Chapter 6 and 4 of Davis)</b> <ol> <li><strong>Primitive Recursive Function</strong> <li><strong>Initial functions</strong> <li><strong>Closure under composition and recursion</strong> <li><strong>Addition and multiplication examples</strong> <li><strong>Sample functions and predicates</strong> <li><strong>Closure under cases</strong> <li><strong>Bounded minimization</strong> <li><strong>Arithmetic fuctions that use bounded search</strong> <li><strong>Pairing functions</strong> <li><strong>mu-recursion and the partial recursive functions</strong> </ol> <blockquote> <p><font color="#ff0000"><b>Assignment #3</b></font></p> <blockquote> <div v:shape="_x0000_s1026"> <div> <strong>Show that prfs are closed under mutual recursion. That is, assuming F1, F2 and G1 and G2 are pr, show that H1 and H2 are, where<br> H1(0, x) = F1(x); H2(0, x) = F2(x)<br> H1(y+1, x) = G1(y,x,H2(y,x)); H2(y+1, x) = G2(y,x,H1(y,x))</strong></div> <div> Hint: The pairing function is useful here.</div> </div> </blockquote> <p><b><font color="#ff0000">Due: 9/17 (</font><strong><font color="#0066ff"><a href="Assignments/COT5310hw3key.pdf">Key</a></font></strong><font color="#ff0000">)</font></b></p> </blockquote> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="15"></a></p> <hr width="100%"> <a name="Week4"></a><b>Week#4: (9/10, 9/12)</b> <b>-- </b><b>Notes</b> <strong>pp. 103-117 </strong><b>(Chapter 4 of Davis)</b> <ol> <li><strong>Turing Machines (Greg Tener)</strong> <ul> <li><strong>Post-Turing Machines (this is the basic notation used in Hopcroft)</strong> <li><strong>Examples</strong> <li><strong>Useful submachines</strong> <li><strong>Computing with Turing machines </strong> <li><strong>Non-deterministic Turing machines</strong> <li><strong>Other Turing Machine variations (briefly)</strong> </ul> <li><strong>Complexity Theory (Dr. Dutton)</strong> <ul> <li><strong>Concepts of P and NP </strong> <li><strong>Polynomial (Karp) reducibility </strong> <li><strong>NP Completeness </strong> <ul> <li>In NP and as hard as any other NP problem </ul> <li><strong>NP Hard </strong> <ul> <li>As hard as any other NP problem, but not necessarily in NP </ul> <li><strong>SAT as canonical NP Complete Problem </strong> <ul> <li><a href="http://www.cs.tau.ac.il/%7esafra/Complexity/Cook.ppt">http://www.cs.tau.ac.il/~safra/Complexity/Cook.ppt</a> </ul> <li><strong>Other NP Complete problems </strong> <ul> <li><a href="http://www.cs.tau.ac.il/%7esafra/Complexity/NPC.ppt">http://www.cs.tau.ac.il/~safra/Complexity/NPC.ppt</a> </ul> </ul> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"></a></p> <hr width="100%"> <a name="Week5"></a><b>Week#5: (9/17, 9/19) -- Notes pp. 118-167 (Chapter 4 of Davis)</b> <ol> <li><strong>Relation of S and Register machines</strong> <li><strong>Notions of instantaneous descriptions</strong> <li><strong>Encodings</strong> <li><b>Equivalence of models</b> <li><strong>Universal machines</strong> <li><b>Consequences of equivalence</b> <li><b>Undecidability (Halting Problem, shown by diagonalization)</b> <li><b>Notation matching (mine versus book's)</b> </ol> <blockquote> <p><font color="#ff0000"><b>Assignment #4</b></font></p> <ol type="a"> <li><strong>Present a Turing Machine to do MAX of n non-zero arguments, n&gt;=0. You know you ve run out of arguments when you encounter the value 0, represented by two successive 0's (blanks)<b>. Use the machines we have already built up and others you build. Do </b></strong><b><font color="red"><strong>NOT</strong></font></b><strong><b> turn in Turing Tables. We won't pay any attention to them if you do.</b></strong> <li><b>Show that Turing Machine are closed under iteration (primitive recursion). This completes the equivalence proofs for our five models of computation.</b> <li><b>Constructively (no proof required), show how a standard register machine can simulate a different register machine model with instructions of form:<br> i. if even(r) goto j // goto j if value in register r is even<br> i. r = r+1 // increment contents of r<br> i. r = r-1 // decrement contents of r<br> <font color="#FF0000">Note: all registers except input ones start with 0; inputs are in registers r1, r2,...,rn; output in rn+1</font></b><br> </ol> <p><b><font color="#ff0000">Due: 9/24 (</font><strong><font color="#0066ff">Key</font></strong><font color="#ff0000">)</font></b></p> </blockquote> <a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a> <hr> <a name="Week6"></a><b>Week#6: (9/24, 9/26)</b> <b>-- Notes pp. 168-207 (Chapter 4 of Davis); Review)</b> <ol> <li><b><strong>RE sets and semidecidability</strong></b> <li><b>Enumeration Theorem</b> <li><b><strong><font color="#000000">The set K = { n | n is in the n-th re set } is re, non-recursive</font></strong></b> <li><strong>Alternative characterizations of re sets</strong> <li><b>Parameter Theorem (aka Sm,n Thearem)</b> <li><strong><b>Quantification and re sets</b></strong> <li><strong>Diagonalization revisited (set of algorithms, Ko or Lu, is non-re)</strong> <li><b>Quantification and non-re sets</b> <li><b>Reduction</b> <li><b>Classic sets <strong>Ko</strong> (Lu), NON-EMPTY (Lne), EMPTY (Le</b>) <li><b>Topics and Promises for MidTerm # 1 (see sample questions on pp 191-200)</b> <li><b><a href="Exams/cot5310F07SampleMidterm1.pdf">Sample Exam</a> -- Complete this for discussion on 9/26 (<a href="Exams/cot5310F07SampleMidterm1Key.pdf">key</a>)</b> <li><b>Standard <a href="Exams/Page1ofMidterm1.pdf">page # 1 </a>of exam</b> <li><b>Review for Exam on Monday.</b> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a></p> <hr> <a name="Week7"></a><b>Week#7: (10/1, 10/3) -- Notes</b> <strong>pp. 208-220</strong><b>; Review</b><strong> </strong> <ol> <li><b>Midterm # 1 on Monday, Oct. 1</b> <li><strong>Reducibility and degrees (many-one, one-one, Turing)</strong> <li><strong>Complete re set (K and Ko as examples)</strong> <li><strong>Lr = { x | dom[x] is recursive }</strong> <li><strong>Lnr = { x | dom[x] is not recursive }</strong> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a></p> <hr> <a name="Week8"></a><b>Week#8: (10/8, 10/10)</b> <b>-- </b><b>Notes</b> <strong>pp. 221-239</strong><b> (Chapters 4, 7 and 8 of Davis)</b> <ol> <li><strong>Rice's Theorem</strong> <li><b>&quot;Picture&quot; proofs</b> <li><b>Introduction to rewriting systems (Thue, Post)</b> <li><b>Relation to Group Theory (semi-groups)</b> <li><b>Relation of Abelian Semi-Groups to Unordered Two-Way FRS</b> <li><strong>More on Post Canonical Forms</strong> <li><strong>Semi-Thue systems</strong> <li><strong>Word problems</strong> </ol> <blockquote> <p><font color="#ff0000"><b>Assignment </b></font><font color="#ff0000"><b>#5</b></font></p> <blockquote> <p><strong>1. Let INF = { f | domain(f) is infinite } and NE = { f | there is a y such that f(y) converges}. Show that NE &lt;=m INF. Present the mapping and then explain why it works as desired<br> To do this, define a total recursive function g, such that index f is in NE iff g(f) is in INF. Be sure to address both cases (f in &amp; f not in)<br> 2. Is INF &lt;=m NE? If you say yes, shoow it. If you say no, give a convincing argument that INF is more complex that NE.<br> 3. What, if anything, does Rice s Theorem have to say about the following? In each case explain by either showing that all of Rice s conditions are met or convincingly that at least one is not met.<br> a.) RANGE = { f | there is a g [ range( g ) = domain( f ) ] }<br> b.) PRIMITIVE = { f | f s description uses no unbounded mu operations }<br> c.) FINITE = { f | domain(f) is finite }</strong></p> </blockquote> <b><font color="#ff0000">Due: 10/22 (</font><strong><font color="#0066ff"><a href="Assignments/COT5310hw5key.pdf">Key</a></font></strong><font color="#ff0000">)</font></b> <p><b><font color="#ff0000"><strong>Note: Last Day to Withdraw is 10/12</strong></font></b></p> </blockquote> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a></p> <hr> <p><a name="Week9"></a><b>Week#9: (10/15, 10/17) -- </b><b>Notes</b> <strong>pp. 240-247</strong><b> (Chapter 10, 11, 12 and 18 of Davis)</b></p> <ol> <li><strong>Simulating Turing Machine by Semi-Thue System</strong> <li><strong>Simulating by Thue Systems</strong> <li><b>Formal Languages Revisited</b> <li><b><strong>Regular Languages</strong> </b> <ul> <li><strong>Equivalence of RL, LL, FSL, Reg equations</strong> <li><strong>Myhill-Nerode</strong> <li><strong>Closure under homomorphism and its consequences</strong> </ul> <li><strong><b>Closure and Non-Closure Properties</b></strong> <li><strong>Grammars and re sets</strong> </ol> <blockquote> <p><b><font color="#ff0000"><b>Assignment #6</b></font><font color="#0000FF">  </font></b></p> <blockquote> <p><strong>1. Using reduction from the complement of the Halting Problem, show the undecidability of the problem to determine if an arbitrary partial recursive function, f, has a summation upper bound. This means that there is a M, such that the sum of all values in the range of f (repeats are added in and divergence just adds 0) is &lt;= M.<br> 2. Use one of the versions of Rice s Theorem to show the undecidability of the problem to determine if an arbitrary partial recursive function, f, has a summation upper bound. This means that there is a M, such that the sum of all values in the range of f (repeats are added in and divergence just adds 0) is &lt;= M.<br> 3. Show that given a Semi-Thue, S, you can produce a Post Normal System, NS, such that x =&gt;* y in S iff x =&gt;* y in NS. You must give the construction of NS from S and a justification of why this meets the condition stated above.</strong></p> </blockquote> <p><strong><font color="#ff0000">Due: 10/29 (</font></strong><b><font color="#ff0000"><a href="Assignments/COT5310hw6key.pdf">Key</a></font></strong><font color="#ff0000">)</font></b></p> </blockquote> <a href="#Top"><img src="Images/up.jpg" height="16" width="16"></a> <hr width="100%"> <a name="Week10"></a><b>Week#10: (10/22, 10/24) -- Notes</b> <strong>pp. 248-256</strong><b> </b><strong>(Chapter 12 of Davis)</strong> <ol> <li><b><font color="#0066ff"><a href="Exams/cot5310F07Midterm1Key.pdf">Key for Midterm # 1</a></font></b> <li><strong><strong>Unsolvable problems related to context-free grammars/languages</strong></strong> <li><strong>Post Correspondence Problem</strong> <li><strong>Ambiguity of CFGs </strong> <li><strong>Non-Emptiness of CFL Intersections</strong> <li><strong>Context-Sensitive Grammars and Unsolvability Results</strong> <li><strong>Valid (CSL) and Invalid Traces (CFL)</strong> <li><strong>Intersection and</strong><b> Quotients of CFLs</b> </ol> <a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a><br> <hr> <a name="Week11"></a><b>Week#11: (10/29, 10/31) -- </b><strong><b>Notes</b> <strong>pp. 257-292</strong></strong> <ol> <li><strong>Details on Valid (CSL) and Invalid Traces (CFL)</strong> <li><strong>Intersection of CFLs revisited</strong> <li><b>Quotients of CFLs revisited</b> <li><strong>Type 0 grammars and Traces</strong> <li><strong>L = all string over an alphabet</strong> <li><strong>L=L^2 for L a CFL</strong> </ol> <blockquote> <p><b><font color="#ff0000"><b>Assignment #7</b></font><font color="#0000FF">  </font></b></p> <blockquote> <p><strong>1. Present the description of a PDA (in words) that accepts LA (see page 253 of Notes). You may assume that [i] is a single symbol.<br> 2. Present the description of a PDA (in words) that accepts ~LA (see page 253 of Notes).<br> 3. Use (2) to show that it is undecidable to determine of an arbitrary CFL, L, over the alpabet A, whether or not L = A*.<br> 4. Prove that Post Correspondence Systems over {a} are decidable. </strong></p> </blockquote> <p><strong><font color="#ff0000">Due: 11/14 </font></strong><b><font color="#ff0000">(</font><strong><font color="#0066ff"><a href="Assignments/COT5310hw7key.pdf">Key</a></font></strong><font color="#ff0000">)</font></b></p> </blockquote> <a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a><br> </p> <hr> <a name="Week12"></a><b>Week#12: (11/5, 11/7) -- </b><strong><b>Notes</b> <strong>pp. </strong></strong><b>293-305</b> <ol> <li><b>Topics and Promises for MidTerm # 2</b> <li><strong><b>Midterm # 2 on Wednesday, Nov. 7</b></strong> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"> </a><br> </p> <hr> <p><a name="Week13"></a><b>Week#13: (11/14) -- Notes pp. 306-329</b></p> <ol> <li><strong>Term rewriting systems</strong> <li><strong>Grammars and Biological Systems (Lindenmayer Systems)</strong> <li><b><font color="#0066ff"><a href="Exams/cot5310F07Midterm2Key.pdf">Key for Midterm # 2</a></font></b> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"></a></p> <hr> <p><a name="Week14"></a><b>Week#14: 11/19, 11/21) -- Notes pp. 330-346</b></p> <ol> <li><strong>Revisit Set Real-Time (Constant-Time)</strong> <li><strong>Real-Time and Mortal Machines</strong> <li><strong>Finite Power Problem for CFLs</strong> <li><strong>Rresults on quotient and derivative (Not testable)</strong> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"></a></p> <hr> <p><a name="Week15"></a><b>Week#15: (11/26, 11/28) -- Notes pp. 347-3782; Review</b></p> <ol> <li><strong>Propositional Calculus</strong> <li><strong>First Order Logic</strong> <li><strong>Predicate Calculus</strong> <li><strong>P=NP?</strong> <li> <ul> <li><strong>SAT as canonical NP Complete Problem </strong> <ul> <li><a href="http://www.cs.tau.ac.il/%7esafra/Complexity/Cook.ppt">http://www.cs.tau.ac.il/~safra/Complexity/Cook.ppt</a> </ul> <li><strong>Other NP Complete problems </strong> <ul> <li><a href="http://www.cs.tau.ac.il/%7esafra/Complexity/NPC.ppt">http://www.cs.tau.ac.il/~safra/Complexity/NPC.ppt</a> </ul> </ul> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"></a></p> <hr> <p><a name="Week16"></a><b>Week#16: (12/3) -- Review Notes</b> <strong>pp. 383-408</strong></p> <ol> <li><b>Final Exam Topics and Promises (in Notes)</b> <li><strong><a href="Exams/COT5310F07FinalSamples.pdf">Sample Final</a> (<a href="Exams/COT5310F07FinalSamplesKey.pdf">Key</a>)</strong><b><font color="#ff0000">)</font></b> <li><b>Clean-up (if time permits)</b> <li> <ul> <li type="disc"><strong>Recursion theorem</strong> <li type="disc"><strong>Fixed point Theorem</strong> <li type="disc"><strong>Rice-Shapiro Theorem</strong> <li type="disc"><strong>Minimal Quantification</strong> </ul> <li><b><font color="#ff0000">Wednesday, Dec. 5; 19:00 - 21:50 (7:00PM - 9:50PM</font></b> </ol> <p><a href="#Top"><img src="Images/up.jpg" height="16" width="16"></a></p> <hr> <center> <address><font size="-1"><i>© </i>UCF (Charles E. Hughes), ceh@cs.ucf.edu -- Last Modified December 2, 2007</font></address> </center> </body> </html>