COCS5315                                             Test-2                                                                     12/18/2005.

 

                In this test, the following notations are used:

 

                1. $:                         Universal Quantifier.

                2. %:                       Existential quantifier.

                3. ^:                         Conjunction operator. (AND)

                4. +:                         Disjunction operator. (OR)

                5. ~:                         Negation operator. (NOT)

                6. ->:                       Implication operator (IMPLIES)

                7. V,W,X,Y,Z:        A variable.

                8. a,b,c:                   A constant.

                9. f,g,h:                   A function.

             10. P,Q,R,S:               A predicate Symbol.

             11. l:                          The Empty-symbol

               

 

                Name (PRINT)_______________________________________

 

                PART-A.               Multiple Choice questions                                                 (88 points)

 

                For each question in this PART-A, write down a big A,B,C,D,E, or F (in capital) precisely next to

each question number and nowhere else.

 

                The first six questions are about the following quadruple TM of nine quadruples.

Note that this TM, M,  has 4 states, q1, q2, q3, and q4, on the alphabet, {a,b},

and the only accepting combination is (q4, B).

 

                                N1:          q1            B             R             q2

                                N2:          q2            a              R             q3

                                N3:          q3            b              R             q3

                                N4:          q3            a              R             q4

                                N5:          q4            a              a              q4

                                N6:          q4            b              b              q4

                                N7:          q2            b              b              q2

                                N8:          q2            B             B             q2

                                N9:          q3            B             B             q3

 

                1.             Which production is included in the equivalent  W(M)?

                                a.             a  q3  b   ->   q2  a  b              

                                b.             a  q3  B  h   ->  q2  a  h

                                c.             q5  B       ->   q4  B

                                d.             All.                                          e.             Two.                       f.              None

 

2.                    Which production is included in the equivalent  S(M)?

a.             q0  B   ->  q0

b.             q3  a    ->  q4  a

c.             q1  B  b  ->  B  q2  b

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

 

                For the next three questions, assume that the following is the input string:            

                                                a b a

3.             In this case, which Post Word can be derived by the equivalent S(M)?

                a.             h B q2 a b a h

                b.             h B a b a q4 B h

                c.             h q0 h

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

 

4.             In this case, which Post Word can be derived by the equivalent grammar?

                                a.             h   b  b  b   q0  h

                                b.             h   q0  h

                                c.             h   b  b  b  q5 a  a   h

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

 

5.               In this case, which string can be derived by the equivalent grammar?

a.                    h  q5 a  b  a  h

b.                   h  a  b  a  q5 h

c.                    a b b b b a                                             

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

 

6.             Which string is accepted by this TM?

                                a.             a  a

                                b.             a  b  a

                                c.             a  b  b  a

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

 

                Next three questions are about a S.T. P (Semi-Thue Process) on the alphabet {a} with the following

six productions:                    aa  ->                      aaa                          // p-1

                                                                aaa ->                     aaaaa                      // p-2

                                                                aaaa ->                   aaaaaa                    // p-3

                                                                aaaa ->                   aaa                          // p-4

                                                                aaaaa ->                 aaaa                        // p-5

                                                                aaa ->                     a                              // p-6

 

                7.             Which production can be eliminated without changing possible derivations?

                                a.             p-1  alone

                                b.             p-2  alone

                                c.             p-3  alone                               d.   All                    e.  Two                   f.  None.

                8.             Which derivation is possible?

                                a.             aa -> aaa

                                b.             aa -> aaaa

                                c.             a   ->  aaaaaa                         d.   All.                   e.  Two.                  f.  None

                9.             Which production can be eliminated without changing possible derivations?

                                a.             p-4 alone

                                b.             p-6 alone

                                c.             both p-4 and p-5                   d.   all.                     e.  two.                   f. none.

 

                Next four questions are about the following CFG (Context-Free Grammar):

                                S -> P  a  Q

                                S -> R  S

                                S ->  b  P  b

                                R -> T  T

                                T ->  T  Q

                                T ->  P  Q

                                P  ->  Q  S  Q

                                P ->  Q

                                Q ->  l  

                                Q ->  P  b  Q         

 

10.             Which non-terminal is Nullable?

a.        Q  and  P

b.       T  and  R                                        c.  both.                                  d.  neither.

 

11.             Which is an implicit (implied) Unit-Production Rule?

a.        T  ->  Q

b.       T  ->  P

c.        S  ->  R                           d.  all.                      e.  two.                   f.  none.

 

12.             Which production rule is to be added to this grammar as a result of eliminating empty-      

               production-rule?

a.        S ->  a  Q

b.       S ->  P  a

c.        Q ->  b  Q                       d.  all above.          e.  two.                   f.  none above.

 

13.           Which production rule is to be added to this grammar as a result of eliminating Unit

                production rule(s)?

a.        S -> Q  a  Q

b.       S -> P  a   P

c.        S -> b  Q  b 

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

 

                14.           Which pair is equivalent?

                                a.     All NFSA’s and all DFSA’s

                                b.     All TM’s without any accepting state and all TM’s with one or more accepting states.

                                c.     All  NPDA’s and all DCFL’s

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

               

15.           Which is solvable?

                                a.             deciding whether or not an arbitrary CSL is accepted by a non-deterministic LBA.

                                b.             deciding whether or not an arbitrary grammar defines a type-0 language.

                                c.             deciding whether or not an arbitrary grammar defines a non-empty language.

                                d.             All.                                          e.             Two.                       f.              None.

               

16.           Which is solvable for an arbitrary grammar G where u and v are each an arbitrary string of

grammar symbols?

                                a.             u -> v      (exactly one step derivation)

b.                   deciding whether or not L(G) includes a sentence of  length at least k where k is a given positive integer.

                                c.             deciding whether or not L(G) includes an arbitrary string of terminals.

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

 

17.        Which WFF’s are equivalent?

a.                    $X$Y(P(X)+Q(Y))

b.                   $X(P(X))+ $Y(Q(Y))

c.                    $Y$X(P(X)+Q(Y))

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

 

18.        Which WFF’s are equivalent?

a.        %X%Y(P(X)^Q(Y))

b.       %X(P(X)) ^  %Y(Q(Y))

c.        %Y%X(P(X)^Q(Y))                     

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

 

19.        Which WFF is valid?

a.     $X$Y$Z  ((P(X)->Q(Y))^(Q(Y)->R(Z)) -> (P(X)->R(Z)))

b.        $Y%X (P(X,Y)) ->  %X$Y (P(X,Y))

c.         %X$Y (P(X,Y)) ->  $Y%X (P(X,Y))

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

 

20.            Which WFF is unsatisfiable?

a.        $X(P(X)) ^ ~P(a)

b.       %X$Y(P(X,Y)) ^ %Y$X (~(P(X,Y)))

c.        both.                                               d.             neither.

 

21.            Which WFF is stronger?

a.        $X(P(X)+Q(X))

b.       $X(P(X))+$X(Q(X))

c.        neither.                                           d.             cannot tell. 

 

$X%Y (P(X)+Q(X) -> R(Y))

22.             Which clause is included in the above WFF ?

a.        ~P(X)+R(a)

b.       ~Q(X)+R(f(X))

c.        ~P(X)^~Q(X) + R(Y)                    d.  all.                      e.  two.                   f.  none.

 

 

                PART-B.               Other problems                                                                   (12 points)

 

                Do two problems.

 

                A.            Consider the following PCP problem.

                                                baba       aba

                                                ba            baa

                                                abab       baba

 

                                Do you think that this PCP instance has a solution.  Be specific about your reasons.

                                If there is a solution, prove and show it.

 

                B.            Give all clauses for:              $X$Y%Z ((P(X)^R(Z))->(S(Y)^Q(Z)))

 

 

C.                   Prove each is a CFL.

a.             { am bm cn  |  m,n.>=1 }                

b.             { am bn cn  |  m,n.>=1 }

c.             { am bn cn dm   |  m,n.>=1 }

 

D.                  Give two CFL’s whose intersection is not CF.

And, show that it is indeed not CF.