Bengal Engineering and Science University 2006 B.E Computer Science and Engineering Theory of computer science - Question Paper
the ques. paper is with the attachment.
. <A-y , B.E. 6th Semester Examination, May, 2006
-. %y*J? vyAjComputer Science & Technology Department V\iJJ fXjjfdAi\cU . Theory of Computer Science (CST - (301)
F.M.: 100 TIME : 3 hrs
Attempt Question No. 1 and any five from the rest.
Answers should be in your own words as far as practicable.
Make assumptions as and when necessary and state them at proper places.
1. Write short notes on any four from the following.
(a) Grammar to compute functions
(b) Godel Number of a string
(c) Representation of languages,
(d)" Class of Regular Languages
(e) Nondeterministic Turing Machine to accept languages
[4x5]
2. (a) Formally define the following concepts.
i. Regular Expressions over an alphabet ii.
A Regular Expression represents a language
(b) Let = {a, b}. Write regular expressions for the following sets:
i. All strings in * with no more than three a's ii. All strings in * with exactly one occurrence of the substring aaa
(c) Construct a deterministic finite automaton to accept the language {to {a, b}* : ui has neither aa not bb as a substring}.
[5+6+5]
3. (a) Construct a non-deterministic finite automaton M = (K, , A, 5, F) to accept the language represented
by ((abUaab) *a*) *.
(b) Some authors define a nondeterministic finite automaton (NDFA) to be a quintuple (K,T,,A,S,F), where K, , A and F are denned as usual and 5 C K is a finite set of initial states, in the same way that F is a finite set of final states. The automaton may nondeterministically begin operating in any of these initial states. Formally define the concept of such an automaton accepts a string ui. Prove why this definition of NDFA is not more general than the standard one in any significant way.
(c) Given a nondeterministic finite automaton M = (K, . A, 5, F), propose an algorithm to compute E(q), the empty closure of the state q.
4. (a) Prove that the language {uju: ui 6 {a,b}*} is not regular.
(b) Prove that the class of context free languages is not closed under intersection.
(c) Show that the following languages are context free.
i. {ambn :mAn}
ii. {altPck : i, j, k > 0 and j = i + k}
5. Let M (K, E, F, A, s, F) be a pushdown automaton. The language accepted by M by final state is defined as follows.
Lf(M) = {OJ E* : (s,u, e) \-*M (/, e, a) for some f e F, a 6 F*}
(a) Show that there is a pushdown automaton M' such that L(M') Lf(M).
(b) Show that there is a pushdown automaton M" such that Lf(M") = L(M).
6. (a) Let G = (V, S, i?, 5") be a context free grammar. Formally define the concept of the derivation of UJ in
G, u 6 E*.
(b) Formally define the concept of the leftmost derivation of a; in G.
(c) Prove that for every derivation of uj in G there exists an equivalent leftmost derivation of LUin G.
(d) Construct a pushdown automaton M = (K, E, F, A, s, F) to accept the language {ambn : m > n).
[3+3+5+5]
7. (a) Formally define the concept of the function / : J\f > N being Turing Computable.
(b) Prove that every Turing computable function from strings to strings, or numbers to numbers, is gram matically computable.
(c) Construct a grammar G = (V, S, R, S) that generates the language {anbncn : n > 0}.
[4+8+4]
8. (a) Formally define the concept of a language L being Turing decidable.
(b) Nondeterministic Turing machine is used to accept languages and not to decide languages - justify.
(c) Construct a nondeterministic Turing machine M = (K, E, A, 5) that accepts the language represented by a*abb*baa*.
(d) Construct a Turing machineM = (K, E, S, s) that computes the function i\\ : M >Msuch that 7r|(m, n2,n3,n4) = n2.
[2+3+5+6]
9. Show from definition that the following functions are primitive recursive.
(a) K] :Mk-,N, k,j > 0, K}(m,n2, ...,nk)=j
(b) / : J\f > Af, f(ni, 722, "3, A4) = 9(2, ri2, n\,n\), gis primitive recursive
(c) sg: M > {0,1}, sg(n) = 1 if n = 0 and sg(n) = 1 otherwise
(d) It: Af > {0,1}, It(ni,ri2) 1 if n\ < n2 and lt{n\,ni) 0 otherwise
[4x4]
|
Attachment: |
| Earning: Approval pending. |
