Theory Of Computation (Toc) Quiz

20 Questions | Total Attempts: 2067

SettingsSettingsSettings
Please wait...
Theory Of Computation (Toc) Quiz

.


Questions and Answers
  • 1. 
    The FSM (Finite State Machine) machine pictured in the figure below represents what language? (ISRO-2018)  
    • A. 

      Complements a given bit pattern

    • B. 

      Finds 2’s complement of a given bit pattern

    • C. 

      Increments a given bit pattern by 1

    • D. 

      Changes the sign bit

  • 2. 
    Let L = {w = (0+1)* | w has even number of 1’s}, i.e. L is the set of all bit strings with even number of 1’s. Which one of the regular expression below represents L ? (ISRO-2016)
    • A. 

      (0*10*1)*

    • B. 

      0*(10*10*)*

    • C. 

      0*(10*1*)*0*

    • D. 

      0*1(10*1)10*

  • 3. 
    S → aSa ∣ bSb ∣ a ∣ b The language generated by the above grammar over the alphabet is the set of (ISRO 2016)
    • A. 

      All palindromes

    • B. 

      All odd length palindromes

    • C. 

      Strings that begin and end with the same symbol

    • D. 

      All even length palindromes

  • 4. 
    The DFA generated from the following NFA? ISRO CS2013
    • A. 

      Q0, q1, q2

    • B. 

      [q0, q1], [q0, q2], [ ]

    • C. 

      Q0, [q1, q2]

    • D. 

      [q0, q1], q2

  • 5. 
    The number of states required by a Finite State Machine, to simulate the behaviour of a computer with a memory capable of storing ‘m’ words, each of length ‘n’ bits is?
    • A. 

      M x 2^n

    • B. 

      2m+n

    • C. 

      2^mn

    • D. 

      M+n

  • 6. 
    The given finite automata represent which of the languages?
    • A. 

      {1, 0}* {01}

    • B. 

      {1, 0}* {1}

    • C. 

      {1}{1, 0}* {1}

    • D. 

      1*0* {0, 1}

  • 7. 
    Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is ( GATE-CS-2003)
    • A. 

      1

    • B. 

      5

    • C. 

      7

    • D. 

      8

  • 8. 
    The finite state machine given in figure below recognizes : UGC-NET JUNE Paper-2
    • A. 

      Any string of odd number of a’s

    • B. 

      Any string of odd number of b’s

    • C. 

      Any string of even number of a’s and odd number of b’s

    • D. 

      Any string of odd number of a’s and odd number of b’s

  • 9. 
    The automata represent which of the languages given below? Nielit Scentist-B [02-12-2018]
    • A. 

      Ab*b*

    • B. 

      A*b*

    • C. 

      B*b

    • D. 

      B*ab*

  • 10. 
    Which of the following languages over the alphabet {0,1} is described by the given regular expression: (0+1)*1(0+1)*1? Nielit Scentist-B [02-12-2018]
    • A. 

      The set of all strings containing the substrings 11

    • B. 

      The set of all string containing at most two 1’s

    • C. 

      The set of all strings containing at least two 1’s

    • D. 

      The set of all strings that begins and ends with only 0.

  • 11. 
    In the given language L={ab,aa,baa}, __ number of strings are in L* (1) baaaba (2) aabaaaa (3) baaabaaaabaa (4) baaabaaa (GATE CS 2012)
    • A. 

      1, 2 and 3

    • B. 

      2, 3 and 4

    • C. 

      1, 2 and 4

    • D. 

      1, 3 and 4

  • 12. 
    Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2*U L1*
    • A. 

      A

    • B. 

      B

    • C. 

      C

    • D. 

      D

  • 13. 
    Consider the DFA given. GATE CS 2013 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

  • 14. 
    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. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

    • D. 

      Option 4

  • 15. 
    Which of the following statements is false? GATE CS 2008
    • A. 

      Every NFA can be converted to an equivalent DFA

    • B. 

      Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine

    • C. 

      Every regular language is also a context-free language

    • D. 

      Every subset of a recursively enumerable set is recursive

  • 16. 
    The transition function for the language L = {w|na (w) and nb(w) are both odd} is given by: UGC NET CS 2015 Jun δ (q0, a) = q1 ; δ (q0, b) = q2 δ (q1, a) = q0 ; δ (q1, b) = q3 δ (q2, a) = q3 ; δ (q2, b) = q0 δ (q3, a) = q2 ; δ (q3, b) = q1 The initial and final states of the automata are:
    • A. 

      Q0 and q0 respectively

    • B. 

      Q0 and q1 respectively

    • C. 

      Q0 and q2 respectively

    • D. 

      Q0 and q3 respectively

  • 17. 
    Which of the following are not regular? UGC NET CS 2017 Jan (A) Strings of even number of a’s. (B) Strings of a’s, whose length is a prime number. (C)Set of all palindromes made up of a’s and b’s. (D)Strings of a’s whose length is a perfect square.
    • A. 

      (A) and (B) only

    • B. 

      (A), (B) and (C) only

    • C. 

      (B), (C) and (D) only

    • D. 

      (B) and (D) only

  • 18. 
    Which of the following are not regular? UGC NET CS 2017 Jan (A) Strings of even number of a’s. (B) Strings of a’s, whose length is a prime number. (C) Set of all palindromes made up of a’s and b’s. (D) Strings of a’s whose length is a perfect square.
    • A. 

      (A) and (B) only

    • B. 

      (A), (B) and (C) only

    • C. 

      (B), (C) and (D) only

    • D. 

      (B) and (D) only

  • 19. 
    The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________
    • A. 

      2

    • B. 

      3

    • C. 

      4

    • D. 

      5

  • 20. 
    How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
    • A. 

      7

    • B. 

      10

    • C. 

      12

    • D. 

      11

Back to Top Back to top