Questione Paper of CS-73: Theory of Computer Science June 2002

Ql(a). Define the following concepts formally:

(i) Deterministic Finite Automata

(ii) Regular grammar

(iii) Context-Free Language

(iv) Turing Machine

(v) Undecidable problem

(vi) Recursive function

(vii) Godel number

(viii) Push-Down Automata

(b) For the Finite Automata given by the diagram

Image No. 2

following strings is accepted:
(i)aa
(ii) aba
(iii)abb
(iv)ababab
(v) a a b
(vi)aabb

Q2(a). Construct a Finite Automata accepting the following set:
{W e [a,b]* : number ofa’s is a multiple of 3 and number of b’s is even}

(b) Draw state diagrams for non-deterministic finite automata accepting the languages

Q3. Construct one grammer for each of the following languages
(i) {W G {a, b}* : w has twice as many b’s as a’s}

(ii) {W e {a, b, c, d}* : w = am bn cp dq with
m + n=p + q}

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

Refer to DEC03,Q4(ii),Page No.-123

(ii) f(m, n) = [m ÷ n] where fora real number x, the expression [x] denotes largest integer less than or equal to x.

Q5. Show that the following functions are primitive recursive:
(i) Product function : f(m, n) = m * n

(ii) The zero or the null function:
0-m=m

the successor function
m + (n-l) =(m+N)-l

Q6(a). In the context of uncomputability / unsolvability /undecidability, tell for each whether it is true or false :
(i) For a decidable language L, its complement L may not be decidable.
(ii) For a given Turing Machine M and an input string w, the problem of deciding whether 1YI halts on w is decidable.
(iii) For a given Turing Machine M, the problem of deciding whether M halts on every is undecidable.
(iv) For two given Turing Machines M, and M2, 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.
(vi) For two given context-free grammars G, and Gz determining whether L(G ) ∩
L (G2) = Ф is solvable.

(b) State the following undecidable problems:

(i) The Halting Problem

(ii) The Post’s Correspondence Problem

(iii) The Tiling Problem