SE9S20 ‘ Ta A What is universal wuming machine? Exphin its working 6 9 Design a Turing Machine that recognizes palindrome strings over 5 = (0.2) 6 PART-C 6 é Construct DFA to accept strings 0's and 1's, a Not ending with string OW in With exact three consecutive 0's prEaonsrvet Finite automata to accept the regular expression: 6 (0 + 1)'(00 + 11)(0 + 1)" go Convert the following grammar to a (ey as ro ie 103 | : i « A adBle ala ja ACs D-abalboble 9 AC 8) Convert the given NFA with cto onginary NEA e\7e2 8 fr +VaDy | YVy n> PVE c-vecla 0 Ve P| Vova | vin ore MM 2xptain the variants of turning Machine. by. Explain the variants of taming Pee cc} Construct context Sensitive Grammar for the following Tanguage L = {a"b"a?*|n > 6 zs Voce? V2 o 6 a7 ad © G& \ ° SEU TDMIBOCT Agee DFISSE9420 Total No, of Printed Pages:3 S.E. (Computer) Semester- IV (Revised Course 2019-20) EXAMINATION AUGUST 2021 Formal Languages And Automata Theory [Duration : Two Hours) [Fotal Marks : 60} structions: 1) Answer THREE FULL QUESTIONS with ONE QUESTION FROM. EACH PART. 2) make suitable assumptions and state those assumptions, if any ' PART-A wh f° Prove by mathematical induction that for any n > 0, 6 s a(n 1) z co b) Construct the minimum state automaton for the following transition diagram 8 ©) Define: 1) Extended transition funetion for NEA, ii) Moore machine h one a 028 a) Design a DFA for the following tanguages € L={abrelfn,m,1 2 1} Ny Br = (W(ab + ba) |W e fa.b)") sruct non determine finite automata for the follwing regular expression: 6 py Cons (a+ byaala + b)* G97 State and explain pumping kemimis for tegultir hinguages & thence prove that =. 6 {a'b! |i > i} is not regular 8) Construct the FA’s for the following languages * Ll= {W{W has odd number of b's, We (a,b)")) L2=| WIW ¢ [a.b)",each bis faltowed by atleast one a) Find the L1U L2,L1 ML2and lt ~ 12 4 SEDUTDEIRECTHSANOOMCCHFDEAS+ Goabrodic dion eedred: 0) ah Om gored sya aren owe =O, sens HY ice ds pk ware Cae d, teenie ep, gy send | an aoe 1bq>= 4 Ga, te, peed @=6 pa ened Be 1, Tee ht) Fae se ae Chg at) 2 16g Poel oe (lag 2 24) 4] 0 awd Be | pap eos ie 2) Shen ee Be | a ere (ba) Mg? lye = Phe (leq Lally by ed =O Ab enrod (ye 8, Tem nag 3 chan NE (lg ASS la oy 0g = 44 (te tGq 4 2) 4) = red th)=]“ae YP Stet 1 ' 1% 4 > Sajey > Ase 5h FeUs sfeyars tir) &C 1 fs (oN | BoeF 1 ep 2B (3)" + | aes = K03,D2 Sa{ ya, s) C2) f Bo= 110.3, Ga) Fee @ SOs ey 302, %)a 2 Ose 2 13-5 an al 5 vm () My 3029,4. (123) ACS Dy 5 3,4) Bae $i, 19, 24 Us) < 24) FY O): z & C3,a)2 (6 SCY Ps Ss 4 540). (ay +OLy, Sh ose Q,. Cys Fe (Ga: Ce Vac). (y ALLS, x Wk Ng \ £054 e032=- cv Pages Sabgeet (oder TEED? Aamemmens | amgmages ond ( ompenemene ame 2 ca] eg " = (RSE ALATA0E be OLA La Sietewe bon defo Oy Mia) 5 MLO) = & hal 2 oe) = & Aha) = «© MLD = ha) = RRO) = Da) = MR ® Meee © Sad = FL? 4) = GT 8) = Fa) = © dR) =D ser a= wee eh TINE LT 0-0 = iy eatennat oem ‘ 1) cmaaat 4 Selene HN be the ha niga semaine satennang sities Ae NE ie ee se eine of tes army SRRRBOH Hy arty ee etal a Whe a a Neto rama Wee + hemes 4 wd te hy etganas ive hate Fe Difireneneg © samme Hanes giannis = sm pete genre foperrorye ~ f =o Ae Coamnatones 6 eer ‘edie ty il sae evore setae ee ee eC ometene 1 Hitlister So te inane = Me AP He A She aie eee ce he 6 Cerne he 8 Re ULEAD mA fk WR le one he ‘ '- tne ie 1) Coneetoms 6 Tuanng staan 1) memgom te lll alt te nytt panies sang mm ane ob Ree tie sting a 6 Pattony oimeerne ‘ hp tm 9 Porte aeectene el meas i 5 ces oar gree ery camper Rieter of Gow FM hs RE ah ine et a at sr Heng ae eit Soeemnas— dhs Bee — Parte 8) Ais Sovatioml As aS Sa A seu a 3nd a= 2 Eaadn are. iuctoaer, without commen Aquoie. Boa. se — te +INTPaper / Subject Code: TE520 / Automata Languages and Computation 1) Wist fs Linear Bounded Automata? } | ©) Comider a grammar *G' whoee productions are gen 1 flows: | $5, Sy >S,7 lab Taf bblab Pere the ‘blowing operations on the sbove grammar: 1) Biknisation of Left Recursion | 2) Le Factoring 4) Constr « Bottom up PDA tht accepts the lowing CFG: 5+ Xa¥ |YBX ~ x—yVlay Ib ¥-+ b| bb wn PART-C Daw an A-NFA that recogsizs the flowing regiar expression over E = (0-1) + 1)01)°(011)" ‘Comtruct 2 PDA that accepts tho following b= Ing) = mG) sand efa.5¥) c) Design a aTicing mchioe to delte a symbol by changing the tape contents ftom YaZ to YZ where 08 ye (cuta)}’, s€ (£U(4)} and xeZ* Assume thet E = (a, b} ‘What are mull productions? How are these oliminatod? = _ Let. a ee he fate ‘amtomnia’s recognizing languages Li and Le resp. « \ ab * "Shxaw finbe automa that accept blowing langeages: ) UL ) iplPaper / Subject Code: TE520/ Automata Languages and Computation 44) Prove that: “If LI and L2 are regular languages than 11. 12iis also Regular Language”. (6) 26 Conver the following NFA to DFA: 6 \ x ‘Construct a context free grammars for the following languages: iL (atbme® [n+ 2m =k forn 20m e 0} 7 aSe[ft i. b= (a'r 21) 77 Sora prbt 5 5 amen owing ang fire pbs S—ubAB Sor al ARP [2B G) ate Sotdl Ete Lt Bate => BAEGn) brn | BEB LOL Jdowni PDA for the CPG with the following producti a 6) ‘Design a Fe POET Ts as E29 Bree . fhe &(aybrd= (ay, Bac) bn a = Crue I(m) P= Mr, ae) Lub Bl (mo, Be Fay arcye (a, b> “pr gn swing Noche ping lng = (S518 (a8 @) “3 Designo Tung machine forthe language over (a,b) that revercs a give sing, © ©) What is Unive Turing Machine? Eapain how encoding i peformed init wit suitable (6) Be loom . 7, Elarbnel,) a 2 AOD aA,6,7, Ga) & a2, Pr)e (Ay “¢cancobarAsbiDimR61 H2cHDDArIO £04) X/2d= Garr)y Paper / Subject Code: TES20 / Automata Languages and Computation a) Write anote on Variations of Turing Machine b) Convert the following CFG into GNF S$—4S+T|T TT id|id ¢) Design a Turing machine to compute the function : f (n) =n mod 2 4) Convert the following Grammar into Chomsky Normal Form: S> bAlaB A bAAlaS\a B > aBB\bs\a ‘Part-C What is Ambiguity in context Pree Languages? Prove that the following grammar is ambiguous: S$ + 0¥|01 XK + OXY [0 ¥ >X¥1|1 b) Obtain the equivalent DFA. Tor the given € = NFA LOPOPO“OrD eae, c) Let MU: and.M2 be the finite amtomata recognizing the languages Li and L2 ‘M2: Draw Finite Automata to accept: (i) L1UL2 (ii) L1- £2 4€3902C9DATAS61D19861342CODDAFNO @ 8) @ (4) 6) 7) (8)sta") @ + SES Fw —a)sSa, COMP 5-2 (16-17) Tega Whatis ambiguity in context free grammars ? Determine whether the following 3 grammar is ambiguous. SPS +a [Salbssissbisps. : 6 i) ign a DPDA that accepts the language > 2 L={a"b?" | n >1) validate the string aa bbbb, 8 5. a) Design a Turing machine that computes minimum of two unary numbers. 4 b) Design a Multitrack Turing Machine for L=(a"b"e "jn 1), 6 _(©)Whatis universal Turing machine ? Give encoding functions for ul” yah UTM. Encode the following turing machine. 8 dor* A AAR ala, A bib, R bb, Raja - Eran non deterministic Turing machine. 2 6. a) Construct context free grammar for the language : L ={a*"\nz=1} and convertit into CNF. 6 - Oe the following Grammar: > Wan! ar fe raheem $ > aABB | aAA SH VO 7A aBBla Prdrdy we Gane ; & B+ bBB/A Cwa ‘ Obtain push down automata. 6 ¢) Construct a turing machine that computes subtraction of two unary ‘TRUE COPY _ > 8 numbers. a sa ieCealte. TO - Na Deore a COMP 5 - 2(16-17) T.E. (Comp.) (Semester — V) (RC 2016-2017) Examination, November/December 2018 AUTOMATA LANGUAGES AND COMPUTATION Duration : 3 Hours Max. Marks : 100 Instructions : 1) Answer any two questions from Part - A (20 marks each) 2) Answer any two questions from Part - B (20 marks each) Y) Answer any one question from Part — C (20 marks) 4) Make suitable assumptions if needed and State. $ ar® PART-A é 1. py’ Prove that : "2 is irrational” using any suitable mathematical proof technique A of your choice. b) Design a DFA for the language : = x = [wing(w) mod 5 + n,(w) mod 3} Orta na eas 3), 8 c) Write a short note on: c me v/s recursively enumerable languages, Cc homsky Hierarchy. E 6 L={a"b™)m 2 1,n 2 1,nm2 3) ort {wing(W) mod 3= 0 where we (a, DI") > eles in oce() 4 ‘Obtain Non deterministic foe automata for the following regular erento: ff 2.4) aye regular expressions for the following languages : (a +b)" aa (a +b)". PTO.+ COMP 5-2 (16-17) PART-C < 7. 8) Design a deterministic finite automata forthe folowing ‘epayages : << DARL = {wiab + ba) | we{a, by") —” RDI = (wing(w) = 2 and ny(w) > = 3}. st closure properties of regular languages and prove that if L, and L, are e regular languages then L, — L, is also regular. - ¢) Construct NPDA to accapt language L = {al bi ck |, j,k > Oandi=jori=n, Q 8 ay Design a Turing Machine for the language L = (SS | Se {a, b}*}. ~ b) Construct a PDA corresponding to given context free grammar : ? P— PP [PI] pl 4 a Describe the behaviour of this PDA for the input string : (()) L}. Pi ©) Prove that : “A given lan guage L Is regular i js M that accepts L". 9 ‘egular if there exists a Finite automa= — Paper / Subject Code: TES20 / Automata Languages and Computation’ ‘Total No, of Printed Pages:4 ‘TE. (Computer) Semester -V (Revised Course 2016-17) vi EXAMINATION JANUARY 2021 Automata Languages And Computation e [Duration : Two Hoors} {Total Marks 60) Instructions: 1. AnswerTHREE FULL QUESTIONS with ONE QUESTION FROM EACH PART 2. Make suitable assumptions and state those assumptions, if my, PART-As. = Qu ‘Prove that: “If nis positive integer auch that n mod 4 is 20:3 then mis not a perfect square” (6) : using contrapositive proof technique, » og Deterministic Finite automata forthe following languages: 3 © & W [ng (W)mod 5. # ri, (W)mod 3) im ii IW || W |mod 3 = |W|mod2.where W € La, bY} ote et x0 _ AF Buse te hierarchy of fora spp a8 etn by Nosmn Chomsky ee a) 4) List and Explain closure properties of Regular Languages, oe ny £ “| Q2 BY Minimize the'foflowing DFA ‘using Table Filling Algorithm: @) » & 7 = 3A B A ee 9 as c 7 &: B a) [Ese D ‘A B D FE F G E G F G i c D S a - pr obaia Regula eins fas the following Kiperanes, i t [ Leen a cate (200 btst + (al t i, L={atb"[m 21, 221, nm 23) A. Scie pumping Lemna for Regular Languages tod hence prove that the language: L=(Caby"a¥ jn > & ke > O) ts not regular. “ 4) Obtain Regular Expression from the following Finite Automata using the method of elimination 4, of states AC3ACRDATSOIDINNSLACODAROO=o) fot goof FCqeasfio)= FG ISH) = £4egs§ + joey = fg ge? y= 6 (4424) = 5G) +e Cua) = Sus + fag — {4e.42f Qe Fae ge, feuaeh peed feed f { per Am = [ o (43:6) = a4 - Le bz = 42 inti [_Tie- $4214) 1424 Tea feat fea. as fox Soe.) 429 aif 3b (Hoa alo) = Sap, ulehe +42 = ya4e-4) 1429 C8 4241,423.1) = fas 42h fon {i a2? jesse =Faqee 8 (Saae} 2 4i+ge = tau aet 5Paper / Subject Code: TES: mn per / Subject Code: TES20/ Auto: ata Languages and (1 ‘OMPutation Te520 ti) Non- deterministic Turing Machine PART-© a) Given a Finite Automata Mf = ({A,B,C,D), fa, b), A, C}Bi - B:5(4,8) = D;6(8,a) = B; 6(8,b)= C2 8(ad Ws are ney 8(D,b) = D; aceepting the language L. Finda Regular Grammar yen a L ue b) Define Generalized Transition Graph anditsproperies wthsutsbleccames, 9 +) Construct a Context Free grammar for the language L=(0'1/2*|one of i,j.kis2 4 and other two are equal fo any positive integer greater than 0}, 4) “Given the Turing Machine M and a string W € J, docs M started inthe initial configuration and perform a defined computation that eventually halts?" Discuss and prove cc) Obtain the Nondetermnistic Finite Automata for the language desenibed by aregular 4+ expression (a*b)* (an+bb) (n+b)* S~alaPigia P— baie Q-Pa R->cRT T— bbb|bRe b) Cpnstructa DFA for the following languages bok = {w € (a, bY"|w contains odd number of a's and even number of b's} xe L-= {we (a,b)'I second last symbol of w is °b'} c) Construct a top - down PDA for the CPG G=((' T* ala}). Also show the moves of the PDA for “a “a* @ d) Write short notes on “Tuning Thesis” a) Simplify the following Context Free Grammar 6 $8 8° RT = ee ie 2 bi? %porwr © i-\ Wed; Bes t- Us a \3 Hn 25, MS Ay ? Ma gt May My09 Pas ZFarh-deb = =o n Met Wy Mee, + » > bah 1) Le> f(y) [Np(x)and Nay) is even » weve, y E026)" ii) L= fr (0,2, 2)" es positive mary integer disiibie by 4} ~ dd) Obtain the regular expression corresponding to the given finite state automation M = ((1.23), fa,),4,1.(23}) where 6 is BCL, a) = 1,60,6) = (25};8C2 a) = ® ™) 3, 8(2,b) = 1, 8(3,a) = 3, 6(3,6) = 2; Q2 3) Using subset construction method, convert the deterministic PSA for the gave a nondetermnistic FSA a ‘s) < a b) Show that the fanguaze £ = (1" | risa prime) is not regular 6 ¢) Discuss the type, language. erammar and the acceptors. of various formal languages as § jper Chomsky hicrarchy. [+ RODSeee Paper / Subject Code: TES20/ Automata Languages and Computation ‘TES20 a) Design a Tusing machine to perform subtraction of two binary numbess- 6) b), Write note on: : ae a xlended Transition Function for NFA a. °) A Rooursive versus Recursively Emumerable Languages jij, Halting problem ~ Languages. Prove that: © ©) State pumping lemma for Context free 1 = (at! In = 0} is not Context free. AC ONACADATASOIDI98612ACODDAFIOYe wey T{- ney qn airy if mye | oan eeessciel st od at ~ {abn i peak L ruth qe : whit Habit i x ‘ : av! = be WA vepare [ rape atl L tf £.a)| Deuigers TM. pea aoe ti tee ac et ES eo = Laer 1,8) — Tn eee et Slavs (farhrE 8) = Ca esbhd LS (q,+b)= tae EA cep seat tL BHOOBE ag Gqe,0) = 9a0,8) 8g. b= hg test) — nee 6G.-0)-=(4x/H) olalel [alee Io Peet! Lqsa) -L - Labs or = op peel «le le{o 5 (4,4) = erat) Lene qu AR) Gra.) oo \. ll —— = eal A Roa Ket ae aE PAGE | Ax L= {om wnat a od azo 4 = $5 Af s2. Se A ane g Ge lak taptoe oa ea S— Ba lac A= OAL [dt Ss sid b= oBlo Nel a) exe existe Deine wef LCG) that has Sableaat 9 itt Keath ce 4 Sssaale habit hamtbigutas fon woe dale Go ashes ss [sks of fssin lai of) Considensiti =. aoale (sosoo didg i”ie SV ah A abso a sN B= beo|A wz Habons A |” Oe iggy, ON so hay ! Bo ass piel — } d= upmtel! cde the Shad S5C wietliactense eat Sones 5(4s,4,5) = — Cae .088) | S>aAR § (qa, 0,8) =~ C O.ga RA) A> ase Tie aware 2 6 A> a é 24,8) = Ggu, & b> bas SC 42,6 8).= 642,88) exes re ase 5 (424,68) ‘= C42, 88) . 1= CRO F QURAN, + __| S_deusaid » . oxi 2 ewathina Mae nccsne Lal bot abba, french as Tt uo Machine felis Sin firal stale, but 7f uo the Sing alana at “cone fl as a Jn—suteunnisca if and andy “fp thane exis a. — Ah 9) Regu expresses Ainsb= Fat bn [mabe stn 23 f x= Cua)Co OY + fa) DUE 4 (i) = {0 | na(w) mals =0 Whee we fob} wT as (aes Oe W)_Nonddoimintte fonile autornata coy Oa Carb) 4: quan iv NFA TTHHTTTTT SQ 2 $etuce e= $0,637 F443?ote | ICLILLLE) te [rts Che bsAc| * | fay] 4d — . re =: key.) | bya as) a, ole, a, al §(9.,.d.2) = (94%) —————, —__ LS (4, Ade lt Add) {Or 0 Se _ 6 pal, Ada baer Arte Adht $y A Bil= Gor ile tA) $—<—<——————_______ Fie | 5G. =r Lae T ba Vlaye Aid: ) 4 £ly eb (4. Av)— Spy tos CG} A) Cer) — DAL £2) e. = (1) rn A Sfeoajiaer eA Dita) Gn DEI AAs) a < DT bath) Fa SL ai) fold Le Thy) btn dee) a eae ae eeie A) = (4<,0,t) L$ (a8) = (erbpb) $(q,,f)-= (44,2,8)— pia piel Ap ee 4 A |S (gpm) = |S toa) ee ae ee S las b)= | J Eth ails OE. | £ lag Ad 2{o4-8 LS Capp LIN 2 Cig Dl) {8 fq4.-0) = 5 |S (qb) = Gaby aap ph leer ea = Pee a 6 laa 10) Lae, 38) 7 aires A - a eee “——_|8(q n= C$ a ae mee)116-2017) ENATION MAYUUNE 2019 ‘Axtometa, _ (WDernten :3 How] eee 1 Flonse check wither you have got the Yumtractogs 1, AEE say te qanns tor Pre oy see SP 2 Ammer nay twe quedions fom Part 3 (20 marks each) 3. Amwer xy one question from Part-C (20 rmarks ach) ‘Mako miable sammptos if needed aad aus JAD PARTA 1 Prove @iE 123 +2344 —--__ #n(n+ 1)(n+2) = 1/4 +1) + 2)(n+3) waing 06 # ‘mathematical induction " fl © Mewne the eracty of homal hogages ss dtd by Cay. es : : ‘i DEA fbr the ‘blowing Imgnges: OTTO ieee : or L=(W In(W) = 2 and m(w)> = 3) 4 © Baylin pplication of foie extomia Regier Expression for the Inngnges:- g L={a""n 24andm <3} L={VOV|U,V © (a,b) and || =2) OY sata Lem fox Regier: ngnges. Prove tat te Inge; &s L= {O" ln ts perfect sqare}is| A nen detoumiiniti: TM 3a o: auttowiotin ctlicl tx some —- SG aaanaihy aj an ssi | pe | aR ti heorn.-) t aeize fi 1 V3 —} eC e Banc afi] A d0R alae ts 1 4 A> s! : \ t 2. Remede-OLGhk phasors [S=6) | | pb achmae | oaoas | 4 3. SB] aes A700 | A | Na phar w = = yA Cae V ee ene “ee7 __b). Mult aoek ra. \ oh Le J arbre” na Y i tak tM te Me (08 3.4, 4e. 8.5) a= 041%) P40) = (9154.8) L oC b)= (42,48) ws é _ fC q2.6\ = (42,8) Net. done - [oq 2 (gaz): : Sf C43.6) = C43,%,)= et 1, tb, ane a then b,=ba a ales se sii fob be coun he att, OT, Bae ee dosent that if 2. ft ete nagulen tan au, pageclan_& ous toe. by Ty ase Setepidin—ae use ei pcp ‘ Khexune iden inc Reserdiou $———____| dour — ie aga 9 a ae a | lteter Anat. pase tLe alan tgeilon —— = ee a8 i _ De i te a ng EU 8 aueli) ee tej oy So p—__ Guat alt a+ve=o I Ls wt iw) med Se wlmod2 ) @6 8" and ¢ =Saz a> / fo 216 — PC) & Dre ive ~ QRS (ka)® De* aK?(4 abbbb dae) _f- bbb! aaaar| bbbb aaaaz) fee “ee bbb dan %e) 4a bb 0a%0) bb "gaze 2 bb nares b ,A% (42,0, dite) fe C43, fe) Sting vabdebdPaper / Subject Cade: 72820 /Antometa Languages and Computation m ay 1 recone ih 1 = (a"b"In 2 0} cannot be constructed”. sth san true? tify? omnes NFA te DFA whe si station technique, ‘ Ps oe, ad . b ay ‘Using mathematical induction prove that: for overy wi. L*(uv)* = vue i j evs = |v }) Prove thet: “If L; and Ta are Regelar Langutge then by Me; 16 alo reguler”. 7 ) Design a DPA to accept strings of decimal numbers thet are divisible by 3. PART-B Q4 8) Constnuct & CFG for the following Lengages: ) b= {WI belmod3 > 0where we {a)"} fd b= (W inv) = ny (w) +1 and 5) sie OA ERNE Molten staal vy fe Nee ; h— efile | lof i= Usk 2O0and i= J+) ee ake a ey ee ee “e praak = 9 kee — Kea op = v ___ fren O =5 (ene a 2 abe rk ots ; “Cerys z Bete ES = =e “att Pa that POD as i. Hence P(n) is Tue on Vn S40 1 nip th Ee 3_OFk fon He NEA . D Qe sag ar jw) e= duh (ier al z Oe pone (ia) ow shite _g» Rou ne dead “Tp é(4r.0)= $ 4e.qa¢ éCans)= tga? SS g @o= i 45 V2, Teseaeee =SEM20 b) Determine regular expression for the fallowing lunguages 6 i ja" b!|n > Am < 3} ii) W [ng (WW) mod 3 = 0 and We {a,8)") ©) Convert the following NPA shown in ansition diagram to DPA, where dais te initial @ tate und go and q, are the final states. ‘ PART-B 8 Avinat is Greibioch Normal form’ Convert the following contest free grammar itt) o2 bral ave [a \bval Greibach Nocimal Form, Q = Aaie peace = BP aval albValc € + albdle c >a byale Aah lo AS State sn explain the properties of gantext fee nnguanes <_ 6 = Vote, Powe Lintesticted Grammar forthe following language L = [a'b'a']t 21) 6 Wee 4) Construct a PDA to sceept the following language = [a™b2"[n 21), Explain the 3 Yer behavior of the above PDA with the Belp of a string Vgod by, Write short note on = 6 1) Linear bounded automat ii) Unrestricted Grammar ini) ‘Context sensitive Grammar 4 and cae following languages : | ax L=('Mlli#}i=0andj = oj~~uguages and Computation e520 show that language L = (a"5%c" a a" j “saPunbs ‘c" |n > 0) isnot a Context Free Language (5 Marks) , Obtain'a Push Down Automata to LM) ={wlw €(a+b)+ andncGo) rat (6 Marks) ¢, Designa Rendesemiaiel Pushdown Automata for the language ao is = {albic® |i=) or i+ j= k ori+2) =k where i j,k > 0} Marks) PART-C ya. Discuss the Halting Problem ofa Turing Machine. (7 Marks) b, Construct a PDA equivalent to the CFG given below (7 Marks) Saba A bab B= A\bb ¢. Consider the Context Free Grammar: SaS|bAA ‘AaB | bB la Sr as ‘ B+ aBB\b aban pare) Derive the String “absabha from the given Grammar using aba 0880 4 @ . LMD @- RMD é ; (ili) " Draw the Derivation tree forthe same. 8 a. Constructa context Free Grammar for the language L = {(a"b™ |n +m is odd} b._Wite'stiort notes on “Turing Thesis: computes i(n)=logs (a), where n€ (0.1}* } & Design a Turning machine to Jar expression r= r,+ raf where ri= ab, fa ax+bb and r5= } Find the finite automata for the regu! (stb)? (cBTADNO6S034ADBFIB3COCOASZAZA N89aahb coe fing w= aabbcee Map ,nabb y or Ba,x#yB whenever x < y In other words, Baox#yB BaaiyB whenever x2 y Baox#yB # Bq,x#yB whenever x < y 7 il igning the TM for the language L = "b" in example 7.2, each eee ahold With leftmost symbol b. On similar lines we can solve ie e this problem also. . _ the start state and let the Tead-write head Points to the EN saghigheis procedure to design TM for this case is shown ‘irst digit ¢ e below: Jace the left most digit of integer x by X and then move the read/write . mead till we get the leftmost digit of integer y.DAcaa ave dh punilde. A comn hak “I 3, scuid bo arash wo if line 4 vot aga, _ —|As ee spines paiatuh Se a — deca bed aiadatet? curler ued om n | Idyhem nach (on ON rraoltGra tle, ork Re pas mend HM ay, en hanes the back beapas int bleating Fie te ean ase at obeility & eae ee ethee RX cops POP og we. on : cles 01s sreededh olen sere eatree 7.20 @ Turing machines Ee , B blo i B [8 | 9 eR reece eee Parana LR = Fe taoR | aol R “| q4B.R 7 ™ is given by UL M=(Q, 2,1,3,a0B,F) where Q= {qo 1, Gas G3} phy E =(0, 1} > oy r = {0, 1, B} . 8- is defined already Qo is the start state B blank character F = {qq} is the final state The transition diagram for this is shown below. VLR 0OR VIR Exam Obtain a Turing machine to accept the language v Aa L= {w| wis even and © = {a,b} } Gee to accept the language consisting of even number of characters is shown low. ‘ 1b ab The transition table for the DFA is shown below:7.26 f@ Turing machines Bq0100B + BBq100B + BBIq,00B + BBqI10B + Bq,B110B + (Initial 1D) Bq e 7 B + BBBBB4B + BBBBBBa, BBBqs10B + .BBBBq,01 BBqI10B + ition i defined for the state qe, the Turing machine halts, Observe shee Se Ce eco on the tape since number of 0’s in first Portion is less than that no z the number of 0’s in the second portion. . , .8: Obtain a TM to accept a string w of a’s and b’s such that N.(w) is equal to feats. the number of a's and b's in the string w should be equal. General Procedure Let qo be the start state and let the read-write head points to the first symbol of the string to be scanned which can either be a or 6. The general procedure to design a TM will result in three cases depending on the next input symbol to. be scanned namely: 1. On encountering B 2. On encountering a 3. On encountering 6 Case 1: On encountering B Change the state from qo to gy, replace B by B and move the Pointer towards right and the Turing machine halts, The transition for this is shown below: 8(qo, B) = (q5, B, R) Case 2: On encountering a +a General procedure: In state qo, if we encounter a, we skip all the subsequent symbols. - -till we encounter b. Then come back to the next leftmost symbol and repeat any of the | three cases based on the next symbol to be scanned. 5 a Detail procedure: The first a is teplaced by X and the first 5 is Feplaced by Y. For ‘example, consider the string aaababbb and consider the scenario where first two a’s ‘Teplaced by X’s and first two 5's are Teplaced by Y’s and the Tead-write head points to the next symbol to be Scanned as shown below: s i {We have seen in chaj ipter 3 ‘As the DFA processes the a 'y language which i Ae is accepted by a DFA is string from left to right in only one into TM also processes the ij - input string i each scanned input ing in only one direction(simi sid enters into ne nbd (either a or b), in re a to the example 7.5.). For and the read-write head ea ‘on same input synitols, ee DFA was in, TM remains same (the iarmanauay ve aie So. the transition table ya recognize the a ferent. a liane ntiatatig eb Gael ro Moving Hoe wa able for TM symbols is shown below: 8 a > [qo | qaR | gubR Lar | doaR | dob.R 5 The TM is given by where Q= (qo, ai} = ={a, b} Tr = {a,b, §- is defined in the form B} qo is the start state * B blank character F="fqp} is the The transition dia; M=(Q, 2,1, 8,40, BF) of table above final state gram of TM is given by R aa, |vw & Finite Autom: ata and Formal languages — A simple approach 7.19 eamele TS. Obtain aT ‘i and-’s ending with 011, uring machine to accept the language containing strings of 0's The DFA which accept Vs deine ODL ir cheee be ee comming of strings of Ok and Tseng Wh The transition table for the DFA is shown below: é 0 1 | Go -|__du qo [qi | a qe [ao [a Pn Lqs_| gs | do _J language which is accepted by a DFA is regular. As the DFA ‘processes the input string from left to right in only one direction, TM also processes the input string in only one direction(similar to the example 7.5.). For each scanned input symbol (either 0 or 1), in whichever state the DFA was in, TM also enters into the same states on same input symbols, replacing 0 by 0 and 1: by 1 towards right. So, the transition table for DFA and TM and the read-write head moves 30, Ee s remains same (the format may be different. It is evident in both the transition tables). So, the transition table for TM to recognize the language consisting of 0’s and 1’s ending with a substring 001 is shown below: "WE have seen in chapter 3 that any 1‘The sequence of moves made by the TM for the string 0000100B outputting m-n is shown below: Bqo0000100B + BBq,000100B + BB0q,00100B + BB00q,0100B ey 13B0004,100B + BB0001q,00B + BB000q3110B + BB00q,0110B by ppsRean 10B + BBq;000110B + BqsB000110B + BBq.000110B gE BBBq,00110B + BBB0gq,0110B + BBBO0q 110B + BBB001q;10B by ¢ .BBBOOI1q,0B + BBBOOI@IIB + BBBOO!11B + BBBOq0111B . BBBq,00111B + BBq,BOOlIB + BBBq00111B + BBBBQOIIB + ‘BBBBOa: 111B'+. BBBBOla11B } BBBBOIIq1B + BBBBOIIg@B | + H . A BBBB0qIBBB _—+_BBBBq,.0BBBB BBBOIqGIBB __.* ® . BBBBOIIq1B + Bl - 4 0q.0BBBB pBBq.BOBBBBr BBP on 0 is not defined, the Turing Machine halts. Observe that number of 0’s on since Bs which is” ‘4-2, The soneiy of moves made by the machine for the string e tape Ww : i wn below: % 01008 is sho’ : we >7.34 B Turing machines but a palindrome but of even length. So, it is same as the hat from states q, and qs on B no transitions are defined as Note: ww* is nothing previous problem except t shown below: B BR o | q, BLR 2 | gaa, R-[ ga. bs | gy, BLL ~ qs Bbq - x gs | qua, “| gs bk | gy, BR. [qs | gs,a, R7] gs, b, R7| qs, BL fie = A qe = 7.7 Transducers A transducer accepts some input and transform that input into the desired output. In this sense, the TM can be called as a transducer. The primary purpose of any computer is to accept some input and transform into the desired output. Using Turing machines, an abstract model of a digital computer can be obtained. The input for Turing machine will be the non-blank symbols on the tape and after processing, the output will be the symbols on the tape. So, the transducer for a Turing machine is a function f defined by f(w)'=w! where w is the input before computation and w’ is the output after computation such that < yo qow +* gaw! for qre F 1) Definition: Let M = (Q, ©, 8, qo, B, F) be a Turing machine. The function fis Turing computable (also called computable) if and only if qow +* qew! for ge F and we I” The arithmetic operations such as addition, subtraction etc. including the common mathematical functions are Turing computable. Some of the operations covered are: * Addition * Concatenation of two strings "Arithmetic comparison . .7.32 Gl Turing machines first character is b and last character js also b. Now, ow that the fir: ter as shown in stepS, At this point, we kn ad to point to the first non blank characte 0 reset the read-write h | . a sharacter is B(blank character), it means voltae de In state qe, If the ie replace B by B, change the state to q7 and m po’ ar od aA, he wnition for this can be of the form towards right. =r pat palicdttoncs * B(@s, B)=(q, B,R) "© i i B), the given string is even : » if the first symbol is blank character (B), ¢ BO eee lanes the state to > replace B by B and move the read-write head towards right. The transition for this can be of the form 5(ai, B) = (q,, B, R) Step 5: Reset the read-write head to point to the first non blank character. This can be done as shown below, If the first symbol of the string is 4, step 2 is performed and if ing is b, step 3 is performed. After completion of step 2 or 864s, 8) = (qe.a, L) % (dub) = (a,b, L) But, if the symbol B is encount fered, change the state to 41, teplace B by B and move the pointer towards tight. The . transition defined for this can be of the form Bae B)=(q,B, RY pa Tesetting the Tead-write head to the first non-blank character, Tepeat through step]. . So, the TM to accept Strings of palindromes over {a,b} is given by M=(Q, 5,7, 8,q,B,F) _a Finite Aut Oh Aiea mata and Formal languages — A simple approach 7.23 Sal change the state ty g. ,™€aNs that all 0’, in the first portion are teplac 4s 88 shown below: ™ Spey vB) ‘ 5(4o 1) = (qs, BR) ccoute tsk {oF leftmost 1. Keep updating the head towards right tll we 0 q2 and move towards est ting ene On encountering 1 change the state 5(a1, 0) =(q, 0, R) 81, 1)=(q, 1, R) Neounter 0 teplace it by 1, chan » change the state to q3 (to get leftmost 0 move the header towards left as shown below: ie 8a, 0) =(q, 1, L) If we encounter 1 teplgce it by 1 remain i i obtain leftmost 0 as ae below: en ee eee 8(@a 1) = (@, 1, R) In state q2: if we e in left Portion) and If we encounter B, it means that no more 0's are found and change the state to qy which indicates n 0’s out of m0°s are cancelled and subi traction is complete. 8(q, B) = (qs, B, L) Now, in state q4 we have to convert all 1’s to blanks. In state q3: To get leftmost 0, replace 1 by-1, replace 0 by 0, remain in q3 and move ‘ds left using the transitions: the head towar Ses tgs (qs, 1) =, 1, L) = ples 3 state to qo and move the head towards right using On engountering B, ‘change the B@s BY = (@p B.R) 's to blanks using the following transitions 8(qs, 1) = Qu BLL) In state q4: Let tis convert all 1° , (qs, 0) = a 0, L)7.36 fel Turing machines eo ee write head till a 0 is encountered. While scanning for a 0, we Seouhenteten So. replace 1 by | and move the read-write head towards right and Stay in the state qo, The transition for this can be of the form — - 3(.1) = (qo41.R) On encountering a 0, change the state to q), replace 0 by 1 and move the pointer towards right. The transition for this can be of the form 8(4o,0) = (a 15 R) Now, the read-write head points to the first 1 of integer-y. Now, move the read-write head to point to the last 1 of integer y. To achieve this, replace 1 by 1, move the read- write head towards right and stay in q, only. The transition for this can be of the form 81, = (qi 1.) On encountering B, change the state to q), replace B by B and move the pointer , towards left. The transition for this can be of the form 8(41, B) = (q, B, i) Now, the read-write head points to the last 1 of integer y. Now, change that 1 to 0, change the state to q3 and move the head towards left. The transition for this can be of the form 8(q2, 1) = (qs, 0, L) 1. Now, we have the pattern xy0 4 on the tape. But, we should move the pointer to the first 1 of the integer x. To achieve this, scan each symbol, replace 1 by 1, move the pointer towards left and remain in a State q. The transition for this can be of the form “ 2 f Pi 5(qs, 1) = (qs, 1, L) : Ley Once the symbol B is encountered, replace B by 'B, change the state to q, and move the read-write towards right. The transition for this is 5(q3, B)= (qa. B,R)7.30 fi Turing machines Similarly the sequence of moves for the string bbaaab is shown below: Gnitial 1) qobbaaab_+_Xasbanab_1 Xbareaab + XqibYaab + qeXbYaab + xybYaab + XXqYaab XXYqyeab + XXYaqyab +... and so on. Example 7.9: Obtain a Turing machine to accept a palindrome consisting of a’s and b’s of any length. Let us assume that the first symbol on the tape is blank character B and is followed by the string which in turn ends with blank character B. Now, we have to design a Turing machine which accepts the string, provided the string is a palindrome. For the string to be a palindrome, the first and the last character should be same. The second character and last but one character should be same and so on. The procedure to accept only string of palindromes is shown below. Let qo be the start state of Turing machine. Step]: Move the read-write head to point to the first character of the string. The transition for this can be of the form wabak! A 5(qo, B) = (au, B, as Step2: In state q), if the first character is a, replace it by B and change the state to q, and move the pointer towards right. The transition for this can be of the form nebet > 8(q1, 4) = (a, B, R) Now, we move the read-write head to point to the last symbol of the string and the last symbol should be a. The symbols scanned during this process are a’s, b’s and B. Replace a by a, b by b and move the pointer towards right. The transitions defined for this can be of the form Ai 3(a2, a) = (aa, a, R)X 8(qa, b) = (Ga, b, R) But, once the symbol B is encountered, change the state to. qs, replace B by B’ and move the pointer towards left. The transition defined for this can be of the form on 3a, B)= (aa, =r opeB Finit '¢ Automata and Formal lan; ses imp! proach 7.31 aunge the state to q., replace a by B and move the point tions defined for this can be of the form a 8(qs, 8) =(qs, B, L) \ Os, _ ety At this point, st x reset he Fead-wrte head a fst character sa and lst character isa a. Now, to point to the first non blank character as shown in stepS. In state qs, if th : an odd falindsone ee sae yee Character), it means that the given string is ii _ 0 replace B by B change the ‘i towards right. The transition for this can be Shh. i. a to q7 and move the pointer ya LnBo os ‘> BS MO. B)= (GBR) > 5 \ e Step 3: If the first character is the symbol b, replace it by B and change the state from 41 to qs and move the pointer towards right. The transition for this can be of the form iia, pr@encs: Heit 8(qi, b) = (qs, B, R) Se an B more Now, we move the read-write head to point to the es symbol of the string and the last symbol should be 6. The symbols scanned during this process are a’s, b’s and B. Replace a by a, b by b and move the pointer towards right. The transitions defined for this can be of the form 5(qs, 2) = (qs, @ R) 5(qs, b) = (Gs bs R) But, once the symbol B is encountered, change the state to qc, Teplace B by B and move the pointer towards left. The transition defined for this can be of the form magnrad Boe (as, B) = (ao. B, vw write head points to the last character of the string. If the last he the Tits to qe, replace b by B and move the pointer fined for this can be of the form * 8(qs, b) =(4s By Ailend aah a In state qo, character -is b, then change towards left. The transitions de!dren (at eee, 4 [Mate mae e afe rer gy i Oe be “1A emda "tn WOR saudl dy tsa a iz a - Hiroe alh wil, atliva tag De pn tbh our ‘syettions aeropsh ay. ¥ Se he eeSo, the TM to achieve x + y is given by where M=@5,T,6,qB,F) ‘os Gis Ga, qs, {iy Ny Fas 35 Ga} = {1,0, B} o is the start state Bis blank character F= (aq) 8 is shown below using the transition table 5 r 1 0 B >| 40 foot R Tau LR : Fat} au LR 2 BL Lar _[q,0.0 = : } 92} di. 1 Le = qu BR ‘de - 5 5 It is left to the reader to take an example and show the sequence of moves made by the TM. By looking at the transitional table we can easily write the transition diagram which is also left to the reader as an exercise. Example 7,12: Given a string w, design a ‘TM that generates the string ww where w < a’, AES gore uit Let qo be the start state and assume that the string w is enclosed between infinite tnumber of B’s and the read/write head points to the first a of the string w as shown below: % .....-BBBBB aaaaaaa BBBB! Ce w The general procedure to concatenate the string w with itself is shown below: eNEY 7.40 kl Turing machines Th ts of the tape and position of read/write head after applying these 1¢ contents of transitions will be a .BBBBB XXXXXXa aBBBB..... w 6: Repeating the steps through step 3, there will not be any more X’s and the left onthe leftmost 1 will be B. Once this B is encountered, change the state to qs which is the final state, replace B by B and move the pointer towards right. The transition will be 8(q1,B) = (@,B,R) The final contents of the tape and postion of read/write head is shown below: b Basan -BBBBB asaaaaaaaaaaaa BBB... Qe wi So, given the string w, the TM to obtain the string ww is given by M=(Q £, 1,6, qo, B, F) where Q= {o, 41s G2, 43 } E= {a} T = {a, X, B} % is the start state B is blank character F= {q} 5 is shown below using the transition table