Loading

SET 1


  Question 1

For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?
I. L1` (complement of L1) is recursive II. L2 (complement of L2) is recursive
III. L2` is context-free
IV. L1` L2` is recursively enumerable


A : I only
B : III only
C : III and IV only
D : I and IV only


  •  
    .

     Correct answer is :D

     Solution :
      1 => This one is true, because L1 is context free which is nothing but recursive, recursive language is closed under complement hence true.
    2 => If L2 and L2` both are recursive enumerable then L2` is recursive Hence option 2 is false
    3 => is false because context free language does not closed under complement
    4=> L1 ` = recursive and the union of context free and RE is RE(recursively enumerable).

  •   Question 2

    Consider the DFAs M and N given below. The number of states in a minimal DFA that accepts the language L(M) ? L(N) is __________.





  •  
    .

     Correct answer is :1

     Solution :
      M accepts the strings which end with a and N acceptsthe strings which end with B. Their intersection should accept empty language


  •   Question 3

    Consider the NPDA < Q = {q0, q1, q2}, ∑ = {0, 1}, τ = {0, 1, ⊥ }, δ, q0, ⊥ , F = {q2} >, where (as per usual convention) Q is the set of states, ? is the input alphabet, ? is stack alphabet, ? is the state transition function, q0 is the initial state, is the initial stack symbol, and F is the set of accepting states, The state transition is as follows Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?



    A : 10110
    B : 10010
    C : 01010
    D : 01001


  •  
    .

     Correct answer is :D


  •   Question 4

    Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?

    A : Q1 is in NP, Q2 in NP hard
    B : Q2 is in NP, Q1 is NP hard
    C : Both Q1 and Q2 are in NP
    D : Both Q1 and Q2 are in NP hard


  •  
    .

     Correct answer is :A


  •   Question 5

    Consider the following statements
    I. The complement of every Turing decidable language is Turing decidable
    II. There exists some language which is in NP but is not turing decidable
    III. If L is a language in NP, L is turing decidable
    Which of the above statements is/are true?


    A : Only II
    B : Only III
    C : Only I and II
    D : Only I and III


  •  
    .

     Correct answer is :D

     Solution :
      Turing decidable => Recursive language
    Turing recognizable => Recursive enumerable language
    I) Complement of turning decidable language is decidable which is true.
    III) True ( Theorem ) Which violates (II) hence key is D

  •   Question 6

    Consider the alphabet Σ={0,1}, the null/empty string λand the sets of strings X0,X,sub>1 and X2 generated by the corresponding non-terminals of regular grammar X0 , X 1 and X2 are related as follows
    X0 = 1 X1
    X1 = 0 X1 + 1 X2
    X2 = 0 X1 + {λ}
    Which one of the following choices precisely represents the strings in X0?


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


  •  
    .

     Correct answer is :C


  •   Question 7

    Which of the following languages is/are regular?
    L1 : { wxwR | w,x {a,b} * nad |w| , |x| >0 } ,wR is the reverse of sring w.
    L2 : {anbm | m n and m,n >=0 }
    L3 : { apbqcr } p,q,r >=0}


    A : L1 and L3 only
    B : L1 only
    C : L2 and L3 only
    D : L3 only


  •  
    .

     Correct answer is :A

     Solution :
      L1 :wR is reverse of string w ∴ Its is regular
    L2 : m ≠ n ,that mean n is greater than m, or m is greater than n. So we need memory, so we can't draw DfA for it.
    L3 It is regular (a+b+c)*

  •   Question 8

    The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0+1)* (10 ) is _________________



  •  
    .

     Correct answer is :3

     Solution :
      (0+1)* (10 )


  •   Question 9

    Let L be the language represented by the regular expression Σ *0011 Σ * where Σ ={0,1}. What is the minimum number of states in a DFA that recognizes L (complement of L)?

    A : 4
    B : 5
    C : 6
    D : 8


  •  
    .

     Correct answer is :B


  •   Question 10

    Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?
    I. if L4 P, then L2
    if L1 P or L3 P , then L2 P
    III. L1 P,if and only if L3 P
    if L4 P,then L1 P and L3 P


    A : II only
    B : III only
    C : I and IV only
    D : I only


  •  
    .

     Correct answer is :C

     Solution :
      L2<= pL4
    L1 <= pL2
    if L4 P then L2 P hence L1 P, hence option C.

  •   Question 11

    Which of the following languages are context-free?
    L1 = { ambnanbm | m,n >=1 }
    L2 = { ambnambn | m,n >=1 }
    L3 = { ambn | m=2n+1 }


    A : L1 and L2 only
    B : L1 and L3 only
    C : L2 and L3 only
    D : L3 only


  •  
    .

     Correct answer is :C

     Solution :
      ambnanbm => This one is CFL
    ambnambn => by pumping lemma this one is not CFL.
    { ambn | m=2n+1 } This is CFL.

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