Kus vbit ,Haliyal Febjtlas 2022 Depatment of Compule Culenee Subj » Mutomoca theo and Com petability i. (ieces) Max Havks 1/00: Ko} + Poornima Roikar Tone. Bhrs Solutron * Module t -® Define the idlnaing terms with examples. loH i AlphabeF An alphabet so @ Frsile , 0P- erm phy cet of Symbols fay 3 fon Me alphabet i. Stiag.- A a? ® a finile Sequence of gundbols@ cheatin from some alphabel 4 eer ol oc Sip as binary aphabel eof. H . Longaage sA cet of Sings all of which are choostn From Some s where 2 is & porhular alphabet ic called language . Lefe, O1, $0, 00, Ih, 10), HO, O- “| wv. Coacalenalton oF language! Le fo, toot. - y Ly zfa,b, aa, bb--4 Pe Oreo pclae ne ee bak Lae Lyta=4 2, 1,02, 1 a,b,aa,bb~}Poor of 4 Mphabet -- ae @ Essie FOP, B=ho, 1] S foo, 10, ot Ib. Desine DSH Desrqn DSN, ton Delonte Both, state cust faye 5, Ge,®) vhere & > set of stale Ze Falphabel Yo tiple Spbe| S- fransition funchon 9: OX 2 >4, My -> Star stake Fat> Final Stale a DESY. Py To accept Sharma hawin rs and even Numbes bs Sven nurbu ofth. To accept binary number drasible yo 5044) £4; je batedmnod s perf] Po 40,1,2,3, 44 defo, 4 3 je @xo4+dmede = © 644 °= 10 ° 1 je Prot lmeds =1 504,024 4, Je Axb+ dmed = 2 Blqp.0d= I> | i i 1 je CaxttDmeds-3 Ola 1) = 45 4, 0 je Qxarodmods 5G °) = Fy “i. je Covadi) mods =0 54, =o q, 2 Je xB +omeds ct 8g, 24 ° Golag BED nods = > Sg, 2492 GA pyri 40) mod $< 3 G4 4-0) =43 4! je OR UED mnods= 4 Bay 1) = —"02a Convery ty Foltoving Npes tof DESY, oer % | 2, e-Choture (9g) = 440 91 295 €+Ciosuse(4,) = fa, ay\ >o e-Ctocure 4,949} 4a taut Sah of Op . 41g eas Qp = $404 —€ Clare (Ye) = Mo y 4} 0) $14 q99,954 2) = 4AGpOPOR ~ CLlesuve S55 < Cent 4 24904,% 5 (hq09 40) 7 2) = WN visage = ctesefah = 44,99 —®) T4994, 925 OAK Mod whos =€-Uese§3 44) oy SHaiay = peytgeh me VC see rhenasAe Samay 2 2” bare ose ha -492} G40} (a) a p Byaoh, =? as faye € aed} foe} © c,+ ie 7 | by Pllosing DASH oy indentfyng er ebb). Hinin ire hable sand non -disting usa t chistingurs a ie y \2PEL_ Tabb tiling ea algrithm: pic & E[ HF ele @ AG F ¥ Ha CD Dd Hark (¢) tor dnhnguddable ctate eP vicevada - 8(p.) per GX Y iy (A,B) eh 27 Rapes this Steps 1 qien marted ri cbc parr It males (3,0) | Ce,4) 1 Cr G0 6(p,4)| C4) C4, DO lvo 4 (D,2)| Corn) C&P E)/40 (oO © 6,6] Cire) CPF) “ued (oe I Gol ce GO. © (Fd) cura) (GO G,O\@,6) C69 » Repeat ctep2 fa upmatked par’ . Yo 4 (ded OE) (mH? CByH) Cee) @pleo Go. (0, P\ Cee) (4% (9) He (FE) (b») 6o Ce, v) Fnaistinquishable pare ce.) h, ©) cB) Pistinguashable pay FB3a. Define Pequiat Expres on , Witte RE LOH. Reqular Expression fs combinalion Consist 1 choosen rom alphabet Zz of Nopal yan and opecoller Closuse (® Dorusiveydoyned 1 paa regulos enprestron denoting emphy longuet endicaty Language lor Uxprasm pion Gm, Cancale patton () th GA @ Contam Um phy ging. ih oy ie in ‘i Ae vreqolos erprasion, We Given hwo ular expresio f&, + represent tanjuaga i Lo. reply. Ra Rt RaPerepesels Longuagi (Lula Rte. requir ex press ion sera lan lL, Rr eae porgagi, Wale RE fa dollmsing languages 8 he St of o's and I's ott, ‘Pree eae rerver a RE = C+)" 000 i). Shngs of als and bis fc. Qrb*aa (Catby pesn to aceeph tnléisectimm of [arquagy \0l F faeb)* b ke having Subdefag Bb- wrile L,=la ints ee owe vequlou then segulan, Languages Cored athe: TEL, he oe es » ati met Ly & Ma Leb Reon (Bye Mot eoctpts La EN Let weeccump, oth take we PPA s bY a and Ly JH accypt Ly Og Lek cnstnich ay cier ‘ie YH an paty (0,4 Moin Fredo, npr & Sp > F004 BCP, aye ty aes Sex a acs ~ e : Hie sirulaba Rig nos M Q:8,x82 Io nig manner LoL v2 (6,2 Ra? yecoqmza a . ele head peri ge Fad es ane 5 Cpa) FxC%2> tea is & oly tt The Sine : | ka, Asis yw) ig in e 4G. ea, % rs in E ne ne my if jj @,, poe Pa) @,weé a) i: G- bray "ge BP en, , UeYe ton sa iy aga tea Wing — Keen's thm p that tw Sie R “their extsts 4 finite Soe (6,4 Bap oo at . on a & Pls wh lee Me (4,54, / & oT Bs (es (iter ae ons on oF a : ie Exprestion F jer ie O= {9 ri oF bot the stofu of Hoddinn 1 where nuh cratu : al 4 es the peer a tb 5 ee ee aoe. not geal \ eee o", er intunwedtale lake whose ee 88 ey lot rs rake ou there I> k ae Sm bao: 5 igo a vs D. be. inde cate a fale: sph sim | Foe Won ; din ts 4 oe xa rope i pf = % it chee Exar, rien 20 jy ate ip luz 20 lip fav all nufz €l € 2 Tea aj--283 Og) language = Chom eve HH) =Q -~ an inp, aes Poe 34% % fracGH wm fu nchim stoke g eath Ai dufine @ +he 6 uw 5 “ ehate of Ade a aaer veeding HE AMT YL wath ued alfa as } aaa “ aj Ys ee J La Aa k zo the ie cymbo| tis lemma for Regular longue L=foweso,if & not then there Oxi @ nw 10 L Such thot w into three Se padyz De A) yh some oy A Shing © & where mrp. jooA--<7 a4) of A ko annite £9 M4 =I Rig ae By Bi = c a3 3 ay” Ry dow ie there enith oa fon tote 1 wo ve not a torg k. _ ‘ ie. There Quist hy ede | od gtotid tq foy the pat tron a wl “en sac by sate "| ato r Sate} i. Kleen = is awe ey a" aes sie NT pe Re ‘|we Ab. Sho cia that pe Lefost: wefort™ | A oot PE eee Ln be no of ste z= i We xyZ = K Since \y\4e Ge ES ore §ony lazl Desine ee i crea 4 EAT cmeists OF Vv > sek of Vourables T > set a Fer mirals C—> Stout Syrabel p> Production Daign cee tyr fu Followmg toa + Le he [| mod 3 < x over B24 ay i) aaa] & nati _ om: SP tf a quadruple abit re LozA wee & Pra = nak} over 2-fab<} sa hB A 2ahble eed 5b Desine rrabigaty: ; ; Ton: Eqrsarnnor is arabiqum | if ee CS ho distinct pause free Bither appl te fhe bs tien a viqnimo OF elit nceqhntmos 1 @ Jetkrnost ap dvs ton * Phd ae oe M- ral jexe| |cejia14 Esper ERETE SSETE RE E> EtE > ETD i EXE ESE D>id+lre eo ees HE ee ee “Side be? Ese erideld ay) ide tdxid Bor = idpidetd Esid & UN AN va Ee t+ & ete iE if LV. id \ i \ Tive aactineh re ee camé ching arid xtd Hen go mat ambiques: ba lohat ¥s Chomsky Normal Pov of CFG 2 tO Crammer fs in CPN fase i all! production Qxe of fern joe © A 2a BCE a€é Comert Folie cramer to (NF > ABC Bab oak Bat |o24 g> bBb|>\ D co CALAC Deei, Gliminate € ~ production. p Doe . { 55 recl BaB Avah |Baljaaa p> beblale ( CAIAC “Shem - voit production oe nec] Ba8 A-sah|Batlar¥ B> bBbla CS CALAC duct Chaminade useless pe sp tind tH “thy Vi vastabla oy ie fo fexrarnal shee Ast p ieee Veo te lad B» bBbIA edule »Convert dhis (nip CNE Sorry , Thhodule new ae | 7 oe pu Lapa. Abob SDBAgB B > ApBAs}a A ‘ Aoa Ap ab A) 2 AaB Ay BAb Loo Bb. What ts NPDA® Design NPDA fev language 10 Ls far? Joxny Drove hansition Agogran « Lorife Sequtnce of moves node by NPDA ‘to accept the shim oaobbb. Ppa ts defined aa H2(8.4,T, 2040,8© Where Q > set of finile cet of Gate AD wo atphaloeh p> stark alphabet Zo > stark content A> Stout ctaleP-> Final state 8: (Ax 2x7) 2 C8, %) g: axfzve4xr > axt™ 8% = (45.4%) B42 4) = Go 2%) 54,6. a) > (4, e) (4, b = (4, © &(q, 67 ) =A %) Piya sate a (42 emnphy ctork. pale aia ( a . bale a ee. Biggs aanbel, z0) pP[q,, ,aavbh, a) +g, , abbb, nals) tg, , bbb, aaa) Uy, bb., aaZe) Hla, 0.20) Ifa, ey a) . L-(4,, 1 22)Hodule - He. A 1g Design qu tor wocwe ever s-ho,1} bate transitive diugrom and ID fy we lolelas Ih. Le nowk 4 oho ie 001c J00- c (4, ©) 709, 8-R) Fy, B= (4,8 © SC4, = C2. | 8la AS oe ¥ ») 5Cq i i jo (qo, 191101) |g Joteto 1 ge ie1oy -—ng,leto! FA014, 101 P—toleq Jol Hy+b. Explarn i7hu Iilape irs Non ~deterministe TH ee ‘tape is TU t- Have multiple where eoth eh’ head Con move Multitape acrased voith & ee head « v Podependeatl y oF Other neade. Initrally the mpl is 09 ee fore. blank At Ait fist ie ns, nk “4apel and es _ ei oc red dhe vo on 2 Other es Nok the machine ae eoasemutne Tinta under ite fod and TH pals & syne ) onveath dpe and mov i heads pep Tal Mult -tape B84 ore Bb Q. is dhe BX Pape, tPA . eymbo |» ORB 8x canhitt A aj, cinitot, SkoT* p> Frat Sake - Vaan aadeelmeniste TH M ceys.8-2 which hot sinle » one Wer infinite “Lapp. Fos given tate’ andl 7 duyrabo | ‘yaa acl east Pen icomn Ones Cama TN nica a 4 type Pee. “stake ot finite solu > Sipe :| Turning matching - Explain the voerkirig of W ObH: f gay Pesne cueing mathine- Ans Turmmg machine ix pnodfted vercten 0€ PDR 5 ts mouth more peor sul ° than PDA Tum pnotldne (TH) M is defwd of 6,2 a ie 2,17, 8 ) 4! 6 ois cerod Stabs Cginite) S > eet of inp alphabet Top ° bape Syrel J ¥ > transition unclim ax 12 ext” hue _> blank. cho loniatng of TN Fa tamcng Gtgelina ibe! 8 Ahan in B bela. TH is Finite atlas WBreciea t0 ee head fac (sel J Pood frovite hod - with the Follsinge com pone + Tape , froderorte ad , L Al Con { unit S . Tape: is wed to dare the tnfermactteg ond 1S divided a a cell can Share The injormaro of one of The sting & Sco ed Srono ait on He Jape ae = a Redd havite lead :- a syeab0| fine ahere Hs pout jo and if can wale tate the ae 4 xeoting fro TOP oy eu voto the Conbe| Und The tape te determined ‘© ombal unit + the achn table ie tansitimn Jglle and tar out d -roove titer fowasds elt # concwlle the Jags. The sead fovile hea Byeb. Design TH to aceeph the la ree L= fo? 192" | n2-0} Driv the ei deg tovite Sequence of moves made by TH tn Shin OON22 - { L- onirat]n204 84 P= (4% ey Q) 8(q,,2) = (4, 0; ) Sta, y= O41 Y R) 54, > Cg », @ BCq, = (ar 1 gD §lq,2a2 G4, © R 5a, C45, Z, Lb) 509, D= 42,4 LD d(4, 1) = C3 >) SC, Y= (4, 7%, vy) °C, od = 9! =) 59, = Oy ¥-®) Repeal this step ite Sa, >= OyY, ® fas D> (449 /) 4, De ez Rg)8C4,,Z, Qc Ca, 2,9 : - Tag, & = Cay 8 2 alee $i tye 0) ye. Zee Ye 0) & A he eM ¥D of (49/ p22 E = Xgl 22 bX 04,1129 yoo KONE AP pK Oy ZAR p07 4, EXO 1422: i KOygs he 1 — KOE jor pes Pawo z2 xo 1z2 LX MHYFZR enh 1g 22 PKK G22 & LoRny Se _ RAYA Z42 PKS | Xx VEZ JK AV VZE ETM HAR ILE — Gg nkvIZe X% wad ye oR XY GEL pat 22 KY 24 O ROY IEEE peeves fx XN IZBL, :Hodule S oe aha’) Explain Heating parblem tm “Tuan ie i ie img rwatbone CTH) bate Sagar — BMA amd on WT SMG" Problem '- Does th qu finrsh + com of Shing m a fine number of SHeps~ The = ankwur ye Cth Yes OY nos Prod Me Fist pe pol} assume thot such a TH piss fo solve this aaa ond thon’ we wl Sow it is confsadicting Heel jwosicall this Teor cnathint of & Halltinoy machi ne « é re a “yes oF ‘no’ tn a Finite amet me- Fiatte amoutl sAauhine Finishes tho t ota Lit halk eo rope») t %e Hosting Q mle J» No Curt dee hot halt on ihpr ne Gipp lication of Turing mle. o GH Ans “Tuning emohine tS wed to Solve ctcussively. gynumeralle lem - ~ Used tor brewing, complexity theory: x used poe ncwol nehoo irnplenceatalira y Wed on avith mic sohermalion theory and - Newity crude » cofhwort esting J) high perlortraree iweentn: Compan » soktwart tng xt ic % Wedd orn ‘ ul ; KM ye Coane h me nee ax eyepresion dertana ‘| ‘ anina Soherenti brouls winqe. Explatn Pocusively Grmenavall Janquag ae A Longue g ie Cea peat 2numerable 4 and 2 onty M there exttts o TH cuch Yhot Lz Ty heve 4) ate ) TCH) 0 the language aecepted by Let M = 8,4, 1,5, 4,,8/) be Tm , the language LOM) nce pled by M ardebined ay Lewy = hus | age Pep 2 peeee td eA where qo” tc mbail LD iPr the Shatng yo whih the fo be scanned. Sholl wet tod vith intmigy tor of blanket: initially » the raachin will be chat Sate 4, with wad vite heath yBomlitig to Bick syelal at etrtry Lt. Attet Gore > Sequence of mover 7 aaa othe, Mfo Snat state Lhalte , then say Shing © ic accepl ed TH. The a.cucphed by TH. pomemtted “ecunsnely an merable lanquoge ef Quantum lom : ihe lo a>. a te cpt ence oyster built peut B centointn4 ae os Peet Cai wsfermobian data & St ae eee a , ‘oan, satu © and | wheat doe data Ya eae , coo pubu is vepratatel matnemasically chow belowIW) >a > ea q yo possible dala ane Tepraened a lo>ely clastrcal Lit o ov |, qubeit can have. other than fo> & [es unlike infinile number of ¢ he cea uted os | Saas a + pil? Where. cane iL iv P Th quits 0 4 1 me called computational “bats Sala ly > 3 called Cuper position £ Use ad Jo>+pli> és talledng uetiturn Gute - qi aera jon ORO date 9 Oiaitul 6M Ne jp cetetiaine u uantum chalet etale 107 wi But >t js arro8st : tyr um far qd ¢ e Wath vata aig ¢ gtate | s> ith a pobabiling {p\* lo b- Po 2 NP Chace. 7 is Taxon machine. IS satd to be of Peainien orem at the follow holde . Cen A “Walte ake 4 ie mt, wage ny B Paattaall (OD oC Cee Cee ette ian Saree ilaee ey at Lyn oseral Tho) ouch orn ¢ Aetermintshe qu tt ae is tm Class NP tk there TS 4 Ar Laney L nbn J ther minethre TH M& & potynoraral me\ | Complexihy TCn) euch Aha L-Tlm ae tn) mor for every Ppa 4 ye al me fo.c. Church Tur oing Thats ins etalg 4 An “ebective Com eae aor algorith mic! cedure That Can be gayred Chia boca Le Lema o @ lzam * ae beings oO Computer eae Carrie oleh " Come TM. o Tn olner wurde 7 there FS ary effete pe we, ty giv odetiim oben » & 4 only i Phere is a TH prot answus yes on inputs be P cand ro de EE ea Ceres wate The. church thesis pai i} os lo contuet edels ih, unal mare porerdr] an he ex! ones “Ag A ig Closel wes be “Tunntng Ghesis aohich ctdle dhe we ae 4 kerning morhme 0 Shedv equvelet 06N- CBF Pat. Poornima Roskare- Dean; Academies KLS VDIT, HALIYAL