Loading

SET 5


  Question 1

Which of the following problems is undecidable?

A : Membership problem for CFGs
B : Ambiguity problem for CFGs.
C : Finiteness problem for FSAs
D : Equivalence problem for FSAs


  •  
    .

     Correct answer is :B

     Solution :
      Ambiguity problem for CFGs are not decidable.

  •   Question 2

    Which of the following is TRUE?

    A : Every subset of a regular set is regular
    B : Every finite subset of a non-regular set is regular
    C : The union of two non-regular sets is not regular.
    D : Infinite union of finite sets is regular


  •  
    .

     Correct answer is :B


  •   Question 3

    A minimum state deterministic finite automaton accepting the language L={W | W ε {0,1} *, number of 0s and 1s in are divisible by 3 and 5, respectively} has

    A : 15 states
    B : 11 states
    C : 10 states
    D : 9 states


  •  
    .

     Correct answer is :A


  •   Question 4

    The language L= {0i21i | i≥0 } over the alphabet {0,1, 2} is:

    A : not recursive
    B : is recursive and is a deterministic CFL
    C : is a regular language
    D : is not a deterministic CFL but a CFL


  •  
    .

     Correct answer is :B


  •   Question 5

    Which of the following languages is regular?

    A : {wwR | w ∈ {0,1}+}
    B : {wwRx | x,w ∈ {0,1}+}
    C : {wxwR | x,w ∈ {0,1}+}
    D : {xwwR | x,w ∈ {0,1}+}


  •  
    .

     Correct answer is :C


  •   Question 6

    Consider the grammar with non-terminals N = {S,C,S1 },terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:
    S --> iCtSS1|a
    S1 --> eS|?
    C --> b
    The grammar is NOT LL(1) because:


    A : it is left recursive
    B : it is right recursive
    C : it is amiguous
    D : it is not context free


  •  
    .

     Correct answer is :C


  •   Question 7

    Consider the following Finite State Automaton. The language accepted by this automaton is given by the regular expression



    A : b* ab* ab* ab*
    B : (a+b)*
    C : b*a(a+b)*
    D : b*ab*ab*


  •  
    .

     Correct answer is :C


  •   Question 8

    Consider the following Finite State Automaton:
    The minimum state automaton equivalent to the above FSA has the following number of states




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


  •  
    .

     Correct answer is :B


  •   Question 9

    Which of the following is true for the language { ap | p is prime }

    A : It is not accepted by a Turing Machine
    B : It is regular but not context-free
    C : It is context-free but not regular
    D : It is neither regular nor context-free, but accepted by a Turing machine


  •  
    .

     Correct answer is :D


  •   Question 10

    Which of the following are decidable?
    I. Whether the intersection of two regular languages is infinite
    II. Whether a given context-free language is regular
    III. Whether two push-down automata accept the same language
    IV. Whether a given grammar is context-free


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


  •  
    .

     Correct answer is :B


  •   Question 11

    If L and L' are recursively enumerable, then L is

    A : regular
    B : context-free
    C : context-sensitive
    D : recursive


  •  
    .

     Correct answer is :D

     Solution :
      If L is recursively enumerable, then L' is recursively enumerable if and only if L is also recursive.

  •   Question 12

    Which of the following statements is false?

    A : Every NFA can be converted to an equivalent DFA
    B : Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machin
    C : Every regular language is also a context-free language
    D : Every subset of a recursively enumerable set is recursive


  •  
    .

     Correct answer is :D


  •   Question 13

    Given below are two finite state automata (? indicates the start state and F indicates a final state)Which of the following represents the product automaton ZY?



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


  •  
    .

     Correct answer is :A


  •   Question 14

    Match the following:



    A : E - P, F - R, G - Q, H - S
    B : E - R, F - P, G - S, H - Q
    C : E - R, F - P, G - Q, H - S
    D : E - P, F - R, G - S, H - Q


  •  
    .

     Correct answer is :C


  •   Question 15

    Match the following NFAs with the regular expressions they correspond to
    1. ε + 0(01*1 + 00) * 01*
    2. ε + 0(10 *1 + 00) * 0
    3. ε + 0(10 *1 + 10) *1
    4. ε + 0(10 *1 + 10) *10 *




    A : P - 2, Q - 1, R - 3, S - 4
    B : P - 1, Q - 3, R - 2, S - 4
    C : P - 1, Q - 2, R - 3, S - 4
    D : P - 3, Q - 2, R - 1, S - 4


  •  
    .

     Correct answer is :C


  •   Question 16

    Which of the following are regular sets?
    I. { an b2m |n >=0,m >= 0}
    II. { an bm |n = 2m }
    III. { an bm |n ≠ m}
    IV. {xcy x, y ε{a,b} *}


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


  •  
    .

     Correct answer is :A

     Solution :
      We can write DFA for both I and IV.

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