| Tot - Pes- 504 Tot — PIT-504 che (7 J 707 (8 i 5 com: 2014 batch COURSE TITLE: THEORY OF COMPUTATION ene raat ee DURATION OF EXAM: 3 HOURS oe COURSE OUTCOMES ‘At the end of the course the student will be able to: Ev Male edie (o\ COL To Gain the knowledge of basic concents of formal languages,and, finite automata techniques. ail ened Understand regular expressions and various problems to minimize FA, - Apply various languages to construct context free grammar. \/~ Evaluate problems relating to Push down automata and Turing Machines. L~ Detailed Syllabus Section- A Introduction: -Symb6ls, string Concatenation, alphabet, Language, Tree, Mathematical Induction Proofs, States, Transition Tables, Finite Automata, Regular Expressions, Push- down Automata, Turing Machine, Context Free grammars. (8 hours) Finite Automata: - Deterministic Finite Automata (DFA), Designing, Non- deterministic finite Automata (NFA) without E-moves, Conversions, Equivalence, NFA with E-moves, Regular expression designing, Finite machine with output assigned, Moore and mealy machines, Conversion and Equivalence. mo (12 hours) A Section: we Turing Machines: Turing Hypothesis, Turing Computability, Non- deterministic, Multitape and other es versions of Turing machines, Church Hypothesis, Primitive Recursive functions, Universal Turing “ffaltty machines, decidabilty, Halting problem, Stack Automata (1Ohours) Prafsbyys Regular Grammar & Context free Languages: Context Free Grammar, Context free Languages, reduced “Cry whip? form of Grammar, Ambiguous and Non- Ambiguous grammar, acceptors end generators) Relations between Classes of Languages, Pumping lemma of regular sets, Chomsky’ hierarchy of languages, “oh wabhasy derivation Trees. (thous) palace + ‘BOOKS RECOMMENDED: Prtfabe~ 1 Introduction to Automata Languages & Computation AN. AHO, J. E. Hopcreft& J.D. Ullman 2, Introduction Theory of Computer Science E.V, Krishna Moorthy 3: Testy Of Compultd, Selene Shinigh S. Some, NOTE: There will be eight question$ of 20 marks each, four from each section. Students are required to attempt five questions selecting at least two questions from each section. Use of Calculator is allowed. Ys Ar fbr be Formal Lamauoges Petts. Line ke Autermado. Conn & Butte) Ss Thou of Gornputts. Sounee Kup . (Ushra, Chuomala, , lang. ¥ Gompulssion) Ns ChamalAagokanarn CPA[ They ef Computation, * TOC th the brnoh hak deals wilh hour eppeliniey Problum can be Lofveol ory a Moc ef tom putlon © A a ee ae et areca : —~r YE qiuls tL theoutival Concept ef Fgh cempuotion Co, compulabitityy ) eee! dimitatien Bos Sepenpot Catse cated chatoctr.) — Supmbel fe the Sealy building block ) which won ht omy alphabet , Ltt ; plot a eT cack acne Hy Avphabus (EZ chma)— Aephabs oat Q ott of Syph?h, uslhich ort always ginite -(L cobteoon af teh ole ) wy Ze {oly fh an alphabet of binary dye Pa On tens & or alphabet oy retmal sree Z= {4b 0% +e Uaing — Shing. a finile _ bequsrret. howe auphober . A” sting. bh guntioly denaicol af (w)® tm tungth ok & string fs dined a |I- Empty tring — fe The ching, with ero beth ponee ot, Lgrbolo ) meprerintcal ag ECNVWL).Bru imoineerthe procs i¢ bast on som Theoretical meeltl - Cormpuker onginuning bk abe not om sweeption te thls . A werkt a ami tomputh in this gue dh bartel on FO Mathumahal medtl . Such a mbthemahcot modulo a Comput allows iu ip uncuustert Ye fymachoning , capability os well as the Limitabions oO com pula + Wihené tho browldge ord basic uretustoncling. of the regolith y ont ™axp Tr TOC , wt wilh dieing, vartons mathymahtal med of com putin. cles Oar cake en Ae ee Purhdown futemata. I Tuning Machine » Thue medels a ako wrepel fry vrlene applicaletrrs Ee cera pia: Golenee be enginitring. fi" af Deere cena tt TU ceca a aa aeNes ef ubingy of brat 2 rat com bE pentiatey 3 Our fhe alphabetdefi a) by ¥ * WH sob y ba | bb hingth ef String | vo] = 2. Ne vot Sting. = Conclusion — fee Uphabtr fA, bY with both n, UBEOLES Ui Sais Can be generoteot =y™ Ce one all (bt. stings . Se- this implies that lovmguayt. ty a, Subset of a 25h sek oul posible onings a ali Length ovet fo, 'Yy ieee Nae MU Zig ey wr gir E fe nu ctrng In Z* ea Lemp th bette of shing- | cas ctemote by > t har one ehina| rT i tyme 4 ee ee L= [64 Ths mioms Jomg tonsint of emphy ig € — thing. wlth Lungtiy ye | 4 — ik Ma ne ening. | G=EY — it har one shirg with Umsth aneMis A Somqucge ay | bette gtring. chesim” yom some &” EOC ar To nag o E* A language thaw cam be foumeel ou “5! con be finile ov infinite , oH th Finlle- Larguoge, Lt = £ cet g org 24 Ue f my) ye » 1444 ye ty Tafinke langeege LA = £ set of alt shings stards wlth hy L1 = { babs, baa 4 ba , bbb , baad , baaab--~Y Input symbols okt 0,4 ae poly .; pe Bee be! 4! lng, > , oe of sting = 14 L= foo,o), lo, NY dig Le £000, 001,010 yl 100, lol, Ho, INy pr L) B= fOr1Y , begin, with Cp) inpnie Le G1, lo; loll, Wit, looool--- Y Lyte [hee { Jo, 11100, 10000,- - - Cont with | fe “ond with 0 ye Powter 4s Za Csigena, ) = = tay 5°= ak oh all Ching, with umgth 0 ge ={e4 Cie nu Be [dunole, a Anyoe ghz ut of aH thing a lng eee foi+49 ae poo) ol yto, WY - oR EZ $014 (o,f BS aie Flas Hen Loc) =¢00, 01,10, NYE™ > lungtt> te (ez >) A \pas ocak \t ntoz ob Aye. aaeeeel Caxclinaltiy, — No ob eluents nee ie cardinality of; Sb. Fonte - 2 Cardinality, Oy a pit mMlant Liye OF A feb Conctinaliy of set A Is dumerd ty IAL. RA Sur of Odd posinve Inkouwy less tram 16 A> £41,3,5,3,44 Lees) Bead oh LL. See ig =O ie |ol =o @- The Caretinatite see Poe Gaal (ocean tno FO) 12--loly lo say A = $0) 1,2,---10Y % totat elemt-= 1] VPP (AY) = 39 = goueLECTURE PAD (Not for Official Use) Hr Pew aS Sigma % - —" We sepuumnt? fnput alphabet by Z=fa by Wir pow YZ swits'be Z° fe 0- Zi. S Sete gh all Shinga with length'o”. Tun it tnnin € or A Swe ew Shr = = Si 104 * atl ching» ae, Length 4) oe gio dy i eh Aghia th Seg le an etalon es ae od pea ee ba bY Fas Fed Lash 4 aul ohing. woth length eo BEES aby Cabypaiby — oO WZ fan ,ab; ba) bby {aby bs BF Oaay 1dab 7 Ob abb i boa bab bQ.1 bbb4l ps CG a i Ling au dungity), /peseibee “en tne Bese by peal ot! 3 MBS. College of Engineering & Technology, Jammu. ~spauation skp — NO ey Peieais: (ince tO aaaWith © ond with b Of Concteattin’ al, .O, \ Conmcuboe b's Cashing asith & enol with @ ,amythies Smbinskos wi madly ant all posible Und Hom deur ic in 2*- Se #u ne: Y shirgs Dau Ved Z% Oa top Ay wlll be init. language. : a me C2 giue Frotne ent ier Ag Posi tyr ft x «BE OF Shing ts possible resaibkt, @ Ta, cring in PAE since , ts Po pe ee : Ont ae iaotity Corea 5 2 st pe Me Beer Stoel s SHIPS fd. np £4 Z* but nat 2h oe inducllon te ae aie aes edinasa gre a, sf air ete ae Howey ff empl a Want wht aor ys gre 8 stent Ht, Osbitrorty Tumba, n by por preniclirg. tt te trae when 1 mA k Mary aastimirg ite Arak for TK & shoiltng. Ie 4 true fA nz RH.oy f Nothumateal Induction Pxe0 Boxed on genuvol ebeuwahorn wspeafic Teuuthy denaifioel by searoning is cobtecl induction . aoe The muthed comstct ef tte basic APS: Step-Tnduction Basiy — Ta ih the Homing point fs an Maductton He , i f pkortel that seule &s fur pos pin) yet n=0 OVE Step 2 Indution Hypothesle — Asus, the sult ie fue feb pm) = kK sup3~ Treuohiow step (Prom pin) = KFI Juypsttuats) Prone tok the xesule- tome n= k+l tramp — Sieh pollewime Aeeuted BY principle se can be Gnt™ in using In dy trus fet ra tet eect N= n (n+l) 9 lel- trduction Bats — Substitute n=] ten LHS= RAS eae eae) os } Lus = &HS Neer te x Ye) he ere i tre foe n=] s4portiests — We akuume fro sent % Induction 1 tue pv nok 14 t3 ot K = K CEH v Induction Hep — Ne howe te pro thot fre uuu tb Pree peu n= +I.+R bE = CRED CK+LH) oe We tone fe prrowe LHs = RHS 2 (kt) CerleD Jae Ba oe ecetl) tet = (ktl) ¢ ea + ret) a iene a \ Retk bekd oe ae a LMS S eHS. LHS & RHS am equa me chou fy rut fa N= K+] abo ay con be amy ner this dakemont fs True pout Vols of 1 “- Veer cia Sae toca “ne = pie (antl) \ 24 tnducHon, Basis — lo) (pAOXe PCI 1 fue Aya ACA) (2x4 HD Kae: ST) e ee 43 LHS = RHS Wt Com Sau PCI) 1% tres Yodpakony Wyp 0Mwhly — Aspume ple) is trav fparast+ ---- tke =k CEH) (2H) 4 a ¥ oe wadurklon Sep — To prom (KL) ie tue ee ar4ar4--- the +(ett)> < (kt) CeELHLD C2 (KA ED 6 ¥ (KAI) (26+ Let Cee) + eae sine at £CH) (I ND GCeE = jens (oot (ry Cortt K+ R46) = v at i 4 at ig ot eh (yrl) (ORE art 8) ms 4 4(KH) (tz) (2e+3) = (RH) (EZ) (2 E+ + 6 6 PCKtI) & truc: tt In Toc thee oe 4 Computattenal meolrL +~ }) Finlte Automata, a Putlhcdewn, Atttomato. 3: Mneay Bound Automata, Twenge Machi : Mt Jk is aera that can parte ee eds of a dengudYo L eur an t/P jalphatek Automata, — Te'ig a maching Utnich, pe rat Ce instalation Of H]w 3 Sw OM Ea Morar acc tees ee tae A pee] a ' —— + [output] Troneihery Comnputotional Mectut — A widely veeephot maelel of tompuranion fh @mpute tg— Comput, [ERI — [rg]suit = hte (A fini Stale machina A Tk fy yu clmptur machine fe setognye pattumnr Te dow nok yormmbes colt the proud inputs \ ‘ie ee or) ~enlly ft wvumt Stak Har cunt Pnpu be i an 2 mimouy In FAe ae tu ty not Hm paar, FA FA KP — ourput To types ef i \ Fa without Ol” eee Mealy machine & DEA NFA & GNF arrays Mpere machine. the clowns Vordbing, ‘aah eae Pugndewn Purtomnrala, — Thon fs ont tempered ST fy Stock Coces & Se ork. wilh be pinkie, ot Infinite )J [Toing.mesrin, — Hb a madrmmatitat mecttl / tempulahon Wat dubinvs an abthroct machint AL tm Lapinps ) ducttopt ree 0ih ro Tump * |) Rondon Accres (Mumord- is impure Twi output” ie ° my show, dvighiet wompuring pove. eee inde eet 6x tory — : a) ie a where he 8 ya, ABR Amor 000% rx 0 Re = at onup language ) hme dteigre a Finite ourterate Pr we Com idle, cee itiegget ete Hhury wa Con hay trot lamas Ko Peg ular, ST ta walle ay Pquar enprentin fee fiery Pequtor Language jek Langs Moat Wit obo >RE = aha Cat)” Ferme = 0 (+b) a Vat string “Fay Oba 4 Abba, anona , aubtoba --- 3 Ends wily bb = AP = Gaels Going J ath , by Raab ) bebd , Aamabb Yy a\o Nite a wugulas, eapresaton jo dumele a longs L Out '? ZF who Ze fad) cy weh that Cue cringe will ham, of tose one Ov! follenied by. attiast ont Number, of! b! follonceal by at bast en nombur s'0” Sting macs. up of attest one'a? suptrant Re Crepsrelory Ae aa” “t ete: thing madi up of atinst ene. (b?, Kiptant by kE= bb™ Sting mad up 9 akiast ont fe), nephrin by REZ OC” REz Wa% pork. c.c® ok PES BA hie ;