GATE CS Theory of Computation MCQ Questions

Q1easy

What is the main difference between DFA and NFA?

A)DFA has more states

B)NFA allows multiple transitions, DFA has exactly one

C)NFA is faster

D)No difference

Q2easy

What type of language does a Finite Automaton recognize?

A)Context-free

B)Regular

C)Context-sensitive

D)Recursively enumerable

Q3medium

What is the pumping lemma used for?

A)Prove language is regular

B)Prove language is NOT regular

C)Construct automaton

D)Generate strings

Q4easy

What type of language does a Pushdown Automaton recognize?

A)Regular

B)Context-free

C)Context-sensitive

D)Recursively enumerable

Q5easy

What is the most powerful computational model?

A)DFA

B)PDA

C)Turing Machine

D)NFA

Q6easy

What is the Chomsky hierarchy order (weakest to strongest)?

A)Type 0, Type 1, Type 2, Type 3

B)Type 3, Type 2, Type 1, Type 0

C)Type 2, Type 3, Type 1, Type 0

D)Type 1, Type 2, Type 3, Type 0

Q7easy

What is a regular expression for all binary strings?

A)(0|1)

B)(0|1)*

C)0*1*

D)(0+1)

Q8easy

What is the purpose of ε-transitions in NFA?

A)Accept empty string

B)Change state without reading input

C)Read multiple symbols

D)Reject strings

Q9medium

What is the halting problem?

A)Decidable problem

B)Undecidable problem

C)NP-complete problem

D)Regular problem

Q10easy

What is the complexity class P?

A)Problems solvable in polynomial time by non-deterministic TM

B)Problems solvable in polynomial time by deterministic TM

C)Problems solvable in exponential time

D)Undecidable problems

GATE CS - Theory of Computation