Manipal University 2008 B.E Computer Science and Engineering University: ; : ; Title of the : Theory of Computation (Make up ) - Question Paper
MANIPAL INSTITUTE OF TECHNOLOGY
(Constituent Institute of Manipal University)
MANIPAL-576104
FIFTH SEMESTER B.E. (CSE) MAKE-UP exam JAN-2008
SUBJECT: THEORY OF calculation (CSE-301)
( REVISED CREDIT SYSTEM )
01-12-2007
TIME : 03 HOURS MAX.MARKS : 50
Summary: It is a MAKE UP ques. paper of 2008 of the subject "Theory of Computation" which will help students expertise their knowledge on the subject.
|
Reg No. |
MANIPAL INSTITUTE OF TECHNOLOGY (Constituent Institute of Manipal University)
msiii snp
g
INSPIRED BY LIFE
MANIPAL-576104
FIFTH SEMESTER B.E. (CSE) MAKE UP EXAMINATION JAN-2008 SUBJECT: THEORY OF COMPUTATION (CSE-301) ( REVISED CREDIT SYSTEM )
TIME : 03 HOURS MAX.MARKS : 50
Answer ANY FIVE FULL questions.
Missing data can be suitably assumed.
1A.
(i) A path is said to be_if no vertex is repeated. (1)
(ii) Show the Prefix and Suffix of the string w=abbab (1)
(iii) Explain (a) Accepter (b) Transducer (1)
IB. Prove by induction that Sn+1 = Sn + (n+1) where
n
Sn = X i = n(n+1) / 2 (4)
0
IC. Draw the schematic diagram of general automation and explain all its important terms. (3)
2A. Show DFA which accepts any number of as followed by a string b,a and followed by strings as and bs. (3)
2B. Convert NFA to an equivalent DFA. (4)
o
stait o.i -tv;-.01 Q1
2C. Find an NFA which accepts the regular expression L ( r ) where
r = (a +bb)* (ba* + X ) (3)
3A. Find L1 / L2 for
L1 = L (a*baa*) and L2 = L(ab*) (4)
3B. Show that L = { wwR / w (0,1)*} is not regular using
pumping lemma concept. (2)
3C. Show the CFG for the regular expression (4)
(i) (011 + 1)* (01)*
(ii) Check for the ambiguity of the grammar S aB | bA A aS | bAA | a B bS | aBB | b
4A. Simplify the following grammar (3)
S aA | a | Bb | cC A aB B -> a | aA C cCD D ddd
4B. Prove and state the theorem for Chomsky Normal Form. (3)
4C. Obtain a PDA to accept the language
L(M) = {wCwR / w (a,b)* } with ID. (4)
5A. Explain the conditions for DPDA. (2)
5B. Show PDA for the following grammar (4)
S aA
A aABC | bB | a B b C c
5C. State and prove the theorem that the family of CFL is closed under Union, Concatenation and Star Closure. (4)
6A. Give the definition for Turing Machine. (2)
6B. Design a TM that accepts L= { an bn : n > 1} with ID. (5)
6C. Explain the TM with Stay Option. (3)
Page 3 of 2
(CSE 301)
|
Attachment: |
| Earning: Approval pending. |
