Reg. No.
B.E. B.Tech. DEGREE EXAMINATION, MAY 2017
Fifth Semester
Computer Science and Engineering
01UCS504 THEORY OF COMPUTATION
(Regulation 2013)
Duration: Three hours Maximum: 100 Marks
Answer ALL Questions
PART A (10 x 2 20 Marks)
1. Prove that "If p is a prime number bigger than then p is odd".
2. Define NFA with transition.
3. Define Regular expression. Give an example.
4. List the algorithms of minimizing the DFA.
5. Construct a CFG for the language bn}
6. Define Pushdown Automata.
7. Explain acceptance of PDA with empty stack.
8. Draw the transition diagram of a Turing Machine that can accept the language denoted by regular expression 11*.
9. State some of NP-complete problems.
10. Define reducibility.
PART B x 16 80 Marks)
11. Prove by mathematical induction that for every integer n≥0 the number 42n+1+ 3 n+2 is multiple of 13.
Show that a language L is accepted by some DFA if and only if L is accepted by some NFA.
Question Paper Code: 31254
2
31254
Or The NFA with states and input alphabet has the following transition table. Calculate ab) Calculate abab).
a
b
1


2


3


4


5


12. Let r be a regular expression. Then prove that there exists a NFA with transition that accept Or Construct a DFA equivalent to the following regular expression 01*+1.
13. Convert to Greibach Normal Form from the grammar A2, where P consists of the following A1 A3; A2 A1 A2 |a. Or Find a Grammar in CNF equivalent to a
14. Suppose L1 is the context-free language generated by productions AB| ε, 011|1} and L2 is the context free language generated by the productions DC| ε, 01}. Construct the grammar generating language L1L2. Or Explain how the multiple tracks in a Turing Machine can be used for testing given positive integer is a prime or not.
15. Show that halting problem of Turing Machine is undecidable. Or
Define Computational Complexity? Explain whether the class of Problems that can be solved in polynomial time is equivalent to the class of non-deterministic polynomial problems i.e whether P=NP.