18 NOV 2018 Reg.No. : Amrita Vishwa Vidyapeetham School of Engineering, Bengaluru Campus B.Tech. Degree Examination November 2018 Fifth Semester Computer Science and Engineering 15CSE303 Theory of Computation Time: Three hours Maximum marks: 100 co Course Outcomes COI | Understand and apply the properties of formal languages C02 _| Illustrate grammar and grammar transformations for formal languages CO3_| Construct finite state machines CO4 | Apply stack data structures for automata COS _| Design and develop computing devices such as Turing machines Answer all questions 1 (@) Find the language accepted by the DFA given in Fig. 1 a 2} cor (b) The automaton Ay is specified by the diagram given in Fig, 2. [3] Co3 i) Translate the graphical representation of Aj into the form of a S-tuple, (S,2,6,50,F). i) The transition function is 6 and the extended transition function is 6*. What is 6*($0, 00010)? Show the steps.4 (©) Design a DFA to accept the following: All strings that start with 0 has odd length [3] CO3 and that start with I has even length on 5) = {0, 1). (a) Let M denote the non-deterministic finite automaton and L(M) denote the [4] COI language accepted by M. Define M and L(M). (b) Given the Nondeterministic Finite Automaton (NFA) A over 2= {a,b,c} [3] CO3 (Fig. 3), which of the statements about A are correct? Fig.3 abe € L(A) and cba € L(A) A accepts precisely the strings which contain the sequence ab. A accepts precisely the strings where neither of the last two symbols is the symbol . (©) Draw NFA to accept all strings matching the regular expression ((01)"+ [3] COS ‘1)+0+using Thompson’s algorithm, (@) Convert the NFA given in Fig. 4 to minimized DFA using subset construction [7] CO3 method. Fig. 4 (b) Identify whether the following languages are regular? 8] col i) Lt = (0*1"2" | (k = morm = n)andk + m+n > 2 ii) 12 = (0'1"2"|(& = morm = n)andk + m+n <2 iii) 13 = (012"|k +m +n > 2) (@) Derive the regular expression for the automaton given in Fig. 5. B] cos Page 2 0f 418 NOV 2018 (©) Let REPLACE be an operation on languages such that REPLACE(L) isanew [3] COL language that is identical to L, except that each ‘a’ in a string is replaced with “ec. For example, if L = {a, ab, aabb, bbb}, then REPLACE(L) = {cc, ecb, ccechb, bbb}. Show that the set of regular languages is closed under REPLACE operation. (©) Which of the following are true? Prove your answer. {4] cor baa €a'b*a‘b" bra’ Nath = at ube ii) ab ned"=0 iv) abed € (a(ed)*by (a) Find the S-grammar for the regular expression (aa"b + bb‘a). Is your [3] C02 grammar regular? Give reason. (b) Write a regular expression to recognize all the valid monetary amounts starting [3] COI with the Rupee symbol ® with an optional decimal point and a two-digit fractional amount; if it is larger than three digits, then commas separate billions, millions and thousands (e.g, % 101.99 or & 10,000 or & 1,670,439,444.49). (©) Generate the right linear and the left linear grammar for the language generated [4] CO2 by the regular expression (a + b)*a(a +b)". The syntax of formulas of propositional logic over the atomic propositionsp, q, ris given by the following rules: © p.q.r-are formulas. + true, false are formulas, If Aisa formula then A, (A) are formulas. + IfA,Bare formulas then A A B, Av Bare formulas. To avoid ambiguity,consider the following precedence rules: ‘© binds stronger than A and v (i.e. — holds higher precedence) © Abinds stronger than V (@) Construct a CFG over = {p,9,7,(), A, V,-ytrue, false} [4] co2 whose language is the set of syntactically correct formulas. Designyour grammar such that the conventions about binding strength arereflected by the parse trees. (b) Draw parse tree for p A (qv 1). B] C02 (©) Show the left-most derivation for p A q Vr. B} co2 (@) Consider the context free grammar G = (V,5,S,R) where Vis {S,A,B), Sis [3] C02 {a,b} and R consists of the following rules: S>AlB AaS|a BobS|b Is this grammar ambiguous? Justify your answer. R Page 3 of 4&) @ i ) Consider the following context-free grammar G that describes regular [7] CO2 expressions over the alphabet (0, 1}: R > (R)|R+RIRRIRe [Ol The alphabet of G consists of the symbols (, }, +, , 0, and 1. Here + and deseribe the union and star operators, while 0 and describe the minimum string. Represent the above CFG in Chomsky Normal Form, Construct a Push Down Automaton (PDA) for the language L = {ab"a"'b™ + [10] CO4 n,m 2 0}. Draw the transition diagram for the construction. Consider the Turing Machine (TM) automaton given in the table below: a a (ee eet [SLOR)[2YL)_-_[GLYR) = | {(s2,0L)] - [G6O.XR[62¥D] — | P = f= [= se [65 a ee a Show diagrammatic representation of the above automaton. 22] cos Show the trace (ID) of the above machine for the strings 0011, 0110. [4] cos Given TM(T) with f = {0,1,B}, 2 = {0,1}, Bis end of string, and 6 as: [4] cos [input 0 [input 1 [input B q0_| GI, 1,R) | Gl, 0,R) | @l,0,R) al_| @2, 1,1) [G@l. 0, R) | @2, 0,1) initial tapes, determine the final tape when T halts, itial position, For each of the followin; assuming that T begins i -]B]B]O[o]1|1[B]B B/B]B)B/B)B]B]B].. Define the following: [10} cos i) ‘Type 2 grammar ii) Multi-dimensional Turing machine Linear bound automata Recursively enumerable language Language that is recognized by the finite automata Page 4 of 6