Loading

SET 4


  Question 1

Let A be a problem that belongs to the class NP. Then which one of the following is TRUE?

A : There is no polynomial time algorithm for A
B : If A can be solved deterministically in polynomial time,then P = NP
C : If A is NP-hard, then it is NP-complete
D : A may be undecidable


  •  
    .

     Correct answer is :C

     Solution :
      If a problem is both NP hard and NP, then it is NP Complete.

  •   Question 2

    Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

    A : The set of all strings containing the substring 00.
    B : The set of all strings containing at most two 0s
    C : The set of all strings containing at least two 0s.
    D : The set of all strings that begin and end with either 0 or 1.


  •  
    .

     Correct answer is :C

     Solution :
      The regular expression has two 0?s surrounded by (0+1)* which means accepted strings must have at least 2 0?s.

  •   Question 3

    Which one of the following is FALSE?

    A : There is unique minimal DFA for every regular language
    B : Every NFA can be converted to an equivalent PDA
    C : Complement of every context-free language is recursive
    D : Every nondeterministic PDA can be converted to an equivalent deterministic PDA.


  •  
    .

     Correct answer is :D

     Solution :
      Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.

  •   Question 4

    Let 1 2 L = L I L , where L1 ∩ L2 are languages as defined below:
    L1 = {ambmcanbm | m,n >= 0 }
    L2={ aibjck | i,j,k >= 0 }
    Then L is


    A : Not recursive
    B : Regular
    C : Context free but not regular
    D : Recursively enumerable but not context free.


  •  
    .

     Correct answer is :C

     Solution :
      The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, }
    L2 accept strings {a, b, c, ab, abc, aabc, aabbc, }.
    Intersection of these two languages is L1 cap L2 = {ak bk c | k >= 0} which is context free, but not regular.

  •   Question 5

    The below DFA accepts the set of all strings over {0,1} that



    A : begin either with 0 or 1
    B : end with 0
    C : end with 00
    D : contain the substring 00


  •  
    .

     Correct answer is :C


  •   Question 6

    Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
    (A) L2 - L1 is recursively enumerable.
    (B) L1 L3 is recursively enumerable
    (C) L2 ∩ L1 is recursively enumerable
    (D) L2 ∪ L1 is recursively enumerable


    A : A
    B : B
    C : C
    D : D


  •  
    .

     Correct answer is :B


  •   Question 7

    Let L={w ∈ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

    A : (0*10*1)*
    B : 0*(10*10*)*
    C : 0*(10*1*)*0*
    D : 0*1(10*1)*10*


  •  
    .

     Correct answer is :B


  •   Question 8

    Consider the languages
    L1 = {0i1j | i ≠ j}.
    L2 = {0i1j | i = j}.
    L3 = {0i1j | i = 2j+1}.
    L4 = {0i1j | i != 2j}.


    A : Only L2 is context free
    B : Only L2 and L3 are context free
    C : Only L1 and L2 are context free
    D : All are context free


  •  
    .

     Correct answer is :D


  •   Question 9

    Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

    A : n-1
    B : n
    C : n+1
    D : 2n-1


  •  
    .

     Correct answer is :C

     Solution :
      all the n states in the max length substring that is the string itself and one final state so n+1

  • MY REPORT
    TOTAL = 9
    ANSWERED =
    CORRECT / TOTAL = /9
    POSITIVE SCORE =
    NEGATIVE SCORE =
    FINAL SCORE =