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.
-
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.
-
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.
-
Prove that the space complexity of any regular language is
finite.
-
Compute the asymptotic space complexity of the language
{anbn}.
-
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