Question Paper of CS-73 Theory of Computer Science June- 2004

Q1(a). Which of the following statements are true? Give proofs for your answers;

(i) Every language described by a regular expression can be recognised by a DFA.

True.

(ii) The languag L = {anb"en | n > 1} is a context free language.

True

(iii) Every context sensitive language is recursive.

True

(iv) The following problem is solvable:

True

Given a TMM and a symbol cc, whether M ever writes CC when stated on a blank tape.

True

(v) There is no push down automata that accepts the language L = {a” b1″ | n > 1}.

(vi) The function f, defined by

Q2(a). Give the production rule for Type 0, Typel, Type 2 and Type 3 grammars of Chomsky hierarchy.
(b) Construct a deteministic finite automata accepting the following set:

{w | w e {0, 1}* : number of 0s in w is divisible by 3}

Q3(a)- Construct a context free grammar for each of the following languages:

(i) L={Onlm|m * n,m,n > 1}

(b) Is every recursively enumerable language recursive? Give reasons for your answer.

Q4(a). Construct a Turing Machine that accepts the language L= {a’Vc” | n > 1}.

(b) Prove that L = {0″ lm|m^n,m,n> l}is not regular

Q5(a). L1, L2 are two recursive languages. Define

(b) Give a regular expression for the language generated by the following grammar:

S → aS | Sb | bSa | e justify your answer.

Q6(a). Find the minimal regular expression for the language accepted by the following DFA:

(b)Let G = (V,E)be a directed graph and let u, v e V. A Hamiltonian path from u to . v is a path starting at u, visiting all vertices exactly once, and ending at v. Show that LC question G has a Hamiltonian path from u to v is NP-complete.