Computer Science 656: Automata and Formal Languages

Spring 2001

Graduate Homework Assignment 2.

Due Wednesday, February 21, 2001

You may discuss this assignment with other students in the class, or other persons. But you must actually write the assignment in your own hand. You must turn in the homework on letter-sized paper, with your name at the top of each page. Use pen or pencil, any color.

Do not type your homework, and do not write your homework as a computer file and turn in a printout.

I will personally grade this assignment.

  1. Define a dynamic bit memory (DBM) machine as follows.
    A machine M is a DBM machine if M's memory consists entirely of bits, and if M can dynamically increase the number of bits of its memory if needed. At the beginning of a calculation, M is "loaded" with a program that occupies some finite number of bits. During each step, M may add more bits to its memory as needed. The input string need not be loaded initially, but is read in one symbol at a time.
    If S(n) is a function, we say that a language L has space complexity S(n) if there is a DBM machine M which accepts L such that the computation of M given any input string w in L of length n uses at most S(n) bits.
    1. Prove that if the space complexity of L1 is S1(n) and the space complexity of L2 is S2(n), then the space complexity of L1+L2 is no greater than S1(n)+S2(n)+5.
    2. Prove that the space complexity of any regular language is finite.
    3. Compute the asymptotic space complexity of the language {anbn}.
  2. Turn this problem in next Wednesday, after we have covered PDA's. Let M be a PDA. Let Lstack(M) be the set of strings which could occur as the stack contents of M during any computation.
    Prove that Lstack is regular.

Back to Course Page