Theory of Computation – Multiple Choice Questions (MCQs)

1. 37. What is time complexity?

   • A. The amount of memory space required by an algorithm
   • B. The amount of time required by an algorithm to run
   • C. The number of variables used by an algorithm
   • D. The size of the input to an algorithm

2. 38. What is the pumping lemma for regular languages?

   • A. A theorem that provides a necessary condition for a language to be regular
   • B. A method for constructing finite automata
   • C. A way to prove that a language is context-free
   • D. A technique for minimizing the number of states in a DFA

3. 39. What is the pumping lemma for context-free languages?

   • A. A theorem that provides a necessary condition for a language to be context-free
   • B. A method for constructing pushdown automata
   • C. A way to prove that a language is regular
   • D. A technique for simplifying context-free grammars

4. 40. What is an ambiguous grammar?

   • A. A context-free grammar for which there exists at least one string that can have more than one leftmost derivation (or more than one rightmost derivation
   • B. or more than one parse tree)
   • C. A grammar that generates all possible strings
   • D. A grammar with no useless symbols

5. 41. What is Chomsky Normal Form (CNF)?

   • A. A standard form for context-free grammars where all production rules are of the form A -> BC or A -> a
   • B. where A
   • C. B
   • D. C are non-terminals and a is a terminal

6. 42. What is Greibach Normal Form (GNF)?

   • A. A standard form for context-free grammars where every production rule has a terminal as the first symbol
   • B. followed by zero or more non-terminals
   • C. A standard form for finite automata
   • D. A complex form of a Turing Machine

7. 43. What is the hierarchy of formal languages (Chomsky hierarchy)?

   • A. A classification of formal languages based on the type of grammar that generates them
   • B. A classification of computational models based on their power
   • C. A classification of algorithms based on their time complexity
   • D. A classification of data structures based on their efficiency

8. 44. The Chomsky hierarchy consists of which four types of languages?

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

9. 45. Which type of automaton accepts regular languages?

   • A. Finite Automaton (DFA or NFA)
   • B. Pushdown Automaton
   • C. Turing Machine
   • D. Linear Bounded Automaton

10. 46. Which type of automaton accepts context-free languages?

    • A. Finite Automaton
    • B. Pushdown Automaton
    • C. Turing Machine
    • D. Linear Bounded Automaton

11. 47. Which type of automaton accepts context-sensitive languages?

    • A. Finite Automaton
    • B. Pushdown Automaton
    • C. Turing Machine
    • D. Linear Bounded Automaton

12. 48. Which type of automaton accepts recursively enumerable languages?

    • A. Finite Automaton
    • B. Pushdown Automaton
    • C. Turing Machine
    • D. Linear Bounded Automaton