Theory of Computation – Multiple Choice Questions (MCQs)

1. 1. What is the fundamental question that Theory of Computation addresses?

   • A. What are the physical limits of computation?
   • B. What are the practical limits of computation?
   • C. What are the theoretical capabilities and limitations of computational models?
   • D. What are the economic implications of computation?

2. 2. Which of the following is a basic model of computation?

   • A. Turing Machine
   • B. Compiler
   • C. Operating System
   • D. Database

3. 3. What is an automaton?

   • A. An abstract self-propelled computing device that follows a predetermined sequence of operations automatically
   • B. A type of programming language
   • C. A network protocol
   • D. A hardware component

4. 4. What is a finite automaton (FA)?

   • A. An automaton with infinite states
   • B. An automaton with a finite number of states
   • C. An automaton that can perform complex arithmetic
   • D. An automaton that can learn from input

5. 5. What is an epsilon transition in an NFA?

   • A. A transition that consumes an input symbol
   • B. A transition that moves between states without reading any input symbol
   • C. A transition to a rejecting state
   • D. A transition to an accepting state

6. 6. Which languages are accepted by finite automata?

   • A. Regular languages
   • B. Context-free languages
   • C. Context-sensitive languages
   • D. Recursively enumerable languages

7. 7. What is a regular expression?

   • A. A sequence of characters that define a search pattern
   • B. A type of finite automaton
   • C. A formal grammar for describing context-free languages
   • D. A model of computation more powerful than a Turing Machine

8. 8. Which of the following operations can be performed on regular languages?

   • A. Union
   • B. Intersection
   • C. Complementation
   • D. Concatenation

9. 9. What is Kleene star operation on a language L?

   • A. The set of all strings formed by concatenating zero or more strings from L
   • B. The set of all strings of length one or more from L
   • C. The set of all strings in L reversed
   • D. The complement of the set of strings in L

10. 10. Which languages are generated by context-free grammars?

    • A. Regular languages
    • B. Context-free languages
    • C. Context-sensitive languages
    • D. Recursively enumerable languages

11. 11. What is a pushdown automaton (PDA)?

    • A. A finite automaton with an additional stack memory
    • B. A finite automaton without any memory
    • C. A Turing Machine with a restricted tape
    • D. A model of computation equivalent to a regular expression

12. 12. Which languages are accepted by pushdown automata?

    • A. Regular languages
    • B. Context-free languages
    • C. Context-sensitive languages
    • D. Recursively enumerable languages