Homework 3

15-212 Java, Spring 1998

February 4, 1998
Instructors: Mosur and Tygar

This assignment is due at start of your section on February 11. Please read the class policies for collaboration, cheating, and late assignments. Answers that are unclear, illegible, rambling, or otherwise annoying will receive no credit. The best answer is the shortest correct answer.

IMPORTANT: Same as assigment 2. You must hand in each part separately, so do each part on separate pieces of paper. Put your name, your section, and the part number at the top of the first page of each part.

Part I: Review

1. Say L₁ and L₂ are regular languages. Is L'={w : w is in L₁ but not in L₂} necessarily regular? Why or why not?

2. In proving that a DFA is as powerful as an NFA, we started with an n-state NFA and constructed an equivalent DFA with 2ⁿ states. In this problem you will prove that in general, there is no more concise way to deterministically simulate a NFA.

Consider the language L = { w=(a,b)* : the n^th symbol from the right end of w is an a}. Prove:

There is an n+1-state NFA that accepts L.
There is no DFA which accepts L and has fewer than 2ⁿ states. (Hint: Use the pigeonhole principle.)

Part II: Turing Machines and Recursive Languages

3. The stack of a pushdown automaton can be considered as a tape that can be written and erased only at one end. In this sense a Turing machine is a generalization of a pushdown automaton. But we can generalize in the other direction as well, by considering a pushdown automaton with two stacks. Using a simulation argument, show that a two-stack dpda is just as powerful as a Turing machine. (We are looking for a clear but informal explanation, rather than an explicit, state by state machine specification.)

4. A linear-bounded automaton (LBA) is a type of Turing machine where the tape head isn't allowed to move off the part of the tape containing the input. All the "regular" rules still apply; in particular, the alphabet of the LBA is finite.

Let M be an LBA with q states and g symbols in the tape alphabet. How many configurations of M are there, for a tape of length n?
Is L={ (M,w) : M is an LBA that accepts string w} decidable? Why or why not?

Part III: To infinity...and beyond

5. Flavors of infinity. As discussed in class, a countably infinite set is one which can be put in a one-to-one correspondence with the natural numbers. Prove that

The union of two countably infinite sets is countably infinite.
The union of countably many countably infinite sets is countably infinite.

A graphical proof is encouraged.

6. One cannot write a program to decide the halting problem on all Java programs less than n characters long, for a fixed value of n. True or false? Substantiate your answer.