GATE GATE Theory of Computation 1

Question 1

Which of the following languages is NOT regular?

Accepted Answer

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

Answer

The language {a^n b^n} requires counting and matching equal numbers of a's and b's, which exceeds the capability of finite automata.

Question 2

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

Accepted Answer

3

Answer

A DFA with 3 states (representing remainders 0, 1, 2 when divided by 3) is sufficient to accept all binary strings divisible by 3.

Question 3

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

Accepted Answer

Type 2

Answer

Type 2 (context-free) grammars have productions of the form A → α, where A is a single non-terminal and α is any string of terminals and non-terminals.

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

The subset construction algorithm for NFA-to-DFA conversion can produce up to 2^n states, one for each subset of the NFA's n states.

Question 5

Which of the following problems is undecidable?

Accepted Answer

Equivalence of two Turing machines

Answer

The equivalence problem for Turing machines is undecidable; no algorithm can determine whether two arbitrary Turing machines accept the same language.

(GATE) Graduate Aptitude Test in Engineering Practice Test

(GATE) Graduate Aptitude Test in Engineering Practice Test

GATE GATE Theory of Computation 1