Homepage for CSCE 551
Theory of Computation
Spring 2008

This site is subject to update through the term. This page was last modified Wednesday May 7, 2008 at 15:43:25 EDT.

Time: MW 5:30 - 6:45
Place: Swearingen 1A20
Syllabus

Announcements

I will post announcements here from time to time.

(5/7/2008) I curved the final scores for the semester by linearly squeezing them accordion-style toward 100%, leaving 100% fixed so that the median became 80% (the uncurved median was 68%). So if your uncurved score is s with 0 ≤ s ≤ 1, then your curved score is given by


c = 1 - (1 - s)(1 - 0.8)/(1 - m),

where m is the uncurved median (about 0.68).

(5/7/2008) Here is the ANSWER KEY to the final exam.

(4/25/2008) Here are some final exam-related items:

(4/9/2008) Here are the answers to Midterm II (except for Question 1.

(4/1/2008) My office hours tomorrow (Wednesday 4/2) will start at 3:45 instead of 3:00. The colloquium will be from 2:30 to 3:30 in the Faculty lounge (Swearingen).

(2/13/2008) Today's midterm will not cover nonregular languages or the pumping lemma. It will also not cover state distinguishability, minimum DFAs or the Myhill-Nerode theorem.

(2/12/2008) Solutions to selected exercises are in an envelope outside my office door. Come by any time to pick one up (one sheet).

(2/6/2008) For the last problem on the first homework (due 1/23/2008), many of you offered the following solution:


b = ∪[∪(a,b) - ∩(a,b)].

This is almost correct. It is only incorrect when a = b ≠ ∅.   If a = b, then

∪(a,b) = {a,b} = {a} = ∩(a,b),

and thus the set inside the brackets is ∅, and you then get ∪∅ = ∅ for the whole right-hand side.

(1/28/2008) Some people viewing this page with Internet Exploder have had trouble viewing the mathematical symbols. I suggest using Firefox or Safari. (I generally avoid using IE on principle.) Alternatively, people have copied/pasted the HTML text into an MS Word document, where it appears to read just fine.

(1/28/2008) Change in the Syllabus. I do not have a grader for this class, so I will not have time to grade assignments. This means that homework does not count for credit. The 20% of the grade for the homework has been redistributed to the exams (midterms are now 25% each, and the final is 50%.) I will continue to assign homeworks, and I will post solutions to many of the exercises so you can get some of the benefit of a graded homework.

(1/16/2008) NEW CLASSROOM! Starting today we are moving from 1A20 to 2A19, which can accommodate more students. (The original classroom was chosen based on faulty enrollment information.) This is a traditional, non-APOGEE classroom (the APOGEE section was dropped, having zero enrollment).

(1/14/2008) Check the Course Syllabus for general information about the course.

Supporting Materials

Past Exams

Course Notes

Homework

Any exercise or list of exercises in the scope of (GRAD &hellip GRAD) are meant for graduate students. Graduate students must do these exercises for full credit, but undergrads may do them as well for extra credit.

Exercises will generally be due twice a week: on Mondays and Thursdays.

Due 1/23/2008:

  1. Text Chapter 0: Exercises 0.1 - 0.9; Problems 0.10 - 0.14. In other words, do (or at least attempt) all exercises in Chapter 0. This chapter builds up and tests your mathematical maturity, i.e., your level of comfort with the various objects and methods of mathematics -- basic logic, sets, relations, functions, etc., as well as definitions, theorems, and proofs. Mathematical maturity is the strongest indicator of success in this course.

    NOTA BENE: Any exercise appearing with an `A' before its number has a solution in the text. You should try working it first before looking at the solution. You'll appreciate the solution a lot more that way.

  2. More Fun with Sets. To a set theorist, everything is a set. In fact, all of mathematics can be cast within set theory, that is, all mathematical objects, definitions, theorems, etc. in math can be formulated as sets and statements about sets. Even objects that we often consider "primitive"---such as natural numbers, ordered pairs, functions, relations, geometric objects, etc.---can be defined in terms of sets. The natural numbers are defined inductively as follows:
    0 = {} = ∅,
    1 = {0},
    2 = {0,1},
    3 = {0,1,2},
    ⋅⋅⋅
    n = {0,1,2,&hellip,n-1},
    n+1 = n ∪ {n} = {0,1,2,&hellip,n},
    ⋅⋅⋅
    The nice thing about this definition is that the member-of relation (∈) is the same as the less-than relation ( < ).

    If x and y are objects, then the ordered pair (x,y) is defined as


    (x,y) = {{x},{x,y}}.

    This encodes x and y into a single object from which x and y can be recovered.

    In the questions below, we'll assume that every mathematical object is a set.

    1. Using just curly braces and commas, write out full expressions for the natural numbers 0, 1, 2, and 3, above as sets. (So you must represent the empty set as {}, for example.)
    2. (GRAD Building on the previous problem, can you determine, for any natural number n, how many braces you must use to fully express n as above? How many commas do you need? Can you prove your answer? GRAD)
    3. Recall that if X is a set, then ∪ X is the union of all elements of X. That is,

      ∪ X = { z : (∃ y ∈ X) z ∈ y }.

      Also, if X is not empty, then ∩ X is the intersection of all elements of X. That is,

      ∩ X = { z : (∀ y ∈ X) z ∈ y }.

      Let X = {{3,7,9,10},{2,3,4,7,12},{3,6,7,11}}. Find ∪ X and ∩ X.

    4. Give alternate forms for the expressions ∪{A,B} and ∩{A,B}. (A and B are arbitrary sets.)
    5. What are ∪∅ and ∩∅?
    6. Let x be any set. What is ∪{x}? What is ∩{x}?
    7. Let a and b be any sets, and recall that (a,b) is defined as {{a},{a,b}}. What is ∪(a,b)? What is ∩(a,b)?
    8. Show how to recover a from the pair (a,b) by giving an equation of the form,
      a = (some expression involving just the pair (a,b)),
      where your expression uses only the set-theoretic operations ∪ and ∩ used in their unary prefix form. (Remember that a and b are sets.)
    9. (GRAD Show how to recover b from the pair (a,b) by giving an equation of the form,
      b = (some expression involving just the pair (a,b)),
      where your expression uses only the set-theoretic operations ∪ and ∩, used in unary or binary form, and the the relative complement operation - in its binary infix form. Remember that a and b are sets. (This one is harder than the last one.) GRAD)

Due 2/11/2008:

  1. Text Chapter 1: Exercises 1.1, 1.2, 1.4(a,b,d,g), 1.5(a,b,d), 1.6(a,g,i,n), 1.7(f,g), 1.11, 1.14(b), 1.16(a), 1.18(i), 1.19(b), 1.20(b,h), 1.21(a), 1.22(a), 1.28(c), 1.29(c).
    (GRAD 1.31, 1.32, 1.40, 1.46(b), 1.48, 1.62).
  2. The problems below are challenging and sometime raise interesting issues that we will discuss in class. They all establish various closure properties of regular languages. For all these problems, we assume a fixed alphabet Σ.
    1. Given two strings x,y∈Σ*, we say that x is a subsequence of y if x results from y by removing zero or more symbols. That is, if x = x1⋅⋅⋅ xm and y = y1⋅⋅⋅ yn and there exist 1 ≤ i1 < i2 < ⋅⋅⋅ < im ≤ n such that xj = yij for all 1 ≤ j ≤ m. For any language L, define SUBSEQ(L) to be the language of all subsequences of strings in L. Show that if L is regular, then so is SUBSEQ(L). (Actually it is known, by a nonconstructive proof, that SUBSEQ(L) is regular for any L.)
    2. Given two languages L1 and L2 over Σ, define the "quotient" language

      L1/L2 = { x ∈ Σ* : (∃ y ∈ L2) xy ∈ L1 }.

      Show that if L1 is regular (and L2 is arbitrary!), then L1/L2 is regular. [Hint: Given a DFA A for L1, define a DFA A' for L1/L2, where A' has all the same components as A (state set, alphabet, transition function, start state) except a possibly different set of final states.]
    3. For two strings x = x1 ⋅⋅⋅ xn and y = y1 ⋅⋅⋅ yn of the same length, define the interleave of x and y to be

      x#y = x1y1x2y2 ⋅⋅⋅ xnyn,

      and given two languages L1 and L2 define

      L1#L2 = { x#y : x ∈ L1 ∧ y ∈ L2 ∧ |x| = |y| }.

      Show that if L1 and L2 are regular, then L1#L2 is regular.
    4. Given a language L over Σ, define

      L/2 = { x ∈ Σ* : (∃ y) |y| = |x| ∧ xy ∈ L }.

      Show that if L is regular then L/2 is regular.
    5. For any language L and integer k ≥ 1, define L1/k to be the language of all strings x such that xk ∈ L (here, xk is just xx ⋅⋅⋅ x  k times). So for example, L1/1 = L, and L1/2 consists of all x such that xx ∈ L. Show that if L is regular, then L1/2 is regular. [Hint: given an n-state DFA recognizing L, construct an nn-state DFA recognizing L1/2.]
    6. Show that if L is regular, then L1/k is regular, for any k ≥ 1. [The previous hint also applies here.]
    7. Given a language L, define L1/* to be the union of all the L1/k for k = 1,2,3,&hellip. Show that if L is regular, then L1/* is regular. [Same hint.]

Due 3/7/2008:

  1. Text Chapters 3 and 4: Ex. 3.1(b,c), 3.4, 3.5(a,b,c,d), 3.6, 3.7, 3.8(b), 3.10, 3.13, 3.15(a,d,e), 3.22, 4.1, 4.2, 4.3, 4.5, (GRAD 3.12, 3.16(a,b,c,d)).
  2. Give implementation-level descriptions of two multitape TMs M1 and M2 such that (i) M1 takes a string over {0,1} representing a natural number n in binary and outputs (on another tape) the unary string 1n, and (ii) M2 takes as input a string 1n and outputs on another tape the binary representation of n. Each machine may use any fixed number of extra tapes.
  3. (GRAD This problem is optional. It is a variant of Exercise 3.20. Assume that M is a normal one-tape Turing machine, except that (i) on input w, the left portion of the tape initially contains $w$, where "$" is a special end marker symbol not in the input alphabet, and (ii) the machine is not allowed to write (change any symbols) anywhere in $w$ during the computation. (M is allowed to do anything it wants in the initially blank portion of the tape to the right.) Show that such a machine can only recognize a regular language.

    [Hint: Since M can easily move from one end marker to the other, we can assume WLOG that the tape head starts on the right end marker instead of the left. Fix an input w of length n, so that the left end marker is in cell 0 and the head is initially scanning the right end marker in cell n+1. For any i ≤ n, suppose that at some time step t, the head moves left from cell i+1 into cell i while entering some state q, and then at some later time t', the head moves right again from cell i to cell i+1 (for the first time since time t) and enters some state r. Note that the state r only depends on the state q (and the input w) and not on the time, since the cells j never change for any j ≤ i. Thus we can define a mapping from the states of M to the states of M based on this behavior, i.e., the mapping that sends any given state q to the corresponding r. (There's an exceptional case to consider: what if M's head never returns to cell i+1 after moving left into cell i and entering state q? In this case, q maps to one of the two halting states of M as appropriate.) Such a mapping is called a crossing sequence at cell i. Note that the set of all possible state-to-state mappings is finite and only depends on M and not on w. Note also that the total behavior of M on input w depends only on M itself and the crossing sequence at cell n, and is otherwise independent of w.

    Now here's your job:
    Define a DFA A whose states include all mappings from the state set of M into the state set of M. Show that, for any cell 0 < i ≤ n, the crossing sequence at cell i only depends on the crossing sequence of cell i-1 and the contents of cell i (show what this dependence is explicitly). Use this fact to define a transition function for A, so that as A reads w from left to right, when reading the ith symbol of w, the state of A goes from the crossing sequence at cell i-1 to the crossing sequence at cell i. Make the start state of A to be the crossing sequence at cell 0 (this is clearly independent of w). What should the final states of A be??? This set is easy to define, although there is no general way of computing what it is for arbitrary M. Explain your definition of A.] )

Due 3/31/2008:

  1. High-level descriptions of algorithms suffice for all these problems: Text Ex. 4.11, 4.12, 4.16, (GRAD 4.17, 4.18), 4.28, 5.4, 5.5, 5.6, 5.7, 5.9, 5.12, 5.16, 5.22, (OPTIONAL 5.26, 5.31).
  2. (GRAD Let B be any language and define B' = ATMB to be the set of all < M,w > where M is an OTM and MB accepts w. B' is called the Turing jump of B. Show that B ≤ m B' for every B. (By essentially the same proof that ATM is undecidable, one can show that B' is never Turing-reducible to B.))
  3. (OPTIONAL Recall that FINTM is the language of all < M > such that M is a TM and L(M) is finite. Define COFTM ("COF" means "cofinite") to be the language of all < M > such that M is a TM and L(M) contains all but a finite number of strings (that is, there are at most a finite number of strings not accepted by M).
    1. Show that FINTM ≤m COFTM.
    2. Show that FINTM ≤m the complement of COFTM.)

Due 4/28/2008:

  1. Text Exercises 7.1(a-f), 7.5, 7.9, 7.11, 7.12, 7.16, 7.17, 7.19, 7.21, 7.22 (OPTIONAL and FUN 7.30, 7.31), (GRAD 7.36, 7.37, 7.41)
  2. Text Exercises 8.1, 8.3, 8.6, 8.8, 8.9, 8.13, 8.17 (GRAD 8.12, 8.18), (OPTIONAL 8.24).
  3. Show that P and PSPACE are closed under union and complement, and that NP is closed under union and intersection.

This page last modified Wednesday May 7, 2008 at 15:43:25 EDT.