Loading

SET 2


  Question 1

Which one of the following is TRUE?

A : The language L = { an bn | n >= 0} is regular.
B : The language L = { an | n is prime } is regular.
C : The language L = { w | w has 3k +1b's for some k ∈ N with ∑ = {a,b} } is regular.
D : The language L ={ww | w ∈ ∑* with ∑ = {0,1} } is regular


  •  
    .

     Correct answer is :C

     Solution :
      (A) { an bn | n >= 0} is a CFL but not regular, it requires memory for the representati
    (B) L = { an | n is prime } is neither regular nor CFL
    (C) L = { w | w has 3k +1b's for some k ∈ N with ∑ = {a,b} }
    is a regular language, since the total count of bs are multiple of 3 plus one. The regular expression is a * ba *(a *ba *ba * ba *)*+(a * ba * ba * ba *)*a * ba *
    L ={ww | w ∈ ∑* with ∑ = {0,1} } is neither regular nor CFL

  •   Question 2

    Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?



    A : { q0,q1,q2}
    B : { q0,q1}
    C : { q0,q1,q2,q3}
    D : { q3}


  •  
    .

     Correct answer is :A

     Solution :
      d(q0 ,0011) = d(q0 ,011)
    =d(q0,11)
    =d({q0,q1},1)
    =d(q0,1) U d(q1,1)
    ={q0,q1} U {q2}
    {q0,q1,q2}

  •   Question 3

    Let L be a language and L` be its complement. Which of the following is NOT a viable possibility?

    A : Neither L nor L` is recursively enumerable (r.e.).
    B : One of L and L` is r.e. but not recursive; the other is not r.e.
    C : Both L and L` are r.e. but not recursive.
    D : Both L and L` are recursive.


  •  
    .

     Correct answer is :C

     Solution :
      Recursive languages are closed under complement.
    If a language L is recursive enumerable but not recursive then its complement is not a recursive enumerable, so both L and L' are recursive enumerable but not recursive is not a viable possibility.

  •   Question 4

    Which of the regular expressions given below represent the following DFA?
    I) 0*1(1+00*1)*
    II) 0*1*1+11*0*1
    III) (0+1)*1




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


  •  
    .

     Correct answer is :B

     Solution :
      Given DFA will accept all the strings over e ={0,1} which are ending with 1.
    0*1(1+ 00*1)* and(0 +1)*1, are the regular expressions for ending with 1.

  •   Question 5

    Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

    A : B :
    C : D :


  •  
    .

     Correct answer is :D

     Solution :
      The most important open question in complexity theory is whether the P = NP , which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems ( since a problem C is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.

  •   Question 6

    If L1= { an | n>=0 } and L2 = { bn | n>=0 } , Consider
    (I) L1.L2 is a regular language
    (II) L1.L2 = { anbn | n>0 }
    Which one of the following is CORRECT ?


    A : Only I
    B : Only II
    C : Both I and II
    D : Neither I and II


  •  
    .

     Correct answer is :A

     Solution :
      L1.L2 is also regular since regular languages are closed under concatenation.
    But L1.L2 is not { anbn | n >=0 } because both the variable is independent in both languages.

  •   Question 7

    Let m A <=m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

    A : If m A <=m B and B is recursive then A is recursive.
    B : If m A <=m B and A is undecidable then B is undecidable.
    C : If m A <=m B and B is recursively enumerable then A is recursively enumerable.
    D : If m A <=m B and B is not recursively enumerable then A is not recursively enumerable.


  •  
    .

     Correct answer is :D


  •   Question 8

    Let < M > be the encoding of a Turing machine as a string over S = {0,1} . Let L = {< M > |M is a Turning machine that accepts a string of length 2014}. Then, L is

    A : decidable and recursively enumerable
    B : undecidable but recursively enumerable
    C : undecidable and not recursively enumerable
    D : decidable but not recursively enumerable


  •  
    .

     Correct answer is :B

     Solution :
      The language accepted by the Turing machine is recursively enumerable. If is undecidable as the Turing machine may halt or it may loop for the strings whose length is not equal to 2014.

  •   Question 9

    Let L1 = w ∈ {0,1} * |w has at least as many occurrences of (110)s as (011)s}. Let L2 = {w 0,1 * | w has at least as many occurrence of (000)s as (111)s}. Which one of the following is TRUE?

    A : L1 is regular but not L2
    B : L2 is regular but not L1
    C : Both L1 and L2 are regular
    D : Neiher L1 and L2 are regular


  •  
    .

     Correct answer is :A

     Solution :
      The automaton for L1 is as follows and No finite state automata can be constructed for L2.


  •   Question 10

    The length of the shortest string NOT in the language (over ∑ = {a,b}) of the following regular expression is _________. a*b* (ba)* a*



  •  
    .

     Correct answer is :3

     Solution :
      R.E= a * b*(ba)*a *
    Length 0 is present as it accepts ∈ all length 1 strings are present (a,b)also aa,ab,ba,bb are present, But 'bab ' is not present. So it is 3

  •   Question 11

    Let S be a finite non-empty alphabet and let * 2S be the power set of S * . Which one of the following is TRUE?

    A : Both 2S * and S * are countable
    B : 2S * is countable S * is uncountable
    C : 2S * is uncountable and S * is countable
    D : Both 2S * and S * are uncountable


  •  
    .

     Correct answer is :C


  •   Question 12

    Which one of the following problems is undecidable?

    A : Deciding if a given context-free grammar is ambiguous.
    B : Deciding if a given string is generated by a given context-free grammar.
    C : Deciding if the language generated by a given context-free grammar is empty.
    D : Deciding if the language generated by a given context-free grammar is finite.


  •  
    .

     Correct answer is :A

     Solution :
      There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG, so it is undecidable.

  •   Question 13

    Consider the following languages over the alphabet S = {0,1,c}
    L1={0n1n | n>=0 }
    L2={ wcwr | w ∈ {0,1} *}
    L3={wwr | w ∈ {0,1} *}
    Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree languages?


    A : None of the languages
    B : Only L1
    C : Only L1 and L2
    D : All the three languages


  •  
    .

     Correct answer is :C

     Solution :
      For the languages L1 and L2 we can have deterministic push down automata, so they are DCFLs, but for L3 only non-deterministic PDA possible. So the language L3 is not a deterministic CFL.

  •   Question 14

    Consider the decision problem 2CNFSAT defined as follows:
    { ∅ | ∅ is a satisfiable propositional formula in CNF with at most two literal per clause}
    For example, ∅ = (x1 ∨ &x2) ∧ (x1 ∨ x3`) ∧ (x2 ∨ x4) is a Boolean formula and it is in 2CNFSAT.
    The decision problem 2CNFSAT is


    A : NP-Complete.
    B : solvable in polynomial time by reduction to directed graph reachability.
    C : solvable in constant time since any input instance is satisfiable.
    D : NP-hard, but not NP-complete.


  •  
    .

     Correct answer is :B


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