TOC MCQ BY SIR

Q. 1Which of the following is not a type of automaton?

a) Finite Automaton

b) Pushdown Automaton

c) Deterministic Automaton

d) Context-Free Automaton

2.What is the defining feature of a regular language?

a) They can be recognized by a Turing machine

b) They can be recognized by a pushdown automaton

c) They can be recognized by a finite automaton

d) They can be recognized by a context-sensitive grammar

3.Which of the following is not true about Regular Expressions?

a) They can describe regular languages

b) They can be converted to equivalent Finite Automata

c) They can describe context-free languages

d) They can be used to search patterns in text

4. In context-free grammars, which symbol is used to represent the start

symbol?

a) S

b) A

c) #

d) ?

5. What is the pumping lemma used for?

a) To prove that a language is regular

b) To prove that a language is context-free

c) To prove that a language is context-sensitive

d) To prove that a language is recursive enumerable

6. Which of the following is true about the Chomsky hierarchy?

a) It categorizes programming languages based on their syntax

b) It categorizes formal grammars based on their generative power

c) It categorizes automata based on their acceptance power

d) It categorizes algorithms based on their complexity

7. Which automaton has the highest computational power among the

following?

a) Finite Automaton

b) Pushdown Automaton

c) Turing Machine

d) Context-Free Automaton

8. What is the difference between a deterministic and non-deterministic finite

automaton?

a) Deterministic finite automaton can handle infinite languages

b) Non-deterministic finite automaton cannot be simulated by a Turing machine

c) Deterministic finite automaton has a unique next state for each input symbol

d) Non-deterministic finite automaton has multiple possible next states for each input

symbol

9. Which automaton has the highest computational power among the following?

a) Finite Automaton
b) Pushdown Automaton

c) Turing Machine

d) Context-Free Automaton

10.What is the difference between a deterministic and non-deterministic finite

automaton?

a) Deterministic finite automaton can handle infinite languages

b) Non-deterministic finite automaton cannot be simulated by a Turing machine

c) Deterministic finite automaton has a unique next state for each input symbol

d) Non-deterministic finite automaton has multiple possible next states for each input

symbol

11.Which property distinguishes context-free grammars from regular grammars?

a) Context-free grammars can generate context-free languages

b) Context-free grammars can generate regular languages

c) Context-free grammars can handle infinite languages

d) Context-free grammars can generate non-context-free languages

12. Which of the following is not a component of a Turing machine?

a) Input tape

b) Output tape

c) Transition function

d) Finite control

13.The halting problem is:

a) Decidable

b) Semi-decidable

c) Undecidable

d) Trivial

14.Which of the following is not a property of recursive languages?

a) Closed under complement

b) Closed under union

c) Closed under Kleene star

d) Closed under intersection

15.Which of the following is not a technique used to prove the decidability of a problem?
a) Reduction

b) Enumeration

c) Diagonalization

d) Induction

16. Which of the following is not a technique used to prove the decidability of a problem?

a) Reduction

b) Enumeration

c) Diagonalization

d) Induction

17.What is the primary purpose of the Church-Turing thesis?

a) To define the limits of computation

b) To propose a theory of computability

c) To establish a foundation for lambda calculus

d) To develop a model of computation based on neural networks

18.Which of the following is true about recursive enumerable languages?

a) They are a proper subset of recursive languages

b) They can be recognized by a Turing machine that halts on every input

c) They are closed under complement

d) They are a proper subset of context-sensitive languages

19. Which problem is not decidable?

a) The language of a given context-free grammar is empty

b) Two context-free grammars generate the same language

c) Whether a given Turing machine halts on a given input

d) Whether a given Turing machine recognizes a regular language

20. Which of the following is not a component of the Chomsky normal form for contextfree grammars?

a) Unit productions

b) ?-productions

c) Binary productions

d) Terminal symbols

21.Which statement is false about the Post Correspondence Problem (PCP)?

a) PCP is decidable

b) PCP is used to prove undecidability of other problems

c) PCP can be reduced to the halting problem

d) PCP involves finding a sequence of tiles that matches at least one pair of sequences

22.Which of the following is not a property of regular expressions?

a) Closed under concatenation

b) Closed under union

c) Closed under complement

d) Closed under intersection

23.Which of the following is NOT a type of automaton?

a) Deterministic Finite Automaton (DFA)

b) Non-deterministic Finite Automaton (NFA)

c) Pushdown Automaton (PDA)

d) Directed Graph Automaton (DGA)

24.Which of the following problems is NOT decidable?

a) Halting problem

b) Post correspondence problem

c) Regular expression equivalence

d) Turing machine halting on all inputs

25.The pumping lemma for regular languages states that for any regular language L, there exists a constant p
such that any string s in L with length at least p can be divided into three substrings, s = xyz, satisfying certain

conditions. What does 'p' represent?

a) Pumping length

b) Power length

c) Parse length

d) Prefix length

26.Which of the following statements is true about contextfree languages (CFL)

a) CFLs can always be recognized by finite automata.

b) CFLs can be recognized by pushdown automata.

c) CFLs can be recognized by deterministic finite

automata.

d) CFLs can be recognized by regular expressions.

27.The pumping lemma for regular languages states that for

any regular language L, there exists a constant p such that any string s in L with length at least p can be divided

into three substrings, s = xyz, satisfying certain conditions. What does 'p' represent?
a) Pumping length

b) Power length

c) Parse length

d) Prefix length

28. Which of the following statements is true about contextfree languages (CFL)?

a) CFLs can always be recognized by finite automata.

b) CFLs can be recognized by pushdown automata.

c) CFLs can be recognized by deterministic finite

automata.

d) CFLs can be recognized by regular expressions.

29.The Chomsky hierarchy of formal languages includes all of the following except:

a) Regular languages

b) Context-free languages

c) Context-sensitive languages

d) Decidable languages

30. Which of the following is NOT a property of regular

languages?

a) Closed under union

b) Closed under intersection

c) Closed under complement

d) Closed under Kleene closure

31. A Turing machine with a finite number of states and tape

alphabet is known as:

a) Universal Turing machine

b) Deterministic Turing machine

c) Finite-state machine

d) Decider Turing machine

32. The concept of recursion in formal languages is associated with which type of grammar?

a) Regular grammar

b) Context-free grammar

c) Context-sensitive grammar

d) Unrestricted grammar

33.Which of the following is NOT true about a regular expression?

a) It can describe regular languages.

b) It can be converted into a finite automaton.

c) It can describe non-regular languages.

d) It can be used to perform pattern matching in strings.

34.Which of the following is NOT a property of context-free languages?

a) Closed under union

b) Closed under intersection

c) Closed under complement

d) Closed under concatenation