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

You may turn this in either by e-mail or on-paper

CFG's
1. 	Show that the following grammar is ambiguous:
        S --> AB | aaB
        A --> a | Aa
        B --> b

PDA's
Consider the following pushdown automaton (PDA) M:
(here, d = delta, e = epsilon)

	M = ({q0, q1, q2, q3}, {0, 1}, {Z, X}, d, q0, {q3} )
	with d given by:
		d( q0, e, e) = { (q1, Z) }
		d( q1, 1, e) = { (q1, X) }
		d( q1, 0, X) = { (q2, X) }
		d( q1, e, Z) = { (q3, e) }
		d( q2, 1, X) = { (q2, e) }
		d( q2, 0, Z) = { (q1, Z) }

Consider the string 110110. At some point in the operation of M, above, 
you have the instantaneous description (ID) (q1, 0110, XXZ). 

2.	What will be the instantaneous ID resulting after the next move?

3. 	What will be the instantaneous ID resulting after the move after 
#1's move?

4.	Will the string 110110 be accepted by this PDA? To answer this, 
give the sequence of ID's (separated by |--, as shown in the PDA handout) 
that shows whether it is accepted or not, and then also tell how this 
shows that this string is accepted or not. (Note that a sequence of PDA 
ID's separated by |-- is a kind of derivation, also.)

5.	Give another derivation (using |-- notation, with instantaneous 
descriptions (ID's)) for any string accepted by this PDA. How do you know 
it has been accepted?

6.	Give another derivation for a string containing at least 5 
symbols that would not be accepted by this PDA M. How do you know it has 
been rejected?

Turing Machines
(note --- I am using subscripts in the "formatted" version of this 
assignment, and parentheses around the state names in the "ASCII" version
of this assignment.)
7.   Assume that you have a Turing machine M, which includes set of input 
symbols sigma = {0, 1} and set of states Q = { q0, q1, q2, q3 }. Currently, 
this TM M has the instantaneous description (ID) 0011(q1)0011.

A portion of the next move function d is:
        d( q1, 0 ) = (q2, 0, L)
        d( q1, 1 ) = (q1, 0, R)
        d( q2, 0 ) = (q2, 0, R)
        d( q2, 1 ) = (q1, 0, L)

        (a)   After the next move, what will be the resulting ID?

        (b)   And, after the move after that, what will be the resulting ID?

8.   You have a Turing-recognizable language B, and Turing machine M 
happens to accept B (that is, L(M) = B).
        (a)   You start out M on an input string w, and M has not stopped 
	yet. Assume that you do not know if 
        w is an element of B or not. Can you guarantee that M will 
	eventually halt? Why or why not?

        (b)   You start out M on an input string x, and M has not stopped 
	yet. Assume that you know that x is 
        an element of B. Can you guarantee that M will eventually halt? 
	Why or why not?

9.   You have a Turing-decidable language C, and Turing machine N happens 
to accept C (that is, L(N) = C). You are told, however, that N does not 
halt for some inputs that are not members of C. How can this be?

10.   What two concepts does the Church-Turing thesis suggest should be 
considered equivalent? 

11.   You sketch out a nondeterministic Turing machine that can accept a 
language D. In what class of languages can you now reasonably say that D 
belongs? Why?

12.   You sketch out a multitape Turing machine, guaranteed to halt on 
all possible inputs, that can accept a language E. In what class of 
languages can you now reasonably say the E belongs? Why?