CIS 480 - Computer Theory - Spring 2000
HOMEWORK #6
DUE: Wednesday, April 5th, Beginning of Class

If you think you can clearly type your responses in ASCII, you may e-mail 
this in --- otherwise, turn it in on-paper.
For problems/languages with subscripts in their names, in the
ASCII version I am writing those subscripts as lower-case letters ---
thus, for the problem of whether a given TM accepts a given string,
that's the language we've called Atm. 

1.	For each of the following languages, state the problem that the 
language is representing.
	(a) ALLdfa = {<A> | A is a DFA that recognizes E*}
                               (E = sigma, above) 

	(b) INFINITEcfg = {<G> | L(G) is an infinite language}

	(c) SUB = {<M, N> | M and N are TM's and L(M) is a proper 
                            subset of L(N)}

2.	For each of the following problems, give a language that can 
	represent the problem.
	(a) Does a TM accept the empty string (e)? (e=epsilon)

	(b) Are a CFG and PDA equivalent? (Is the language generated by a 
	CFG the same as that accepted by a PDA?)

	(c) Does a PDA accept any strings?

3.   You sketch out a nondeterministic Turing machine that can accept a 
language D. 

        (a)   In what class of languages can you now reasonably say that 
	D belongs?

        (b)   It turns out that there is a problem P corresponding to 
	this language D. Given what you know  
        about D, what can you say about P? (I can think of several 
	reasonable answers to this question you 
        only need to give one.)

4.   You sketch out a multitape Turing machine, guaranteed to halt on all 
possible inputs, that can accept a language E. 

        (a)   In what class of languages can you now reasonably say that 
	E belongs?

        (b)   It turns out there is a problem Q corresponding to this 
	language E. Given what you know about 
        E, what can you say about Q? (I can think of several reasonable 
	answers to this questionyou only 
        need to give one.)