Date: Wed, 08 Jan 1997 20:45:22 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 2 Solution Set Friday, January 19, 1996



next up previous
Next: About this document

CSE 322 Assignment 2 Solution Set Friday, January 19, 1996

  1. Prove that for all .

    We can prove this by induction on i:

    Basis: The statement is true for i = 0 because for any x and so

    Inductive hypothesis: Assume that the statement is true for i=k:

    Inductive step: From this we need to show it is true for i=k+1:

    By induction, the statement is true for all .

  2. Regular expressions
    1. The set of strings over that contain the substring aa exactly once:

    2. The set of strings over that do not contain the substring aa:

    3. The set of strings over where the total number of a's and b's is 3:

  3. Consider the equation:

    where A and B are fixed sets and X is a set variable. Assume that B is not empty.

    1. Argue that is a solution to the equation.

      To do this, we verify that below:

    2. Argue that if X solves the equation, then .

      Let X be a solution to the equation. One way of proving that is by showing that for any . Intuitively, we can see this by substituting for X into the equation a few times:

      First we notice that = X, so it must be true that . Similarly, after the first substitution we can say that , so . Thus, for any i we can apply i substitutions to get . The union of these is also a subset of X, so

      The answer above is all I really wanted, although to be truly formal we should prove that for all by induction:

      Basis: We know that from above. Inductive hypothesis: Assume for some . Inductive step: From the inductive hypothesis, we know that . This means there must be some Y where . Substituting this into the equation we get . From this we can see that that .

      Therefore, for all .





next up previous
Next: About this document



James Fix
Mon Jan 29 18:15:01 PST 1996