Loading

SET 3


  Question 1

Which of the following pairs have DIFFERENT expressive power?

A : Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
B : Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
C : Deterministic single-tape Turing machine and Non-deterministic single tape Turing machine
D : Single-tape Turing machine and multi-tape Turing machine


  •  
    .

     Correct answer is :B

     Solution :
      NPDA is more powerful than DPDA. Hence answer is (B)

  •   Question 2

    Definition of a language L with alphabet {a} is given as following
    L = { ank | k > 0, and n is a positive integer constant }
    What is the minimum number of states needed in a DFA to recognize L?


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


  •  
    .

     Correct answer is :B

     Solution :
      (n + 1) states as n is constant and k can have any value so if n = 2 then we can do this with k=1 and with 3 states.

  •   Question 3

    A deterministic finite automation (DFA)D with alphabet ? = {a,b} is given below Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?



    A : B :
    C : D :


  •  
    .

     Correct answer is :A

     Solution :
      Options B and C will accept the string b
    Option – D will accept the string “bba”
    Both are invalid strings.
    So the minimized DFA is option A

  •   Question 4

    Let P be a regular language and Q be a context free language such that Q ⊆ P.(For example, let P be the language represented by the regular expression p*q* and Q be {pnqn | n ∈ N} ). Then which of the following is ALWAYS regular?

    A : p ∩ Q
    B : P-Q
    C : * - P
    D : * - Q


  •  
    .

     Correct answer is :C

     Solution :
      ∑ * - P is the complement of P so it is always regular, since regular languages are closed under complementation

  •   Question 5

    Consider the language L1,L2,L3 as given below.
    L1={ 0p 1q | p,q ∈ N }
    L2={ 0p 1q | p,q ∈ N and p=q }
    L3={ 0p 1q 0r | p,q,r ∈ N and p=q=r }
    Which of the following statements is NOT TRUE?


    A : Push Down Automata (PDA) can be used to recognize L1 and L2
    B : L1 is a regular language
    C : All the three languages are context free
    D : Turing machine can be used to recognize all the three languages


  •  
    .

     Correct answer is :C

     Solution :
      L1: regular language
    L2: context free language
    L3: context sensitive language

  •   Question 6

    Which of the following problems are decidable?
    1)Does a given program ever produce an output?
    2)If L is context-free language, then, is L` also context-free?
    3)If L is regular language, then, is L` also regular
    4)If L is recursive language, then, is L` also recursive?


    A : 1,2,3,4
    B : 1,2
    C : 2,3,4
    D : 3,4


  •  
    .

     Correct answer is :D

     Solution :
      CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

  •   Question 7

    Given the language L-{ab, aa, baa}, which of the following strings are in L*?
    1) abaabaaabaa
    2) aaaabaaaa
    3) baaaaabaaaab
    4) baaaaabaa


    A : 1,2 and 3
    B : 2,3 and 4
    C : 1,2 and 4
    D : 1,3 and 4


  •  
    .

     Correct answer is :C

     Solution :
      L ={ab, aa, baa}
    Let S1 = ab , S2 = aa and S3 =baa
    abaabaaabaa can be written as S1S2S3S1S2 aaaabaaaa can be written as S1S1S3S1 baaaaabaa can be written as S3S2S1S2

  •   Question 8

    What is the complement of the language accepted by the NFA shown below?



    A :
    B : { ∈ }
    C : a*
    D : { a , ∈ }


  •  
    .

     Correct answer is :B

     Solution :
      Language accepted by NFA is a+, so complement of this language is {∈}

  •   Question 9

    Assuming P ≠ NP, which of the following is TRUE?

    A : NP-complete = NP
    B : NP-complete ∩ P = ∅
    C : NP-hard = NP
    D : P = NP-complete


  •  
    .

     Correct answer is :B

     Solution :
      If P!=NP, then it implies that no NP-Complete problem can be solved in polynomialtime which implies that the set P and the set NPC are disjoint.

  •   Question 10

    Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.



    A : B :
    C : D :


  •  
    .

     Correct answer is :D


  •   Question 11

    Which of the following statements are TRUE?
    (1) The problem of determining whether there exists a cycle in an undirected graph is in P.
    (2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
    (3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.


    A : 1,2 and 3
    B : 1 and 2 only
    C : 2 and 3 only
    D : 1 and 3 only


  •  
    .

     Correct answer is :A

     Solution :
      1. Cycle detection using DFS: O(V+ E) = O(V2 ) and it is polynomial problem
    2.Every P-problem is NP(since P ⊂ NP)
    3.NP - complete ∈ NP
    Hence, NP-complete can be solved in non-deterministic polynomial time

  •   Question 12

    Which of the following statements is/are FALSE?
    (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
    (2) Turing recognizable languages are closed under union and complementation.
    (3) Turing decidable languages are closed under intersection and complementation
    (4) Turing recognizable languages are closed under union and intersection.


    A : 1 and 4 only
    B : 1 and 3 only
    C : 2 only
    D : 3 only


  •  
    .

     Correct answer is :C

     Solution :
      (1) NTM ≅ DTM
    (2) RELs are closed under union & but not complementation
    (3) Turing decidable languages are recursive and recursive languages are closed under intersection and complementation
    (4) RELs are closed under union & intersection but not under complementation

  •   Question 13

    Consider the languages L1 =∅ and L2 ={ a} . Which one of the following represents L1 L2* U L1* ?

    A : {∈}
    B :
    C : a*
    D : {∈ , a}


  •  
    .

     Correct answer is :A

     Solution :
      Concatenation of empty language with any language will give the empty language and L1* = ∅* = ∈ . Hence L1L2* U L1* = {∈}

  •   Question 14

    Which of the following is/are undecidable?
    1. G is a CFG. Is L(G) =∅?
    2. G is a CFG. IS L(G) = ∑*?
    3. M is a Turning machine. Is L(M) regular?
    4. A is a DFA and N is a NFA. Is L(A) = L(N)?


    A : 3 only
    B : 3 and 4 only
    C : 1,2 and 3 only
    D : 2 and 3 only


  •  
    .

     Correct answer is :D

     Solution :
      There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable

  •   Question 15

    Consider the DFA given below.
    Which of the following are FALSE?
    1. Complement of L(A) is context–free
    2. L(A) = L((11* 0 + 0)(0 +1)* 0 *1*)
    3. For the language accepted by A, A is the minimal DFA
    4. A accepts all strings over {0, 1} of length at least 2




    A : 1 and 3 only
    B : 2 and 4 only
    C : 2 and 3 only
    D : 3 and 4 only


  •  
    .

     Correct answer is :D

     Solution :
      (1) L(A) is regular, its complement is also regular and if it is regular it is also context free.
    (2) L(A) =(11*0 + 0)(0 +1)* 0*1* = 1*0 (0 +1)* Language has all strings where each string contains ‘0’.
    (3) A is not minimal, it can be constructed with 2 states
    (4) Language has all strings, where each string contains ‘0’. (atleast length one)

  •   Question 16

    Consider the following languages
    L1={0p1q0r | p,q,r >=0 }
    L2={0p1q0r | p,q,r >=0 ,p≠r }
    Which one of the following statements is FALSE?


    A : L2 is context free
    B : L1 ∩ L2 is context free
    C : Complement of L1 is recursive
    D : Complement of L1 is context free but not regular


  •  
    .

     Correct answer is :D


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