Q1: 1. Which of the following is a method used to test whether a language is regular in Theory of Computation?

• A) Pumping Lemma
• B) Turing Machine
• C) Greedy Algorithm
• D) Breadth-First Search

Q2: 2. What does the Pumping Lemma help determine about a language?

• A) Whether it is context-free
• B) Whether it is regular
• C) Whether it is recursively enumerable
• D) Whether it is decidable

Q3: 3. If a language satisfies the conditions of the Pumping Lemma, it is

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

Q4: 4. Which of the following is a real-life problem that can be modeled as testing whether a language is regular?

• A) Checking if an email address is valid
• B) Sorting a list of integers
• C) Finding the shortest path in a graph
• D) Encrypting sensitive data

Q5: 5. The Pumping Lemma is particularly useful for proving that a language is

• A) Not context-free
• B) Not regular
• C) Decidable
• D) Finite

Q6: 6. Which of the following is a characteristic of regular languages?

• A) They can be recognized by a pushdown automaton
• B) They can be represented by regular expressions
• C) They have unbounded memory
• D) They are always context-sensitive

Q7: 7. A language that cannot be recognized by a finite automaton is

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

Q8: 8. The Pumping Lemma states that for any regular language L, there exists a constant p such that

• A) Any string in L can be pumped to generate infinite strings
• B) A finite automaton can recognize L in p steps
• C) Any string in L of length at least p can be split into xyz
• D) L can be transformed into a context-free language

Q9: 9. Regular languages are closed under which of the following operations?

• A) Union
• B) Intersection
• C) Complement
• D) All of the above

Q10: 10. Which of the following is a common mistake when applying the Pumping Lemma to test regularity of a language?

• A) Choosing a string that is too short
• B) Ignoring the conditions of the lemma
• C) Using a non-deterministic finite automaton
• D) Applying the lemma to a context-free language

Q11: 11. If a language can be recognized by a regular expression, it is

• A) Always regular
• B) Always context-free
• C) Always context-sensitive
• D) Always recursively enumerable

Q12: 12. Which of the following is a property of regular languages?

• A) They are closed under concatenation
• B) They are closed under complementation
• C) They can recognize non-regular languages
• D) They require infinite memory

Q13: 13. The Pumping Lemma is a useful tool for proving that a language is not regular because

• A) It can be applied to any type of language
• B) It provides a systematic way to find counterexamples
• C) It guarantees that the language is context-free
• D) It simplifies the process of designing a Turing machine

Q14: 14. Which of the following statements is true about regular languages?

• A) They can be recognized by a context-sensitive grammar
• B) They have a pumping length of zero
• C) They can be recognized by a deterministic finite automaton
• D) They can represent uncountably infinite languages

Q15: 15. The Pumping Lemma can be used to show that a language is regular by demonstrating that

• A) Every string in the language can be pumped
• B) There exists a string that cannot be pumped
• C) The language can be accepted by a Turing machine
• D) The language is context-free

Q16: 16. A language that is regular

• A) Can always be recognized by a nondeterministic finite automaton
• B) Can be described by a context-sensitive grammar
• C) Can have an infinite number of strings
• D) Can be recognized by a finite automaton

Q17: 17. Which of the following is a common approach to proving that a language is regular?

• A) Constructing a context-sensitive grammar
• B) Showing that the language is context-free
• C) Demonstrating the existence of a pumping length
• D) Using a universal Turing machine

Q18: 18. Regular languages are closed under which of the following operations?

• A) Kleene closure
• B) Cartesian product
• C) Set difference
• D) Power set

Q19: 19. If a language is regular, then it is also

• A) Always context-free
• B) Always recursively enumerable
• C) Always context-sensitive
• D) Always decidable

Q20: 20. Which of the following is a property of regular languages?

• A) They can be recognized by a turing machine
• B) They can be recognized by a pushdown automaton
• C) They can be infinite
• D) They can be complemented

Q21: 21. The Pumping Lemma is used to show that a language is not regular by demonstrating that

• A) Every string in the language can be pumped
• B) There exists a string that cannot be pumped
• C) The language is context-free
• D) The language can be accepted by a Turing machine

Q22: 22. Regular languages are closed under which of the following operations?

• A) Subtraction
• B) Division
• C) Concatenation
• D) Symmetric difference

Q23: 23. If a language is regular, then it is also

• A) Always context-free
• B) Always recursively enumerable
• C) Always context-sensitive
• D) Always decidable

Q24: 24. The Pumping Lemma is particularly useful for proving that a language is

• A) Context-free
• B) Not regular
• C) Decidable
• D) Finite

Q25: 25. Which of the following is a real-life problem that can be modeled as testing whether a language is regular?

• A) Checking if a string is a palindrome
• B) Solving a system of linear equations
• C) Finding the maximum flow in a network
• D) Encrypting sensitive data