Manipal University 2009 B.E Computer Science and Engineering University: ; : ; Title of the : Theory of Computation - Question Paper
MANIPAL INSTITUTE OF TECHNOLOGY
(Constituent Institute of MAHE- Deemed University)
MANIPAL-576104
V SEMESTER B.E. (CSE)
SUBJECT: Theory of calculation
TIME :3 HOUR MAX.MARKS : 50
Summary: It is a regular term ques. paper of 2009 of the subject "Theory of Computation" which will help students expertise their knowledge on the subject.
MANIPAL INSTITUTE OF TECHNOLOGY (Constituent Institute of MAHE- Deemed University)
|
Reg No. |
MANIPAL-576104
V SEMESTER B E. (CSE)
SUBJECT: Theory of Computation
MAX.MARKS : 50
TIME :3 HOUR
1. Answer Any Five questions.
2. Mention Clearly each step involved in solving the problem.
3. Answer to the point and avoid unnecessary explanation.
1A. Prove that by induction 1+3+5+.......+ r = n for all n>0, where r is an odd integer
and n is the number of terms in the sum. 3Marks
IB. Construct an NFA accepting strings that have a 1 either 3 or 4 positions from the end hence find regular expression. 4Marks
IC. Design a finite automaton which checks whether a given decimal number is divisible by three. 3 Marks
2A. Minimize the states in the following deterministic finite automaton (DFA) depicted in the following diagram. Where Q3 and Q5 are final states and Q0 is the initial state of the following DFA.
4Marks
2B. Find a regular expressions for the language
L= {w {a, b} : Number of as in w is even and number of bs in w is odd}
by reducing equivalent generalized transition graph.
3Marks
3Marks 2 Marks
2C. State and prove Pumping Lemma for regular languages.
3A. Find an s-grammar for L= { an bn | n >0 }
3B. Remove all undesirable productions from the following grammar. SaA | aBB,
AaaA| X BbC|bbC,
CB.
What language does this grammar generate?
4 Marks
3C Explain the concept of an Exhaustive Search Parsing method.
4 Marks
4A. Construct an NPDA for accepting the language
L={ wcwR | w {a,b}* } 3 Marks
4B.State Pumping Lemma and hence prove that
L= { an | n >1 } is not a context free language. 4Marks
4C.Prove that family of context free languages is closed under union 3 Marks
5A.Design a Turing Machine to compute the function
f(w) = wR where w {0, 1} + 3 Marks
5B.Prove that class of Off Line Turing machines is equivalent to class of Standard
Turing Machines. 4 Marks
5C. Discuss the concept of Universal Turing Machine 3 Marks
6A. Let S be an infinite countable set. Then prove that its power set is not countable.
4 Marks
6B. Define Context sensitive language and give one example for the same. 3 Marks 6C. Write a short note on Turing Machine Halting problem. 3 Marks
|
Attachment: |
| Earning: Approval pending. |
