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.

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

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

Ql(a). Define the following concepts formally:

(i) Mealy Automation

(ii) Godel number

(iii) Context-free language

(iv) Non-Deterministic Pushdown Automata

(v) Regular Grammar

(vi) Primitive Recursive function

(vii) Non-Deterministic Finite Automata

(viii) Universal Turing Machine

(b) State the operations under which each of the following class of languages are closed:

(i) Languages accepted by finite automata

(ii) Languages generated by context-free grammars

(iii) Languages accepted by Push-Down Automata

Q2(a). Construct a deterministic finite automata accepting the following set:

(b) Describe informally the language accepted by the Deterministic Finite Automata shown below:

Image No.12

where E denoted initial state and F denotes final state and (a, b) is the set of inputs.

Image No. 13

Q3. Construct one grammer for each of the following languages :

(i) {w e {a, b}* : w has twice as many b’s as a’s}

Q4. Construct Turing Machines that compute the following function:

(a) f(m,n) = m*n.

Q5. Show that the following function are primitive recursive:

(i)f(m,n)=2m + 3n

Q6. Mention two problems, for each of the following domains, which are undecidable:
(i) Turing Machines

(ii) Context-free Grammars

(iii) Grammars (Non-context-free)

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

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

Quastione Paper of CS-73:Theory of Computer Science Dec-2001

Ql(a). Define the following concepts formally:
(i) Deterministic Finite Automata

(ii) Regular Grammar

(iii) Context free language

(iv) Non-Deterministic Pushdown Automata .

(v) Turing Machine

(vi) Primitive Recursive function

(b) State the operations under which each of the following class of languages are closed:

(i) Regular languages

(ii) Languages generated by context free grammers.

(iii) Languages accepted by Turing machines.

© State the relation between regular languages and finite automata.

Q2(a). Construct Deterministic Finite Automata accepting the following language:

{w e {a,b} * : each b is immediately preceded and immediately followed by an a}

(b) Describe the language accepted by the Deterministic Finite Automata shown below, infomally

Image No. 12

where F denotes the initial state which is also the final state. E is another state. Also {a, b} is the set of inputs.

Q3. Construct one grammer for each of the following languages:

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

(b)wwR:we{a,b}*}

Q4. Construct Turing Machines that compute the following function:

(a) li(m, n) = m - n.

(b)II(ni,n) = m*n.

Q5(a). In context of primitive recursive functions, state the initial functions and rules of primitive recursion and composition.

Initial function

(b) Show that the product function f(m, n) = m*n is primitive recursive.

Q6. Mention two problems from each of the following domains, which are undecidable:

(1) Context-free Grammars

(2) Grammars (non-context-free)

(3) Turing Machine

Question Paper of CS-73:Theory of computer science June 2001

Ql(a). Define the following concepts formally:

(i) Non-Deterministic Finite Automata

(ii) Context-Free Grammar

(iii) Pushdown Automata

(iv) Non-deteministic Turing Machine

(v)Godel number

(vi) Unsolvable/Undecidable Problem

(vii) Primitive Recursive function

(b) State the operations under which each of the following class of languages are closed:
(i) Languages accepted by finite automata

(ii) Languages generated by context-free grammars

(iii) Languages accepted by Push-Down Automata

© State the relation between regular languages and finite automata.

Question Paper of CS-73 : Introduction to computer organization June 2005

Q.l(a) Give an NFA equivalent to the following regular expressions:
(i) ba + (aa + b) a * b
(ii) b + aa + aba * b

(b)Induction step :
Let m =(m1,m2,…..,mp)e NP

© What is Ld, the diagonal language? Give a construction for Ld .

(d)(i) Define Kleene’s Closure with an example.
(ii) State the Pumping Lemma for CFL.
(iii) Check whether or not the sets accepts by any FA are closed under union, intersection, complementation and concatenation.

(e) Define Decidable and Undecidable problems. Give two examples of each.

Question Paper of CS-73 : Introduction to Computer Organisation Dec-2004

Q.l(a) State the operations under which each of the following classes of languages are closed.
(i) Languages accepted by Finite Automata

(ii) Languages accepted by Pushdown Automata

(b) What is the difference between an NP-complete language and an NP-hard language? Give an example of a language which is NP hard and not NP-complete. Justify your choice of example.

© Give a regular expression for the language accepted by the above FA. Describe the language.

(d) Prove that a context free language is recursive.

(e) Construct a Moore machine equivalent to the following Mealy machine.

Question Paper of CS-62 C Programming And Data Structure June- 2005

Q.l(a) Write the syntax of any five file handling commands supported by C .

(b) Write a ‘C program to count the number of characters and lines in a text file whose name is supplied command line.

© Define an adjacency matrix and an adjacency list. Create an adjacency list and an adjacency matrix for the following graph:

(d) Define a graph. Explain at least two traversal techniques in graphs,

(e) What do you understand by a height balanced tree. Construct a height balanced tree for the following list: 5, 10, 0, 7, 8, 2, 6, 3

(f) Write an algorithm to sort a list using quick sort. Show it’s operations on the following list:
5, 10, 3, 0, 15, 7, 3