Keys:

 

    1-5:     DDBBE

    6-10:    DDAAD

    11-15:   ABBCD

    16-20:   AADDD

    21-25:   CDDD(C)A

 

     COSC3302                  TEST-2                       4/28/2005

 

 

     NAME__________________________________________________

 

 

     THROUGHOUT THIS TEST, THE FOLLOWING NOTATIONS ARE APPLICABLE:

 

      1. RE:      Recursively Enumerable

      2. PC:      Partially Computable

      3. TM:      Quadruple Turing Machine. (deterministic with 2-way infinite tape)

      4. NDTM:    Nondeterministic quadruple TM

5. S.L.     The Simple Language with the following three BASIC instructions:

                        V = V+1

                        V = V-1

                        IF V <> 0 GOTO L

      6. NPDA     Nondeterministic pushdown automata.

 

     PART-A.   Multiple Choice Questions.            (75 points)

 

1.     Which is a Macro that can be implemented solely by the three instructions in S.L.?

a.     GOTO L

b.     V = 0         and    V = W

c.     V = V1 + V2   and    V = V1 * V2

d.     All.              e.   two.         f.   none.

2.     Which is Solvable?

a.     TM Halting Problem

b.     TM State Problem.

c.     Both.             d.    Neither 

3.     Which is Solvable?

a.     Membership Problem for RE sets.

b.     Membership Problem for Recursive sets.

c.     Both.             d.    neither. 

4.     Which is Computable?

a.     Halt(x,x)

b.     STP(x,y,t)

c.     Both.             d.    neither. 

5.     Which preserves Computable functions?

a.     composition

b.     primitive recursion

c.     unbounded minimalization

d.     all.              e.    two               f.    none 

6.     Which preserves PC Functions?

a.     composition

b.     primitive recursion

c.     unbounded minimalization

d.     all.              e.    two               f.    none 

7.     All TM’s are equivalent to

a.     all RE sets.

b.     All SL programs.

c.     All PC functions.

d.     All.              e.    two.              f.    none. 

8.     RE sets are closed under

a.     Union.

b.     Complementation.

c.     Both.             d.    neither. 

9.     All CFL’s are equivalent to

a.     all NPDA.

b.     All TM’s

c.     All RE sets.

d.     All of above.           e.    two.              f.    none 

10.    Suppose that a family of languages is closed under union and also under intersection. In this case,

a.     it is closed under complementation.

b.     Any proper subset of this family is closed under union.

c.     Both.             d.    neither

11.    Suppose that a family of languages is NOT closed under union and NOT closed under intersection. In this case,

a.     it may or may not be closed under complementation.

b.     Any proper subset of this family is not closed under union.

c.     Both.             d.    neither.  

12.    Suppose that Problem A is reduced to Problem B. In this case,

a.     Problem A is at least as hard as Problem B.

b.     Problem B is at least as hard as Problem A.

c.     Both.             d.    neither.

13.    <3, <2,4>>  is

a.     568

b.     567

c.     neither.

14.    All deterministic quadruple TM’s with 2-way infinite tape are equivalent to

a.     all deterministic quintuple TM’s with 2-way infinite tape.

b.     all non-deterministic quintuple TM’s with 1-way infinite tape.

c.     Both.             d.    neither.

 

 Next three questions are about a TM with the following seven quadruples:

            Q1    B     R     Q2    //Quad-1

            Q2    1     R     Q3    //Quad-2

            Q3    1     R     Q4

            Q4    B     B     Q5

            Q2    B     B     Q5

            Q4    1     R     Q3    //Quad-6

            Q3    B     B     Q3    //Quad-7 

 

15.    Which string is accepted by this TM?

a.     11

b.     1111

c.     111111            d.  all.          e.  two.      f. none

16.    The language accepted by this TM is

a.     {l , 11, 1111, 111111, 11111111, … , infinity}

b.     {11, 1111, 111111, 11111111, … , infinity}

c.     {l ,  111, 111111, 111111111, 111111111111, … , infinity}

d.     none above. 

17.    The purpose of quadruple-7 above is

a.     to not accept the current input string.

b.     to enter an infinite loop thereby accepting the input string.

c.     Both.             d.    neither.

18.    Which is Computable?

a.    f(X1,X2) = X1+X2  and   f(X1,X2) = X1*X2

b.       f(X1,X2) = integer(X1/X2) 

c.       f(X1,X2) = integer(Remainder(X1/X2))

d.       all.              e.    two.              f.    none

    

    

19.    Which is Computable?

a.     P(X1,X2) = whether or not X1 and X2 are the same

b.     P(X1,X2) = whether or not X1 is a divisor of X2

           (like 4 and 8 but not 4 and 9 nor 4 and 10)

             c.   P(X1,X2) = whether their difference is zero or not.

             d.   all.              e.    two.              f.    none.

 

       20.  Which is CF???

            a.    L1 = {bm cn |m,n>=0}

            b.    L2 = {am bn cn dm |m,n>=0}

c.       L3 = {am bm cn dn |m,n>=0}

d.       All.              e.    two.              f.    none

21.  Any CFL without the empty string in it can be represented by

a.    CNF

b.    GNF

c.     Both.                   d.    neither.

 

       Next four questions are about the following CFG:

                  S ->  S   R   S

                  S -> R

                  R ->  P  Q 

                  Q ->  ( )

                  Q ->  ( S )

                  Q ->  P

                  P -> R           // rule-7

                  P ->  l

 

22.  Which string is in the language generated by this CFG?

a.     l    

b.     ( ( ) ) ( ( ) )

c.     ( ( ) ) ( ( ) ) ( )

d.     All.              e.    two.              f.    none.

 23.  Which non-terminal is Nullable?

a.       P

b.       Q

c.       R

d.       All.              e.    two.              f.    none.

    

24.  If rule-7 is eliminated, the resulting equivalent grammar will be

a.   

S ->  S  R  S

S -> S  S

                  S -> R

                  R ->  P  Q

                  R ->  P

Q ->  ( )

                  Q ->  ( S )

                  P ->  l

 

            b.   

S ->  S  R  S

S ->  S  S

                  S -> R

                  R ->  P  Q

                  R ->  Q

                  R ->  P

                  Q ->  ( )

                  Q ->  ( S )

                  P ->  l

 

            c.    both.             d.    neither.

 

      25.   Suppose that the following string is sufficiently long:

 (())(())(())

In this case, which decomposition of this string into five parts will satisfy the CFL Pumping lemma?

a.    u = “(())”              b.    u =  l  

                  v = “(“                       v =  (“

                  w = ”()”                      w =  “()”

                  x = “)”                       x =  )((“

                  y = “(())”                    y = “))(())”

 

            c.    both.                   d.    neither.

 

 

 

     PART-B. Other problems.                   (25 points)

      

      Do three problems in this PART.

 

      A.    L1 = {am bm cm |m >= 0}

            L2 = {am bn cm |m,n>=1}

 

            Prove or disprove that each language above is CF.

 

 

      B.    Give a program which the Predicate HALT(X,X) would contradict.

            And, then describe some key points for that.

 

 

     C.    Give an example language which no deterministic push-down automaton can

accept.

And, then give reasons why that is the case.

 

 

      D.    Design a TM that accepts L = {111, 111111, 111111111,…, infinity}

 

 

 

      E.    List various types of languages along with their characteristics and

            corresponding accepting devices.

            And, indicate cases where determinism and non-determinism do not

coincide and brief reasons of why they do not.

 

F.    Define the Macro:  X=V

in terms of the following:

                  V = V+1

                  V = V-1

                  If (V <> 0) goto L

                  Goto L

                  V = 0

     

            Note that the current value of the righthand side variable, V,

            should not be changed at the end of the instruction.