Question Paper of CS -73 Theory of Computer Science Dec – 2003

Ql(a). Define the following concepts formally:

(i) A deterministic finite-state automata

(ii) Push-down Automata

(iii) Non-Deterministic Turing Machine

(iv) Undecidable problem

(v)Languageoveran alphabet

(vi) Recursive function

(vii) Context free grammar

(viii) Godel number

(b) State the relation between regular languages and finite automata. Discuss through a simple example.
© Fill in the blanks:

(i) A relation that is reflexive, symmetric and transitive is called a/an _______ relation.

(ii) A________number is one that is the product of two natural numbers, each greater than one.

(iii) A language is Turing-acceptable if and only if it is generated by some ————- .

(iv) The class of languages accepted by finite automata is star.

Q2(i). Give a Deterministic Finite Automata accepting the language of the set of all strings over {0,1} such that every substring of length 4 contains at least three 1’s.

(ii) For the following language, give a proof that it is or is not regular:

Q3. Construct one grammar for each of the following languages:
(a){ambnm>n}

(b) {W e {a, b}* W has twice as many b’s as a’s}

Q4. Construct Turing machines that compute the following functions:
(i) f(m, n) = m - n

(ii) f(m,n)=m*n

Q5- Show that the following functions are primitive recursive:

(i) sum function : f{m, n} = m + n

(ii) power function : f(m, n) = m”

Q6(a). In the context of uncomputabUity/unsolvability/undecidability, tell for each whether it is true or false.

(i) For a decidable language L, its complement I may not be decidable.

(ii) For a given Turing machine M and an input string W, the problem of deciding whether M halts on W is decidable.

(iii) For a given Turing machine M, the problem of deciding whether M halts on every input is undecidable.

(iv) For two given Turing machines M, and M:, the problem of deciding whether they halt on same string is undecidable.

(v) The problem of determining whether for a given grammar G, L(G) is empty is decidable,

(b) State the following undecidable problems:

(i) The Halting problem

(ii) The Post’s correspondence problem

(iii) The Tiling problem