Loading

SET 6


  Question 1

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

A : P3 is decidable if P1 is reducible to P3
B : P3 is undecidable if P3 is reducible to P2
C : P3 is undecidable if P2 is reducible to P3
D : P3 is decidable if P3 is reducible to P2's complement


  •  
    .

     Correct answer is :C


  •   Question 2

    Consider the machine M: The language recognized by M is:



    A : {w ∈ {a, b}* / every a in w is followed by ex≠actly two b's}
    B : {w ∈ {a, b}* every a in w is followed by at least two bí}
    C : {w ∈ {a, b}* w contains the substring 'abb'}
    D : {w ∈ {a, b}* w does not contain 'aa' as a substring}


  •  
    .

     Correct answer is :B

     Solution :
      We can try some sample strings like aba, abbbb, abbbabbb

  •   Question 3

    Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

    A : Df ⊂ Nf and Dp ⊂ Np
    B : Df ⊂ Nf and Dp = Np
    C : Df = Nf and Dp = Np
    D : Df = Nf and Dp ⊂ Np


  •  
    .

     Correct answer is :D

     Solution :
      Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design. Deterministic context-free languages (DCFL) are a proper subset of context-free languages. Non-deterministic finite automata and Deterministic finite automata, both accept same set of languages as NFAs can be translated to equivalent DFAs using the subset construction algorithm.

  •   Question 4

    Consider the languages:
    L1 = {anbncm | n, m > 0}
    L2 = {anbmcm | n, m > 0}
    Which one of the following statements is FALSE?


    A : L1 ∩ L2 is a context-free language
    B : L1 U L2 is a context-free language
    C : L1 and L2 are context-free language
    D : L1 ∩ L2 is a context sensitive language


  •  
    .

     Correct answer is :A

     Solution :
      L1 and L2 are context free languages. See this for closure properties.

  •   Question 5

    Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
    L1' --> Complement of L1
    L2' --> Complement of L2


    A : L1' is recursive and L2' is recursively enumer≠able
    B : L1' is recursive and L2' is not recursively enumerable
    C : L1' and L2' are recursively enumerable
    D : L1' is recursively enumerable and L2' is recursive


  •  
    .

     Correct answer is :B

     Solution :
      Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. Recursive Languages are closed under complementation, but recursively enumerable are not closed under complementation. If a languages L is recursively enumerable, then the complement of it is recursively enumerable if and only if L is also recursive. Since L2 is recursively enumerable, but

  •   Question 6

    Consider the languages:
    L1 = {wwR |w ∈ {0, 1}*}
    L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
    L3 = {ww | w ∈ (0, 1}*)
    Which one of the following is TRUE?


    A : L1 is a deterministic CFL
    B : L2 is a deterministic CFL
    C : L3 is a CFL, but not a deterministic CFL
    D : L3 is a deterministic CFL


  •  
    .

     Correct answer is :B


  •   Question 7

    Consider the following two problems on undirected graphs
    α : Given G(V, E), does G have an independent set of size | V | - 4?
    β : Given G(V, E), does G have an independent set of size 5?
    Which one of the following is TRUE?


    A : α is in P and β is NP-complete
    B : α is NP-complete and β is in P
    C : Both α and β are NP-complete
    D : Both α and β are in P


  •  
    .

     Correct answer is :C

     Solution :
      Graph independent set decision problem is NP Complete.

  •   Question 8

    The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE?



    A : It computes 1's complement of the input number
    B : It computes 2's complement of the input number
    C : It increments the input number
    D : It decrements the input number


  •  
    .

     Correct answer is :B


  •   Question 9

    Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? A

    A : R is NP-complete
    B : R is NP-hard
    C : Q is NP-complete
    D : Q is NP-hard


  •  
    .

     Correct answer is :B

     Solution :
      (A) Incorrect because R is not in NP. A NP Complete problem has to be in both NP and NP-hard.
    (B) Correct because a NP Complete problem S is polynomial time educable to R.
    (C) Incorrect because Q is not in NP.
    (D) Incorrect because there is no NP-complete problem that is polynomial time Turing-reducible to Q.

  •   Question 10

    Let L1={ 0n+m1n0m | n,m>=0 } , L2={ 0n+m1n+m0m | n,m>=0 } and L3={ 0n+m1n+m0n+m | n,m>=0 }
    Which of these languages are NOT context free?


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


  •  
    .

     Correct answer is :D

     Solution :
      A PDA can be built only for L1. It is not possible to build PDA for L2 and L3.

  •   Question 11

    If s is a string over (0 + 1)* then let n0(s) denote the number of 0ís in s and n1(s) the number of 1ís in s. Which one of the following languages is not regular?

    A : L ={ s ∈ (0 + 1) * | n0 (s) is a 3-digit prime }
    B : L ={ s ∈ (0 + 1) * | for every prefix s` of s1 | n0(s`)-n1(s`) <=2 }
    C : L ={ s ∈ (0 + 1) * | n0 (s) - n1(s) | <=4 }
    D : L ={ s ∈ (0 + 1) * | n0 (s) mod 7 = n1(s) mod 5 =0 }


  •  
    .

     Correct answer is :B

     Solution :
      Languages in option (A) And (D) are finite so both the options are eliminated. Only left options are (B) and (C). Both (B) and (C) look not regular as we don't have memory in DFA.

  •   Question 12

    For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s) mod 5 = 2 and d(s) mod 7 != 4}. Which one of the following statements is true?

    A : L is recursively enumerable, but not recursive
    B : L is recursive, but not context-free
    C : L is context-free, but not regular
    D : L is regular


  •  
    .

     Correct answer is :D

     Solution :
      It is regular L1=d(s) mod 5 =2 is regular with 5 states L2=d(s) mod 7 =4 is regular with 7 states therefore L1 ^ L2' should be regular because regular grammar are closed under intersection and compliment

  •   Question 13

    Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

    A : Both DHAM3 and SHAM3 are NP-hard
    B : SHAM3 is NP-hard, but DHAM3 is not
    C : DHAM3 is NP-hard, but SHAM3 is not
    D : Neither DHAM3 nor SHAM3 is NP-hard


  •  
    .

     Correct answer is :A


  •   Question 14

    Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

    A : L1 ∩ L2 is a deterministic CFL
    B : L3 ∩ L1 is recursive
    C : L1 ∪ L2 is context free
    D : L1 ∩ L2 ∩ L3 is recursively enumerable


  •  
    .

     Correct answer is :B


  •   Question 15

    Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

    A : 3
    B : 5
    C : 8
    D : 9


  •  
    .

     Correct answer is :D


  •   Question 16

    Which one of the following grammars generates the language L = {aibj | i ≠ j}

    A : S->AC|CB
    C->aCb|a|b
    A->aA | ε
    B-> Bb|ε

    B : S -> aS|Sb|a|b
    C : S->AC|CB
    C->aCb|&epsioln;
    A->aA | ε
    B-> Bb|ε

    D : S->AC|CB
    C->aCb|&epsioln;
    A->aA | a
    B-> Bb|b



  •  
    .

     Correct answer is :D


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