Quiz: Theory Of Computation! Computer Science Trivia

25 Questions | Total Attempts: 40

SettingsSettingsSettings
Please wait...
Quiz: Theory Of Computation! Computer Science Trivia

.


Questions and Answers
  • 1. 
    Let A = {0,1}, The Possible strings of the length of 'n' that can be formed by elements of the set A is
    • A. 

      N!

    • B. 

      N^2

    • C. 

      N^n

    • D. 

      2^n

  • 2. 
    The major difference between a Moore and a Mealy machine is that
    • A. 

      The output of the former depend on the present state and the current input

    • B. 

      The output of the former depend on the present state

    • C. 

      The output of the former depend on the current input

    • D. 

      None of these

  • 3. 
    The recognizing capability of NDFSM and DFSM
    • A. 

      May be different

    • B. 

      Must be different

    • C. 

      Must be the same

    • D. 

      None of these

  • 4. 
    FSM can recognize
    • A. 

      Any grammer

    • B. 

      Only CFG

    • C. 

      Any unambiguous grammar

    • D. 

      Only regular grammar

  • 5. 
    Pumping lemma is generally used for proving
    • A. 

      A given grammar is regular

    • B. 

      A given grammar is not regular

    • C. 

      Whether two given regular expressions are equivalent

    • D. 

      None of these

  • 6. 
    Which of the following pairs of regular expressions are equivalent
    • A. 

      1(01)*0 and (10)*10

    • B. 

      X(xx)* and (xx)*x

    • C. 

      (ab)*a and a*b*b

    • D. 

      X*y and x*x'y

  • 7. 
    The basic limitation of an FSM is that
    • A. 

      It can't remember arbitrary large amount of information

    • B. 

      It sometimes recognizes grammars that are not regular

    • C. 

      It sometimes fails to recognize grammars that are regular

    • D. 

      All of these

  • 8. 
    An FSM can be considered a TM
    • A. 

      Of finite tape length, rewinding capability and unidirectional tap movement

    • B. 

      Of finite tape length, without rewinding capability and unidirectional tape movement

    • C. 

      Of finite tape length, without rewinding capability and bidirectional tape movement

    • D. 

      Of finite tape length, rewinding capability and bidirectional tape movement

  • 9. 
    TM is more powerful than FSM because
    • A. 

      The tape movement is confined to one direction

    • B. 

      It has no finite state control

    • C. 

      It has the capability to remember arbitrary long sequences of input symbols

    • D. 

      None of these

  • 10. 
    The FSM pictured in fig is a
    • A. 

      Mealy Machine

    • B. 

      Moore Machine

    • C. 

      Kleene Machine

    • D. 

      None of these

  • 11. 
    Which of the following pairs of a regular expressions are not equivalent?
    • A. 

      (ab)*a and a(ba)*

    • B. 

      (a+b)* and (a* + b)*

    • C. 

      (a* +b)* and (a+b)*

    • D. 

      None of these

  • 12. 
    Set of regular languages over a given alphabet set is not closed under
    • A. 

      Union

    • B. 

      Complementation

    • C. 

      Intersection

    • D. 

      None the of these

  • 13. 
    The FSM in fig recongizes
    • A. 

      Any string of odd number of a's

    • B. 

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

    • C. 

      Any string of even number of a's and even number of b's

    • D. 

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

  • 14. 
    Any given Transition graph has an equivalent
    • A. 

      Regular expression

    • B. 

      DFSM

    • C. 

      NDFSM

    • D. 

      All of these

  • 15. 
    The below CFG is equivalent to which regular expression
    • A. 

      All of these

    • B. 

      (a + b)*

    • C. 

      (a + b)(a + b)*

    • D. 

      (a + b)*(a + b)

  • 16. 
    Any string of terminals that can be generated by the following CFG
    • A. 

      Has at least one b

    • B. 

      Should end in an 'a'

    • C. 

      Has no consecutive a's or b's

    • D. 

      Has at least two a's

  • 17. 
    The set {a^nb^n | n=1,2,3......} can be generated by CFG
    • A. 

      S → ab /aSb

    • B. 

      S → aaSbb /ab

    • C. 

      S → ab /aSb /€

    • D. 

      None of these

  • 18. 
    Choose the correct statements
    • A. 

      All languages can be generated by CFG

    • B. 

      Any regular language has an equivalent CFG.

    • C. 

      Some non-regular languages can be generated by any CFG

    • D. 

      Some regular languages can't be generated by any CFG.

  • 19. 
    CFG is not closed under
    • A. 

      Union

    • B. 

      Kleene Star

    • C. 

      Complementation

    • D. 

      Product

  • 20. 
    The set A={an bnan | n=1,2,3,….} is an example of a grammar that is
    • A. 

      Regular

    • B. 

      Context free

    • C. 

      Not context free

    • D. 

      None of these

  • 21. 
    L= {an bnan | n=1,2,3,….} is an example of a language that is
    • A. 

      Context free

    • B. 

      Not context free

    • C. 

      Not context free whose complement is  not CF

    • D. 

      Context free but whose complement is not CF

  • 22. 
    The intersection of a CFL and a regular language.
    • A. 

      Need not be regular

    • B. 

      Need not be context free

    • C. 

      Is complement of regular 

    • D. 

      Is always CF

  • 23. 
    The following grammar is
    • A. 

      Context free

    • B. 

      Regular

    • C. 

      Context sensitive

    • D. 

      LR(k)

  • 24. 
    Which of following conversion is not possible algorithmically?
    • A. 

      Regular Grammar to Context free Grammar

    • B. 

      Non deterministic FSA to Deterministic FSA

    • C. 

      Non deterministic PDA to Deterministic PDA

    • D. 

      Non deterministic TM to Deterministic TM

  • 25. 
    The number of internal states of a UTM should be at least
    • A. 

      1

    • B. 

      2

    • C. 

      3

    • D. 

      4