| Formal Languages and Automata Theory Fall 2007 |
email: ceh@cs.ucf.edu
Structure: MW 19:30-20:45 (7:30PM - 8:45PM), HEC-103; 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, 16
Instructor: Charles Hughes; Harris Engineering Center 439C; 823-2762; ceh@cs.ucf.edu
Office Hours: MW 17:00-18:15 (5:00PM - 6:15PM)
GTA: Greg Tener, TTh 18:30-19:30 (6:30PM - 7:30PM) in HEC 365
Text: There will be no required text. I will use extensive notes.
Primary Reference: Davis, Sigal and Weyuker, Computability, Complexity and Languages 2nd Ed., Academic Press (Morgan Kaufmann), 1994.
Secondary References: Hopcroft, Motwani and Ullman, Introduction to Automata Theory, Languages and Computation 2nd Ed., Addison-Wesley, 2001.
Papadimitriou and Lewis, Elements of the Theory of Computation, Prentice-Hall, 1997.
Prerequisites: COP 4020 (Covers parsing and some semantic models); COT 4210 (covers regular and context free languages)
Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cot5310/
Notes URL: http://www.cs.ucf.edu/courses/cot5310/Notes/COT5310Notes.ppt; or
http://www.cs.ucf.edu/courses/cot5310/Notes/COT5310Notes.pdf
Dr. Tiplea's Notes: Computability; Decidability; Complexity
Assignments: 7 or so. At least one (the review on prerequisite formal languages and automata) is extensive.
Exams: 2 midterms and a final.
Material: 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 ;-)
Important Dates: 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
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%
NOTE: you must earn a B or better to have this count as a required course.
For PhD students, there is no choice, as this is required,
MS students can make this an elective, by taking one of COP 5611 or COP 5021 in its place.
Assignment #1
Take Home Review Exam (word version)
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. <RegularEquations>Due: 10/15 (Key)
Operations of an ordered FRS with N rules
Read x;
i=0;
while i<N do {
i++;
if (a[i] divides x) {x = b[i]*x / a[i]; i = 0; }
}
Print exponent of 2 in x;Assignment #2
- Present a Register Machine that computes FIB. Assume R1=x; at termination, set R2=1 if x is a member of the Fibonacci sequence and 0 if not.
- Present a Factor Replacement System that computes FIB. Assume starting number is 3^x 5; at termination, result is 2=2^1 if x is a member of the Fibonacci sequence; 1= 2^0 otherwise. Actually, it can be done without the 5, but that may make it easier.
- Prove that non-deterministic FRS's are no more powerful than non-deterministic VAS. This means you need only show that any non-deterministic FRS can be simulated by a non-deterministic VAS.
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.Due: 9/10 (Key)
Assignment #3
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
H1(0, x) = F1(x); H2(0, x) = F2(x)
H1(y+1, x) = G1(y,x,H2(y,x)); H2(y+1, x) = G2(y,x,H1(y,x))Hint: The pairing function is useful here.Due: 9/17 (Key)
Assignment #4
- Present a Turing Machine to do MAX of n non-zero arguments, n>=0. You know you’ve run out of arguments when you encounter the value 0, represented by two successive 0's (blanks). Use the machines we have already built up and others you build. Do NOT turn in Turing Tables. We won't pay any attention to them if you do.
- Show that Turing Machine are closed under iteration (primitive recursion). This completes the equivalence proofs for our five models of computation.
- Constructively (no proof required), show how a standard register machine can simulate a different register machine model with instructions of form:
i. if even(r) goto j // goto j if value in register r is even
i. r = r+1 // increment contents of r
i. r = r-1 // decrement contents of r
Note: all registers except input ones start with 0; inputs are in registers r1, r2,...,rn; output in rn+1
Due: 9/24 (Key)
Assignment #5
Due: 10/22 (Key)1. Let INF = { f | domain(f) is infinite } and NE = { f | there is a y such that f(y) converges}. Show that NE <=m INF. Present the mapping and then explain why it works as desired
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 & f not in)
2. Is INF <=m NE? If you say yes, shoow it. If you say no, give a convincing argument that INF is more complex that NE.
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.
a.) RANGE = { f | there is a g [ range( g ) = domain( f ) ] }
b.) PRIMITIVE = { f | f’s description uses no unbounded mu operations }
c.) FINITE = { f | domain(f) is finite }Note: Last Day to Withdraw is 10/12
Week#9: (10/15, 10/17) -- Notes pp. 240-247 (Chapter 10, 11, 12 and 18 of Davis)
Assignment #6
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 <= M.
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 <= M.
3. Show that given a Semi-Thue, S, you can produce a Post Normal System, NS, such that x =>* y in S iff x =>* y in NS. You must give the construction of NS from S and a justification of why this meets the condition stated above.Due: 10/29 (Key)
Assignment #7
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.
2. Present the description of a PDA (in words) that accepts ~LA (see page 253 of Notes).
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*.
4. Prove that Post Correspondence Systems over {a} are decidable.Due: 11/14 (Key)
Week#13: (11/14) -- Notes pp. 306-329
Week#14: 11/19, 11/21) -- Notes pp. 330-346
Week#15: (11/26, 11/28) -- Notes pp. 347-3782; Review
Week#16: (12/3) -- Review Notes pp. 383-408