Question Paper of CS-73: Theory of Computer Science Dec 2002

Q1 (a). Define the following concepts formally:

(i) Language over an alphabet

(ii) Non-Deterministic Finite Automata

(iii) Mealy Automaton

(iv) Context-free Grammar

(v) Regular Language

(vi) Initial Primitive Recursive Function

(vii) Universal Turing Machine

(viii) Unsolvable Problem

(b) Fill in the blanks:

(i) For each non-deterministic finite automata there is a/an________ deterministic finite automata.
(ii) The class of languages accepted by finite automata is___________. Under complementation.
(iii) A language is regular if and only if it is generated by a _________ grammar.
(iv) Any language accepted by a non-deterministic ___________is accepted by 3 deterministic Turing Machine.

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 l’s.

(ii) For the following language, give a proof that it is or is not regular:
{x e{0,l}*| x e{01,10}*}

Q3(a). Describe the language accepted by the Deterministic Finite Automata, the transition diagram of which is as given below

(b) Construct a grammar for the following language

Q4(a). Design a Turing Machine for the language of the set of strings with an equal number of O’s and 1’s.

(b) Design a Turing Machine that computes the function that returns the quotient on division of a natural number m by a natural number n.

Q5(a). Describe ‘Godel Numbering’, briefly.

(b) Show that the following functions are primitive recursive
(i) 03(n1,n2,n3) = n3 + 2
where n1,n2, n3, are natural numbers

(ii) Pulse-Three (nl, n2, n3) = nl + n2 + n3

Q6(a). For each of the following, tell whether it is true or false :

(i) If L is a Turing-decidable language then its complement L is also Turing-decidable.
(ii) Every Turing-acceptable language is Turing-decidable.
(iii) The complement of every Turing-acceptable language is Turing-acceptable.
(iv) Every Turing-decidable language is Turing-acceptable.
(v) Given an arbitrary Turing Machine M and an arbitrary input string W, there is an algorithm to determine whether M accepts W (or not).
(vi) A language is Turing-decidable if and only if both it and its complement are Turing-acceptable.
(vii) A language is Turing-acceptable if and only if it is the output language of some Turing Machine.
(viii) A language is Turing-acceptable if and only if it is Turing-enumerable.
(ix) The problem of determining whether a Turing Machine halts on every input string, is solvable.
(x) There is an algorithm for determining ‘whether a given primitive recursive function isregularor not.

(b) Describe the following problems, and tell for each whether it is solvable or not:

(i) Post’s correspondence problem

(ii) Tiling problem