SN TIME: yor [3 Obtain @ DFA to accept Strings of a°s and b's having odd nu 27 Draw a DEA Model Que’ Toe 1a | Fifth Semester B.E. Degree Examination TON THEORY OF COMPUT 1. Answer any FIVE full questions, choosing at least fo2, Draw transition diagrams wherever necessary Module tofa’s and even number of b's. i cept deSinal sings ovale by 3 Define the following terms with example LD Alphabet iy Power of Alphabet i) Languages —_ stion Paper-1 with effect from 2022-23 (CI BCS Scheme) Max. Marks: 100 NE question from each MODULE. OR, Ghia an & NFA Which accep sings consisting of 20 oF wore ws followed by zero or more b's followed by zefo or mote es. d Cor ‘] Deine Detemninas inte Aviomata, Explain the wo pref __|> | tstisar far desctbing the Tension Eynction wih an example. _| x Obtains DEA forthe ]Tawing NFA osing lay evalaiion methou OI wh ° 1 | start Zo, . | al ot Ot.) accept Le a pe ee | Mo i 05 [ohm applications oF RE: What are the notations used iv UNIX Operation cory 5 is 1 stem? Liat few Regular expressions with its UNIX notations iran €-NFA for the Regular Expression (9°) Bb (a*8)* cor |-6 the minimized DFA ofthe following coz) 9 | sfojr | Sige | BLATC =a pila =D Lee | pets =r oR Qui Ta] Define Pumping Lemipa, Prove that below language is nota regulr| 2 | COR) Language. L={a'b!|i>j} Develop Regular expressions for the following Languages on = [ a, D} errAccopr sigs Tas ands whose filth symbol from the right end is, Hy Accept strings ofa's and b's contuning nt more than 33. Find Regular language accepted by the following FA by liminating states? Page 01 of 02Module-3 amar? Explain the Techniques for redveing with suitable examples he following grammar is ambiguous by waking the sring ah bS Lc . ia oo fe Context Free Grammar forthe follow ORT AE set oF all strings with ty more than three as | when E= {a,b} To accept the set of stings with any umber and 5 | _with at least one a The below Graminar obtain the comesponding PDA ADaBla, B>DAlb "CP a_ S$ aB ba AP alas |bAA B b/bS |aBB. For the string aabbaby, find a joni) Rishtmost Deri FG. Design CFG forthe fllosing Langues: Consisting of st of ll non-paindromes over ={8.0)~ k= {or n20} {ab}, wis the reverse of w}-— Module-t Deine the Flowing with suitable samples, is Language. (ii) Chomsky Normal Formst~ ff fai Groibach Normal Form. 2 cor {y Remove all die cproductions and Unit produetions Foo the J exammat: S3aA[aBB__A>aAA|c BO bBIbIC _C>B i CoH i © Hetine GE, Conver the following grammar into Gr SSABI{O AD O0A|B BO TAL atid GB cos 8 OR @.08 [a Lafrite the EMD, RMD and Parse tre for the string: +*-xyxy 7 using the grammar __E > +EE | *EE | -EE | x | GB Cor 6 Jy Obiain the following grammar in CNF: LF" | sr ashje AD aAS|a __B SbS|A|bo 3 cor 6 Define CNF. Convert the following grammar into CNF © |S>0A[1B AD OAA/IS[1__B 1BB|OS|0 ie cos 8 Modules a [g }Define ‘Turing Machine. With a neat Block diagram, explain the 7 the working of basic Turing Machine COs 6 |] Design a Turing Machine to accept all set of palindrome over (a,b)*, Draw the transition table and also transition diagram, Show the sequence of IDs forthe string: “abba” iB ‘COs 6 «| Wate a short note on 4) Mulitape Turing Machine | +) Nondeterministc Turing Machine D2 COs 8 OR Q.10 Ja | Briefly explain The Techniques for Turing Machine construction, Also \write applications of Turing Machine. 2 [1b [Design a Turing Machine to accept the Language: ‘COs 6 sili Page 02 of 02fo the transition diagram and show the moves made | Saaaabdb fachine to accept strings formed on Write transition diagram and sequence of IDs for 1y* and Todicate as L1, 12, L3, L4, ete, Iti also desirable to indicate the COs and POs 0 beo © 1 b) Draw a DFA to accept decimal strings di ° 5:6), be (yg %.-) co(2,5) 8) Xmoolan g Omedseo.— Vmod ey Dewd Seay BmedS=0 mod $=} IMEI QL Sj eye Bao) doo 2100 G poe 22-50) ae ‘ Q 2 a) Obtain an & NFA which accepts strings consisting of zero or more a's followed by zero or more b’s followed by zero or more ¢’s.P Sdeodiny Stule ef DPA 4.3 —— & wet Sumbels E-Jos Consol she & en input © &) §(A,0)= S(a,0) —\So(m D=fnln1) = 6, (4,0) Biles ae 2 SEE Conds Slat & om Input OG) 8o(B.0)= Su(f%e9ho) | (8.1) =Sn(P2,4,)1) = 44,4, %3—p = 14, %§-e Consretrr Shek © §(¢,0) = &u(%o) (41) = Su (4, D) =fa3—F =f le Condin St DBD 9 inpet 0 § | S(D,0)= Su (84 9,%3,°) = $9,9, %5—D %(, 1) j} ee) Ne 2pt strings of a's and b’s whose fifth symbol from the right end a (orto 3'a Carts) Cats) +n) (rts) ii, Accept strings of.a’s and b’s containing not more than 3 a’s. | bas e) Yearey carey o! Q 4 c) Find Regular language accepted by the following FA by eliminating states? mn Bates?Ow that the following grammar is ambiguous by taking the string aab. 85 0$b8 BO Onks => aaSb3 >aaibs Daas >aab => aab a - S } @ q Ths Cy Me tg amb — 5 c) Design the Context Free Grammar for the following Languages. i) To accept the set ofall strings with no more than three a's when % = {2b}. S— BABA BAB A> alé a> pele ii) To accept the set of strings with any number of a's and b’s with at least one ~ — S4a8|bs\athe below Grammar obtain the corresponding PDA Arun gramman 15 G@ne S>ahRC A>aB)q BobaAlb “sug C>a Push sierhry Sumbeal 3 into the Seek Lid) Bo input Symbel §(4.,¢, %) = 4,2) Ries ADAkABC 30 _—_. aa Swabee 8 (4, 4, 2) = CF, ABc) A> aB £(4,.4,4) = (9,2) oe 84, 2, 4) =(4,€) 64, 6, B) =(4,A) B>b a ety 6 B) = (4 €) 4 ame 7 C9 2) Set Dyalty me to Rrod Mere tote any np Sarntorde 2a Bi )= (%,&) <<G be the Grammar S-raB | bA he + ban [aS|a al Rmp 3>5a8 ee => aars S = aapB ag aabe A RabbS 53 aq BbaB Ns oi > aaBbabs Aalbabs => a0 boa bab. Beets ga Qbabvab mob baba eoiag bbabab _Q.6 c) Define CFG. Design CFG for the following Languages: 77) Consisting of set of all non-palindromes over © {a,b} $5098 |bSb |ahb|bAa A> af] bale i) L= {0° |n20} cae Ol] Sos! |! iii) L= (wew®: we {a,b}*, wis the reverse of w} alkeeea [Saga [686 Le | LtRemove all the productions and Unit productions from the grammar: CaO! A> adA\c B> bB | bbC CoB NUubot verter = 953 Resch Gouna 8 ak |o \aBe A> adh lata B® b®\ bee e> 2 S> ahla [ ope A> att far ta B> bB] bbe e> be|bee\00A |B BoIAL Lot Peoduclin A> 8 Sasi lo A> o0A\ 1A B> TA) 2 Repl Ode Be Repleainen'? ' ao | Bi | S > Ave |o A> Bobo A| BAB: B> BAB Bo 6 Bi? | Reph AB wri Do Rept Bih worth Do. D> AB Da > BA BoB. osvth Dd, ne D> BoBo S DoB A> Oph | Dc8) B> 008) D> BB Ror O Dos BA Bi}-Ao, ASA, B=Ag) Bo= As, BRA, Do=As, D1. = Ae & Do = Aq Ns > Achy |o me eur A> Been] Aamo SB UP ON i n> Agha, peas A783 0 _ AGD IA As 3 Aw Ne D | 1h Be & be tn GNF ALD obs hy [IAW Ay Ae Ag Aa 1 biG v/ a m Que- Ag > Comat | thrha) Aa Sa As Ofefi Ae | 1d Ag Aw ye As '9 GNIF A, > (6dr Aids J Aude) ay /0 uae > ototn Ar Ay 1A Ay Ao by |\ rite the LMD, RMD ws RMD andl Paise tree for the string: 4*-.x¥ using the Fo HEE |-RE[@EE|xly MP £> +e KMD > "epee E> + EE => 4 - BeBe => +By = 4 mn eek => +x ey => 4 — 4 BB > txeBay > roy — Cy XB > 4 or-Bexy => +e By ey => pro my syA004 [IS] 1 1B LBB | 0S\0