GATE GATE Theory of Computation

Question 1

Which of the following languages is NOT regular?

Accepted Answer

{a^n b^n | n ≥ 1}

Answer

All strings over {a,b} with even length

Answer

All strings over {a,b} starting with 'a'

Answer

All binary strings ending in '01'

Question 2

What is the minimum number of states in a DFA that accepts all binary strings divisible by 3?

Accepted Answer

3

Answer

2

Answer

4

Answer

6

Question 3

Which grammar type in the Chomsky hierarchy corresponds to context-free languages?

Accepted Answer

Type 2

Answer

Type 0

Answer

Type 1

Answer

Type 3

Question 4

An NFA with n states can be converted to an equivalent DFA with at most how many states?

Accepted Answer

2^n

Answer

n

Answer

2n

Answer

n²

Question 5

Which of the following problems is undecidable?

Accepted Answer

Equivalence of two Turing machines

Answer

Membership in a regular language

Answer

Emptiness of a context-free language

Answer

Membership in a context-free language

Question 6

Which of the following is true about a pushdown automaton (PDA)?

Accepted Answer

PDAs are equivalent in power to context-free grammars

Answer

PDAs can recognize all recursively enumerable languages

Answer

Deterministic PDAs recognize all context-free languages

Answer

PDAs have two stacks