Fifth Semester Computer Science and Engineering
CS 332 - THEORY OF COMPUTATION
Time: Three hours
Maximum: 100 marks
Answer ALL questions.
PART A - (10 x 2 = 20 marks)
1. Obtain the e -closure of the states q0 and 1, in the following NFA with e -transition.
2. Show that (r* )=r* for a regular expression r.
3. Construct a context-free grammar for generating the language L ={an bn/n≥1}.
4. Let G be the grammar S -> aBlbA, A -4 ala Slb AA, B ---> b1b Sla BB. For the string aaabbabbba find a leftmost derivation.
5. What is the additional feature PDA has when compared with NFA? Is PDA superior over NFA in the sense of language acceptance? Justify your answer. 6. Explain what actions take place in the PDA by the transitions (moves)
6 (q, a, Z) = {(Pl I Yd, (P21 Y2), ... I (P. I Y.)} and 6 (q, e, Z) = {(P1 I Y1) (P21 Y2), ... I (Pm.,Y.m) 7. Explain the Basic Turing machine model and explain in one move. What are the actions take place in a Turing machine?
8. Explain how a Turing machine can be regarded as a computing device to compute integer functions. 9. Give two examples of undecidable problem.
10. Is it true that complement of a recursive language is recursive? Justify your answer.
PART B - (5 x 16 = 80 marks)
11. (i) Design a Turing machine to compute f (m + n) = m + n,v V m, n ≥ 0 and simulate their action on the input 0100. (10)
(ii) Describe the following Turing machine and their working. Are they more powerful than the Basic Turing Machine?
(1) Multi-tape Turing machine.
(2) Multi-dimensional Turing machine
(3) Non-deterministic Turing machine. (6)
(a) W Construct a DFA equivalent to the NFA M = ([p, q, r), 10, 1), 6, p, [q, s)), where 8 is defined in the following table.
(10) 8 0 1 p fq, sl jq) q jr) 1q, r) r Is) (p) S - (p)
ii) Show that the set L = la n V /n 11 is not a regular. (6) Or (b) (i) Construct an NFA equivalent tothe regular expression (0 + 1) (00 + 11) (0 + 1). (8)
(ii) Obtain the regular expression that denotes the language accepted by the following DFA. (8)
13. (a) (i) Begin with the grammar S 0A0/1B1/BB A C B SIA C S/E and simplify using the safe order (1) Eliminate e -productions (2) Eliminate unit production (3) Eliminate useless symbols (4) Put the (resultant) grammar in Chomsky normal form.(10) (ii) Let G = (V, T, P, S) be a CFG. Show that if S =>ά, then there is a derivation tree in a grammar G with yield a. (6) Or (b) (i) Convert the grammar S AB, A BS/b, B -~ SAla into softwaretrojans.blogspot.com
Greibach normal form. (10) (ii) Let G be the grammar S - 4 aS l a S b S / E . Prove that L (G) = {x/each prefix of x has atleast as many a's as b's } (6)
14. (a) Construct a pda accepting {an bn an/m, n ≥! 1} by empty stack. Also construct the corresponding context-free grammar accepting the same set. (16) Or (b) (i) Prove that L is L (M2) for some PDA M2 if and only if L is N (M1l) for some PDA M1. (10) (ii) State pumping lemma for context free language. Show that {0n1ln 2 n /n≥1} is not a context free language. (6)
15. (a) (i) Obtain the code for the TM M = ({q1, q2, q3 }, {0, 1}, {0, 1, B},,5, qj, B,{ Iq2}) with the moves 3 (qj, 1) (q31 0, R) 8 (q31 0) (qj, 1, R) 3 (q3, 1) (q21 0, R) 8 (q3, B) = (q3, 1, L) 8 (q3, B) = (q3, 1, L) (4) (ii) Show that Ln is recursively enumerable. (12) Or (b) (i) Define Ld and show that Ld is not recursively enumerable. (12) (ii) Whether the problem of determining given recursively enumerable language is empty or not? is decidable? Justify your answer. (4)
Click To Download
0 comments:
Post a Comment