GATE GATE Theory of Computation 2

Question 1

The halting problem is:

Accepted Answer

Undecidable in general

Answer

Turing proved that no general algorithm can determine whether an arbitrary Turing machine will halt on a given input.

Question 2

Which of the following closure properties holds for regular languages but NOT for context-free languages?

Accepted Answer

Intersection

Answer

Regular languages are closed under intersection, but context-free languages are not — the intersection of two CFLs need not be context-free.

Question 3

In a deterministic finite automaton (DFA), what happens when the input string ends in a non-accepting state?

Accepted Answer

The string is rejected

Answer

A DFA rejects an input string if, after consuming all input, the machine is in a non-accepting (non-final) state.

Question 4

Which normal form ensures that a context-free grammar has no unit productions and no ε-productions (except possibly S → ε)?

Accepted Answer

Chomsky Normal Form (CNF)

Answer

Chomsky Normal Form requires all productions to be of the form A → BC or A → a, eliminating unit productions and ε-productions.

Question 5

Which of the following is a decidable problem for context-free grammars?

Accepted Answer

Membership: does string w belong to L(G)?

Answer

The membership problem for CFLs — whether a given string belongs to the language of a given grammar — is decidable using CYK or Earley parsing.

(GATE) Graduate Aptitude Test in Engineering Practice Test