Scribd
Upload
289 views48 pages

TOC Notes by Ajay Sir (1) Compressed

Uploaded by

pwasu12350
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
289 views48 pages

TOC Notes by Ajay Sir (1) Compressed

Uploaded by

pwasu12350
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 48
ay Ss ae by prf- Ajay Pashankar \ "ot theory of Compabetion ALPHABETS An alphaber is a finite , non-emphy sek of symbels We Ute the cymeo! = fo me! for an aighaber 29: “ Ssiead is te binary athaber sTRing, A Siving Lor sometimes word) is @ Finite, Stquenie of Symbelt cheater, From some alphaness a: \oa10 is a string Fem the binary alphabet F= 40%! Empty eheck usher, ‘i i | 8 YD Seecamer welherner the gentente U according +0 the niles of ) Ser of rules 4Noun ir Woman ver? > tue, | — | Lark? < Nousty eaprs | | Znouney 3 fraih N —> ser of bexminals GS —-> strb symbol Ca io «sr an NJ 3 Tohy Alphaber VenuT oder From win yon can clerive nodes. juonstesrtined odes art these M 6 is Srecial Non Teuminal ede lerewopmy aed ais \e “ dung) Buse BS arta 28? => Supp EA vHete7. E Noun > =P The woman vewrittes as =P ctirealy sertves Finite Stole, Machine ( Finile Automate > Automata, os Ph astpar ote , as | | Machine ae pes FA e-NFA DFA _ Deterministic. Finite Automata = FSM — EH is he simplegk model of computation = Th has 4 very limited memory Circle Fs known a Edges: is trecuition Vevbeling of ealgeo is inpuls- Sevce — AyB CD Ais the initial or starting dates of DEA — aseu D is the Final or terminating ster of DEA Double Circle. = (G+ 2,40,F, 8) ~~ Qc set of all sie Zs inputs qo = Stavt Shue finitval craze Fa seb of Final stares 7 6 = transition function From $e 9 KE 5 @ziAec.Dy s z= tony “Te Te] Loz 44 ~ f * sfo [A | para : a a re eu ela Deterministic Ff; Tite Automate LEveneteay Lis set of an vee a tal ( Ererote oy Strings thak start with “og F 40,00, 01,060, o10, on 72D 60, anni Cronene ren Shing reaches Fina) ¢ sing is a. Final Siete "tbe Tea redegy GORE mathing Final se F meganyee Pate Rema ° ‘ aL sG22®- fret inte | O°3OLOL® sve Sitep Aira Soke Deterministic Finite Mubmare COxample-2) Ee eee Cerne“ 2 Consmict a DFA that acepls any strings over {a,b thal cloes Ane shying aabb init. conten Zea} Try 40 design @ simpler praslem . Has cuntesFas Lek us censtnict a DEA thar atcepis all strings Over da, b} thar conialng “me shing ‘Mabb In ik: bb x b&b = Ob Q a 6 a eon ey © ee — Fite the cates ene The Fined chute TAR SIME E Ib Moe a fined Stale String id moberceceted. pase@ i a lem ——— NFA ~ Non- Deleemsinish' Froiie Automata rt Feit Atttomerte Delteminisne Finite Antonieta £ v DETERMMIEM. PIn DEA | given the contunt smte, (8 Kees the Ushobs the nan) mig sitll be, 2p Dr has only one Unique nent-sicte. % Tt has ne ehsives or nandomness PTE Ts simple and easy 46 sleotyn * Non deterministic. Fini Awomato MON- DETERMINISM Dn NEA ,SIVER the current chule there could mulhiple nen stares - PP THE next state say be chosen a random D7 AU the NEE states mony be chosen in parahet. 5 fate. EA this steiag can aloo accept emety ne re NFA~ Ferma) Definition Lt fier of all sings that end with OF (9) Es 40, F 6) | Q= St OF shareo - (bh | . = Los Ec inpots qpoz Stork sisit Jinihisl she A Foc serof fine! state “ie vés gna a a4 aoe ty A Bb. a x 2B A> ALBA BR) 2 2B srate_ ALG exo 2b7 ext 2Os AAS A, 8,6, AB, PCBS PEED pbk pase® i ; NFAY Exampic-t ~62@ Le § sep of ell shangs hob end with OF E93: 100 2 oO 4 @ A) +O-OLG io - > €2. o1 @->8 32 O-Paese * LOTTP there is eany way 0-Tun the macnine. “that ends in any seb of Stoleo out of hich Ateast one sive Is 4 Final stae then the NER crecepta 5] NFA-ckAmpLC — 2 NFA— ERAMPLES — 2. Le {ser oF all shings that simrts with 0% = 0,00, o1,000,----4 mo ©) ont 2): cof 45: ler x @+>+ Dead conti consmuct @ NFA thar aceeh ser of ol) shings over 40% of length Z ew Eriol) ° La Loo, 01,109,113 43: 00 _ a OD DOO) 4g: 00) x OOO? pase@) NFA - Examees 3 EX 1) Lis dset of all strings that ends with "Py ee! , { CO cml, amy of 15) 101, Noy Ext) L2o4 sek of afl stings tat contain tot. atte por Ex La- {sek of ah shings tha stave with “10'5 BO " ERA) Lys Goer of aut shag tok tontain [01h ere @- Ss EX 5D LSS Leer of att shings ttakends cath '1y' 4 Assignment !- TF you weve to coasmith the ejuiunlen’ DFAS for the al —Pen dell me hows Many mininum number g gine Weel yoy ase Foy athe consbudion of cach ef the DFAS - du BL 34 Ds aD Love NPs page () Conversion of NEA +2 DFA Every DEP is am nea, bub mob vice Vera, Bub there is 09 equivalink OFA RY every Z NFA, + ORS Ss , NRA $2 9x E32 nen = pea Le £ seh of all srings overto,!) thar Starts with 'o% ee h0 Ny o i ae acegsete - of ne oO) : pis 8 Brot ©) ce Conversion of NEA+e DFA cranpte -t rr UE Leet oF alt stings over do, “leubser Construction Method ) Subseh constuction Methas 1D hak ene sith "a" o 1 x pes fA2y B\e ¢ ot AB - tingle state a eal #8 | fay faBy for Calintatiy AG Jude nto ser oF Paad & ave | Miu gait) pase@s) i Finite Autemoda With owbpus, Mealy Machine. | (9, 3,4, 6,5,40) Whert @ = Finite seb of sets = Finite mn . Soe JD = The seb of output Alrhotels & = Traniition. farction @ HES Pre Cit fancies EXE DA Qos Tilia frat [stad ctate \fo ola. ole uipur 14 dercodent 0° inpur and see Eg: wlio 5028? OO-O & sa wn 3: Pergih of Stet Moore Machine (B, E,O,S,> Wo) where + Q= Finiie ser OF Stateo Sa Finite ponwempry Fo of Tarot airhoeel? pe Te kek Oty paphebe? Ge Transition fanthon; - Qxrecg | Dae cure fasorons Go = Teikal ste I stat ste OS Vourpur clependenr 2? Stet ony. 1e10 non pase Censhichten of Meay Machi na ——_— eee Ex 1) Conswuck 4 Mealy Machine that Produces +he oF Gey binery input S¥eing, afi JS Serle ent Vo lofoo otek) "2 complernent SLX wonshack ‘ov ken ‘ satya falt Machine thab prinn ‘a! uhenever the sequence iS Encountered in an7 inpur winery ching, rs: Fate} asa by Machine’ fb af 7 2 ie Be vp ol : Te 2° be & fooe a abe bbbb poe GD Conversion of Mealy Machine fo Moore, Machine Convert the fentowi Renewing Mealy Muhine $y ib equivalent Moore Mathing e=feth Srtasy Moort 2 Mealy > No ef shayes Were fame, heal» Mecre-ap No of Stmie> ineréneest + x ond FP URID np ef sinter ab Maxim wen. i Pase(S) CHAPTER %- Egret 8 Noam chemsky gave a Mathematical model ef Grammar tohith js effective for Wiring Compuiex languages. “The Four yee ef Grammar according t2 Noam Chomsky are.’ Grammar Type| — Crrammar Accept Language Accepted Automaton “Eire Unrestided Grammar Reuirsively Crumerasle. Turing Machine < Tale SOO Reytahion conktxb Sensi Linear Bounded qrammar tnsivive Language pat “TYPE Conteh Free Context Free Language —Puchdowon Akins Granmar Finite Stote ire-Z Regular Grammar Regular Language _ 2 a Automate? Graramar :- A Grammar’ Gr dan be Formally described USING 4 tuples as Gir (Ts, P) Where » . N= Set of Vaviatles or Mon-Texminal Symbols TS Serof Terminal Symbols Ss stort sympo} PS production rues for Terminals and Non—Teeminale & Production) vutes hot the Form a—zf2 where a and Bare Strings on ( NUT and atleact ane cymbol of a belongs to Ve Frome G=(415-R 030,04, 5, 4s-08, A>9,6>6}) N= {Sh Bh SF gag T= 19.8% ab $25 ee Ps SPAR Ava, arb a e a ——— ee Regular Srammar : ee Regular Grammar Can bé divide) iar two HPs. Rishk Linear Grammar Lee’ Linear Grammar eee — eye = A grammar is said 4p be Right Linear [A grammar is said to be LeFe Linear AF al) produckont ave of the Fornn if all productions ave of the Form A> xB A2Bx Ao ROK ested Se Viont ET where A, GEV and LET: ES gpabSlb sgn liner ge SbbIb — leet Hear SSE’ b > le linear” Tye St Regular Grammar Right \inew Leer linen Context frec Grammar f ranguoge ( 4 —ee iy Th Forrral Langue theo, ct conteed fre bhenguage 1s av tangas’ genetated by some Conitat free Grammar: The Set of all CFL is identical to the ser of languages accepted by Pushdow) Autonalas lonkAt Free Gfemmar |: ty fon is defined ey EPID as guiy where, SPL Vis Ser oF Variables or Non-Texminal Spmsels Es Sth of teeminel symbols S = Sect symbol Pos produdion nee Zonkext Fire Grammar has preduchoa Rule OF tray form Azae where, sivuey® and Aen aAb 3 aaAbb (7 Azar) Daaahbbb (bt AsaAb) —Paagébbb (byA3 €) —> aagbeb De jong From O Grammar The set of all strings thal con be detived fom a grammar is sats! to be she LANGUAGE genecoled from thal 4rammar . Example Ii: Consider the Grenmar Gt =(1s.A3 La-bh, 5, 1S 2aAb ahah Are) S adh [be ahh] saahbb Cby aA daadh] —Saackbhh Ley abaaahe] Saangrbh Ter A2eI > aca bbb OE 3 AB, A248, BO &3) 2 Example 22 Gj2t Cis 84 dab ysis S> AB ab Chey Ana eae? Le (G22 =Laelg — The only shing genezated ty Greer Gremrle 35 5 ($5-ABY, 14 63,5. } SABA aahla , R3B\b4) s3An8 SAB SAB sab Ceynta, Bee | + aAbB kb —>qabb —>aab abe Se a abe | Etaa= ts act, qib,asy, 3 | TaD | mzo and, Poe@® fa" | mzoandnzod eee Regular exeresions are ued far representing certain sets oF Stein (0 algebric fashion Rater for Regatar” Expreaion Y Any -texminad simbst ies Symbols @ 5. Bere, ao Ah Induding A and db are Teywlak. expressions - > fale 9 Fegutax expression 5 Fk Shion ae . Re OF aeas naa. ne are Prec’ ‘thos: iv | ME merlication oF the amour ruses aa ey 2) Ga abs | Ron ob gave eead ab org orb or bbe R= abbr te} bba | 4) ZA, 0, 00,000, - Closure of © rae* > d4acr D» ORERG= > GR -Reag D> €* 2 ang bre 2 = ©) pt pt pF D prt-ptr D> (RF. RF D Erar* oe +rtR= w* ‘> (par*p= PCaP)* 1 (p+ ars (p* @™)* oCp* 4 @*)* 12 Cp+eR=EPR+ GR and RUFF QD = RPTRE Ayvdens “Theeremy IF Pp and @ are two Regular Expressions over S ,and if P dom not Contin € then the Poowing equation in R given by R=@+RP has a unique solution fe. R= apr RoaarP —> © Re @p® =@ r@Pp*P = ge +r™P) [eretr=e*] = gP* ' R=egerr = o+fered? = G+ ar+Rr* = 2 =at @Prtarrrlr = g+apr+ar*+rr® | apr apt gpreRrt? © Cpc@r*] page) opendg Terlay Fe RE Sj gLerrt Pre +--- 77 PF penny R= oP™ Any, Example Pref using Tdenti tes oF Rewwtar Exprecsiong Pret that (10041) tC14+00%1 ) Corlo® 1) * (o4 10¥ 1) 1S eed to oF Cot low 1) : LHS = (lagor1) eC lF00% 1) Cor lot) * (orio®) =r soot) [Ee + Cor er IF Corie ld T SMe o> E+F ® = (roo (oriot iy* = (Es. 400F]) Cormrn® -pERER = (er0o%) 1 (oriot Ir = o* Corio )* ne erpeReR® Exeenplen Crort 2) Regular Erteresion: pesisn Reguar Expresi¢n For the following languases over (a,b 1) Language accepting strings oF length enactiy 2 2) Language accepting etrings of length artenck 2 3) Language accepting shings af length atmoch 2 ea” . "19 bys faa pab,ba, bbd 2 ups Lavabhs be Faas Rpcaapathba +hb ac@ebs (ath) tare nee 2 aca te) ela eb) wean Hee lath) (ath) > Durs Le a, b-a4 ob, ba by Re E+ Qtbraatal4t Latbb = (eased (eta) page@) beste SING Rejular Expreasiog - Examples cs q Find i the Regular Expression for +he Foiewing DEA Viz e+4.b +139 20 Wis 4a ml w@® V3= 4b —@ Wy = 920 + 4b +4, +hybe 2@ @ qo e+ gabe Pubting values oF Tpand da hom a@ and @ he E+4ar+ 4pb4 a= et ig Coen RaQ TRF aot ry o = Roge® Readers theorem a1 et € (ab +ba)y --ER=R | slab +ba)* L> Regular Expression .. Fied te Regwlar Expression for the Following MFA G%= 322 OO a a b&b ey es = Gas Git tab tsb Qs eperaa tie -@ @> qe<49 @ 2 (qa tqobt taee -- by 99” E yaar debate ihe — quar dye Fash putting vate of a3 hom P quarts? 42%) 6 =yatiethee atdr(b tae uw 4 Mes Ff + ep 2 We \u Segre =e QeqpR Arden Thee oe 42 A419) ( bab) * —s ©) M2 E+ 4,044, 0 Plutting value 3F a from @ VT E+ 4,0 H(q,a)Cbraby¥)b 4 +{C4,9) *) R=OtP Hz E+ 4, (A talbtar)*)b Reet a ir R ge k r ER=R 4,2 € (Catatetar)*yb)t U daraceranytey* a Final state G3) Yaz 434 4 2 bM1a0 (0 Fae) a Gyz Catalerank yt o wraryity Pulling value of 4. from © Putting value of 9 From (A Conversiba of lar Exprestion’ to Finite Astamata Bulo For aeionin Butts” For dorian (A +b) a o (A438) c fa.) a a A2—-O2-©) a _Conventen of Regular Expreasion te Finite Rubumale - Gramp ie (Fért TD Convert the Following Regular Expressions te their Sajuivatent Finite iar: 7 pa*b YD fate Bacrg* ) pots bb, bab, baab, ++ | m 2+ HO) wm Carrere ce : . “ bev e | a pO | & ‘3 acpe* a, aoe, abebe abt eke \, Abe, ANF foe Pan(i5) Conversion of Regular trpression 4p Finile Aukomnaks - Craenplet fart) Conver the Fallowing Regular Expression te 14s equivalear Fini Automata : 0 +(o+N)oO*! (oFio*y Equivalence of toe Fini Awomare Shes +0 identify equivalence For any Pair oF staies $4,254 the transition for inpuk a6 E is clefined by £40,404- where 6 §97,aFe 4a and 619j-835 44 “The hoo automata are nor equivalent [fF fora pair £40,444 one is INTERMEDIATE Steve and the other ig IMAL Shue: 2) TE initiel State is Final slede of one Automaton , then in second automalon also hfvial stare mutt be Final steve For them to be equivalent, pase @s) se = a (4.44) (uy) (42, 45) ae ae (n,45) a) (4.94) , v4 43,40) ar Be Fs CerGd 43-44) =. ¢ uy vey as fs ze Zs Wage) (45,40) (41,44) aK is A and 8 ave equivalent Cerwenion of Requint Evprinton 40 Finite Auomets —tannpien Farha) J Conwert the Fellowing Regular Expression te ifs equivalent Finite Automata: * oe Cage a Lore sand g,aa,aaat-~% (ale y* lab |e) fe, a,aa,aased, or & 5 4 o ee a re ne Destanig Regulax Expreniion -Exameles ( Park -tt) | oon [when there are Multiple Final Steves) Sind the Expression for the qyzeruce ——O gino tere It4itia! ~® ays et U0, ~R=GtRP F3= 4,0+4,9+1st -O 2 \ : lg TE -reaet | a "e Final Get Ga. 4, = (€0) a= GRoRF Vas of —@ Qatdiittet De Reunion of both the Final States = O* + OF 1 UD* =o* 40% wer = o* (e+ 1%) errr ce = o*1* Le Required Exereasion * Yp Pumping Lema is used to Prove thak a Language ip Mor REGULAR. >> Lt cannot be used fo prove thak a Langue i Regular. , “pr Te is a Regular ‘Language, then A has a Pumping tength 'P! such tha any string's' usnere | SIZ P may be divided isto = parts AZ Such tha the following conditions crust be emie Up aygiz EA for every Fz0 eo wire G) \javlsP Prove thar a language(s nok Requlae Using PUMPING LEMMA follas belts Sensi I | (he Pave wiry Contradiction > Ascume that A is " <3 Tt has tehave a Pumping Length (44 P) > Al strings longer than P ean be pumped [5] xP 3 Mow Find a ching 'S! in A such thot jst P > Divide S ins ATE > shoo thak se yiz EA Per Some i —> Then Loncider all ways thar S can be divided into ayu 3 Show stHhat none of these Can sabisFy all the 3 pumping conditions ak the dome time > S tannok be Pumped 37 CONTRADICTION - page@7) Pumping Lemm, a UsIng Pumping Serene wongeeges)- Gramere (rant =) bemma Prove that the lan, Proof GMa AR EOP E 2 0F i ne me Assume rat A ie Peta Tumping length = p saaft => S= qaqa aagabbbtbhb aU ze Poe case |: “The y part is in the ‘al park Ba aaaggbbbbbbb a =z (ase2: Te Y is inthe ‘Bt Park a pbb bbbb | anaasag ie) ay + ee cae 8; the Y Ts To the ‘a! and ‘py! Pack aasegage perbky + = - _ eo > ots x we ethic sting detent We im our language | aaaaa aaaqabhbbebb because ne of oe and WS are net etna) | ne F for Cau? i 2. eye =p a “Whig ahing chen neh lie in our language | qaaad be bbb bbbbh beens serof o's and iS are not apa | ze ‘ “pen | forcemeer 4. 4, Beenie Me of 9'f and U's aye? aye Fae met yin gaaaa bh bbbbb aabk bebee aa — PYISP | peF Cotte THe language 16 Nok Reyutet Using famring feama ‘Promging tera for Rules, Longines Enenrnis Part “FD sing Pumping Lemme Prive that the | 7 & ba is Not Regatay enguaze A- 311 etait 3 oleh profit: peer Assume Hak A is Regular Then it must have a Pumping lent = P s=0of xyle ap a y?2 :; ot a ie Sl pogooone00a100000001 000 ceaparoossces! eA 4 2 al? M19 \ayl Sk eee OE Aig Not Regular a masa Derivation Tree evivetion Thee or Pare Tree |. Tee fs an evdered rusted tree Mak graphical spepresents the semantic information of crrings clevived Fra ¥ Grammar. al on Comitosh Free. for the Grammer Gz LV, TT, P/S¥ where 6-7 OB, ASIANS &—> OAR goat vertex. Must be lolelled by the stort Syme] vertex t+ Loketled by rion Terminal Syrmbols Leowebs, Labelled by] Terminal Symbols ore Example ‘+ foe @> LeFb Bevivetion Tree” Bight Gerivalion Tree A lef Derivation Tree is obtained A Raghr Derivation Tree iz toy applying prediction te the leftmost Obfeined by prvcluchon to Variasle in each step. mE sae: vightmosh variable in eath oer Eg: For generating the sting aabaa from the Grammar 6-3 aAS|aSslé, ASsbalba Gabaa ease | Arsbsiguous Grammar A Grammar is said te be Ambiguous sree ‘ For @ sting WL thar means two or more left derivation trees) Eyomple:. ays ple: @|=( 98h faty,+, #4 P,S4 where P consith of SBS >s4+5|]s¥*¥slalb he shing B+akb can be geneented as! $3 5+5 S2sts ars sts hs —parsts arses >azyaXs — atrars arate = atate Thus, this wranmar is Ambiguous Simpl'fq cation of Content Pree Grammar etimes al the production rules and symbcis ove nek reed Becides this, there may ale be Some MULL . imination of thee productions and ed In cF4,som for the derivelion of strings - productions and UNIT raeductons- EI Spmvolt is called impli fication oF CFG fication consist ef the following steps :- in OF CFG 2) Removal OF Unit Productions 3) Removal of Null Productions. Wy Reductio Reductien of GF Seduction 2 ceq are reduced in boo Phases phasel- Derivation of 29 equivalence gremmar "Gi, From the CFG, Gr, Such thal each yowiable sdewiest elerives some terminal Shing Derivation Procedure :- Skpiz Trehide ol eymbels Wy, that derives some ermine) and initialize i erep2r Tnelude 21 {and rereat slep2,unnl Witte mols Wie thek cterives WE Slop: Tncremertt ciep Hz: Toclude of production Mules Hal have Wi in Th page If There Exists two or more clerivation — Phase 24- Derivation of an equivalent grammar "al! From the GPG, Such thay Sach Simeel GPreas in a seniential Form. Derivalion Procedures; - a edire Slept: Thetude the Stark symbol ta Va 97d inthatize To) Ssp2t Trelude alt Symbole Nyy) heb can be derived Free 4; SA4 nctucte el) produesion Mules thes have been apriied. SHP8: STreremenk T and repeat ster 2, unk Yi. = Ve Example :- Find @ reduced Grmmer equilenr to ane Srammar Gy, Raving production vies Pi sSaciIB Asa, C+18C, EsaAle Phasets Tehasce§ We LAC, EYEE devite eminnte = od of elemenk af Wy We = A ,C/6,547 5" oF W2 2 fA cE, Sy Gtetaces), Lace}, P93 Ale | Pi g9AC, ASO, C36, EP a | 1 ee est \ Mac Um eeAca at 45, 0,6,0.03 ty ys A. Gacd Bete. 3,84 p.4s3 4 Pre SSAC ABA E RE pose) Simelihiation of Context Free Grammar” Removal of Unit Productions ‘Any preduction Rule of the fom ASB wher AB ene? serminals is called Unik Production - Pricecture Far Rernowal + px re the green “He Temove A-3B, ald production A Boo x oceucs fn tee grammer: Co € Terminal 76 OP Delete A ast From. the qrommar from ster until all Unit Produchon: elt It ave removed Repeat ction nue ts 9 Exompitt= Remove Unik Preductions Frees the, crevamar whore prod hy pr S31, R24, yY>zle, z2M Mon, naa yoz, BPM, Mom D gine Na -we add Moa P cont, Boa A oreib rea wae HOPS moa jue add 294 aaa, wo 2 Sine ee gb MR TE gine Z-7e .we add Ta 3? aoe ,toalb, PL SOy gaa, Mot APF up from Stat Symvol Swe an mot reach. le ee sR oe prove the Unteachable symbols pr gst, HA yi alb youn Res Simplifiation oF Contes Free Grammar —ae"c""_"rcooeoOeuoeoer aoa Removed of Mull Productions SS eens Tn a CFq, i a pratt Co es Samper 'A' is a nullable variable Tf there ix = " 3 & Or there f% a derivation thal start at 'A' and leads €- (tie AS se) Productionfer Reriovel:_ —— re Steplt-Te remove A ©, took for all Productont Whoe ryht ide contatns A Ser2:- Replace each occurences of 'A" in each of these productions with € Sie Bi- Add the vesubiant productiens 4e the Grammar Extompig = Remeve Null Productions from the fettacing Grammar SB ABAC, AoAle, B2LBIE,C>e Are , BE I> To eliminate A & > ABAC | Spasec => aAasc}each Be => AzoA Axa New prduction: 6-5 agac ABC RAC BC B3ok \ha .B-> BBE Ce a) To eliminde Be S>Aac | Aclae ,BSb New Prduction: 6—> ABACT ABC | BAC IBC | AAC jacie Ao oAle Bo LBIb boc Normad Forms DeMorsky Morne) orn @Greibach Normal Fe ; © homely Normal orm =n Chomekey Normal Form (CMF) we have a reabichon on length of RHE: which $2 elements fa RHS suuld Se ptouiees Variable ora Terminal. A CEG is in chomsty Ho Form Forms : : Asa if the productions are in the Frttovsing A BC Where A,B and © are non-decminals and a ie adeeminal, SPS tp convert a given CFG to Ghemuky Normal Form: | sep ILE the Start Syrnbel S occurs on some right side jcreale a meus start \ Sumbol sc! and & nen, Production s'> 5° \ mn ' | Remove Null Productfens- (Ucing the Null Production Removed discussed a in previous tectured. step 3:- Remove Unt+ fieduetionn( ——4i— ) | siep 42- Replace each Production A> Ba Bn Where n>2, with APB SC Whe C5 Bye Bn Pepenk This step for all (ecluckon having Mo or more Symbele on othe right aide jn dhe form AaB where ‘a! 2 Th the Tight side of any Production ee f ; derminals then the Production 16 a -herminal and A and B eve nee Ts replaced by ASXB and x24 Repeat this Step for every Produchion Hhteh is of the Form A2aB- convert the Allecing CFG HeeNE + Ps 6 > Ash lab, ADBIS, BP ab le 1) Since S appears: iq RHS we add hew : jt ‘ 7 stale 8 and 6 f “ge EndGelee and S-3S is added to P: S135, SHASAlOB -ASBIS, Bablée (uc e-beam ®D Remove the Null Productions: Be and ADE: Afler remeving @-s€ + il Afler removing Awe + aa Pis'as , 5 AsA)oBlalAsisAls_ A=>BIS Bob B Remove “the Unit Produdions= Gas, Ss APB, ADS? | After reinoving Sas: Pgs 6 sasalaBialas ISA ,A2815 Bb After Removing S'>S 2 pz sy ash [aBlalAsisa , } 82 asnl aflal ASISA, A2B1S ,B>b || ppter pemeving A®BtP: s'-3 ASAla@lalASISA, 6 ASA JaBlalas \sh, AsbIS, Bob fe ectctatre tot alin deep ed oa ee ARR. Removing AS? S'SASATABIAIASISA, 6 > ASA [abla lAsl sh, Az b\erash jan lalAsisa, oS yaw find owt the produttions hak has Mevethan TWO Variables in RHS eb5 ASA, S2ASA and A@ASA Afler removing: these pwe ger Pisi—> AX/aBIATASISA, S— Anlablalasisa, A = wlAx lag lalAsisa, Bob, Kash * 5) Now change the prductiont Sak, S2a8 and A—saB Finedly we gar > ont P2 6 Ax19Bla JAS) SA, (.... yaa) S— Ax lyBIalASISA , Aa BIAXIYB IAL ASISA, Boe, ex SA, ) ska Which is the required chormsky Normal Form for the given CFG - Theag. WE Ge “Theory of st-1r Computation Handriritten Notes : Prepared by, pf. Ajay Pashanknr : peep: profe jay Poul Greibgch Normal Form A CFG is in Grelbach Nowmad farm if the Prductons are in the Following Forme! Awe ’ Bp bere eon Whee Wey. Cn OFF MonsTerminals aad © 1¢ a Terminal: Steps 40 convert a Given ¢fq +o z: Skepl: check TF the given CEG has any Unit Priduckons OF Nal) Produvions and Remove if -Hhere are any (wing Yhe Unit Sri) Predation’ removal Fechaiquer ‘discussed in tee previous leckure). Nore Form (CMF) and slept: Check Whether the CFG Ts already jo Chorniky fom Fechnigus convert Th 40 EMF if it ts Mot Cusing the CFG to CAE Convers Thccdated in the previons lecture) sitp Br change the Mame of the Mon-Terminal Symbe ic into Some AZ in ascending order of t Eseamy — swamp $- — § 5 CA) BE Replace G with Ay bok | S68 C with Ko cob K awe AO8 B with hy f we. gett \ ie Aya Aaka [Ay Aa Ay oe bl AY Ava ge Oe Mon-Terminaly are i asten Order, Such thak Slepus Allee the rules so hak the Th athe Production & of Ane form Ai-7 AZ, then, 4423. and should never be igi Ay a bv Ay Ay = Ba Ay [Ra AS Ma Vag Pry AY, L Lert Recursion Ay bv Ne Ay? BIE ASAS _ - vase) Remove. Lef+ Reeure fore CGreibach Newmal Form) peta ths) Normal ferns Conversion oF GEG to cut. Removal of LeFk Recursion) ORI SE AEG to CHF - Removal of Left Recursi Ay Ao Aa hy Ay Rye \Ay Ay — > Ay bIbAZAY | AAA R a Te Aasa LeFh Recursion SRP Ss Remove Lett Recunton Entredute a New variable +o remove “the Left Recursion Ay => ©1b Asay Lag Ay hy Ay > Ay dg Z LA ay ~ nn { neat production one with Zand one citer 2) > ob IbARAY |b 21 bASAYZ - C4 te in Gey Ay Now He grammar is = Ay Rafa TAy Ay Ay blb Aghy|bZ/bAZAYZ R25 Au kyl AyAyz Ab Age Ae Ae Pb Pb AeA | BT Aa Alb AS 1 BAY TE ASAn AY IBZ Ay b Ag AGZ Ag = sas (Replacing Aad by Aya b)b Ag Ag | 6%) BAZ Ay Zz Mane w2 27 b Ay l AgAy Ay Loz Ay [banayz ral + Ceeptacing Ayah) BAY | EAs Ay AyZ [be AuZ | bag Ayana Agob ga Pumping Lemma (for Context Free —— Pumping Lemma is mor Gonket Free (for CEL) ig used to prove thak 4 langmage Contest Fire Lanquage \ i exaled TEP formal language theory,a context Free Lagguage ie a longa Jo by some content Free Grammar: “The ser of all cFL is identicn pashan Automat: do the cot of languagen acrerted by Context Free evammay ie identfied by 4 tuples as Gz fv, 5,5, Ph ohert NJ = set cf Varianie or Hon-Termingl Syfmbels t Ss Ser of Terminal Symisets - S = Stark Symbel | P = Production Rute | mena FRE Grarama? has roluckion Rate of the Form Apa | whert , ac§VUZI™ ond Aev Po 16 & ig a Conbeak Pree Language then Wa Pumping Length 'P' Such that any stings! where [sl ZP meow te divided inte 5 Pres Sauyrty Suth Hak ite Following conditfono ruck be tan. Du viatylz WD |vyl zo a) vals P isin A for every TR 0 To Prove thot @ Lan: IS NOk conleser Free Using Pumping Lemmal for CEL Follow? the steps eeieid, (we prove udng ConTRADICTION) PJ Assume thar Ais content Free —2 Tr has te nave a Pumping Length (say-P) —> All strings lonyer than P can be pumped }sl> PF —> wow Find a sting 's' in A such that |S] =P —> Divide S into uvayz —> chee that Uviccy'z BA forsome i —> Then Gnsider the ways that SCan be divided into uuaye > shew that hene of these can satisfy od) the | pumring conditions oF the Same +Hme. — > S Campet be Pumped o= CONTRADICTION Pusrdown Avdonats ( Formal definition) . A pushdown Automat is Formally defined by % Talon a Shou beled: P= (Q@, 3,0, & 4,20, F) Where » Qe A Finite Get of states Za A Finite cob oF Typat Symbols Pos A finite Strack, Alphabet & < The Transition Funthon Yo > “the Stavk chute Zor The Stard Shul Symbol Foo The sek oF Final /AtcerHiny States “Taving Machine ~Tevtrodtuttian € Pork= 4) Recarsively Baumert le Languages Contnt Free Languages Regular Languages { FM t the Thpur swing ele ]s Tale |a[o]s] PDA: > the: Thpul Sting A Sink, “TURING MACHINE: A Tape _ Tape Alphabets: EF = Lo,!,ab,xZoy 3 the Blank Li is @ Speciot Syus) ute The blank 7s a cpecias cymbot wed the Fill the infinite tape. “Dhitiel configuration: the Input string Blanks eu 4e infinity opemitens on tHe Tare? Srermriens on He re: > Kead | Scan Symbe! below the > Updase f ririte a Symbol bela the TareHend > Move the “Tape Head one Step LEFT —> Move the Tape Head one skp RIGHT “Tape Head: “Tisring Machine -Iintredution (Par 2) a ee eer erireskaelian Caro “The Conte! Portion uf fopuy-. “he Tanah ering Blank ou fe infinitey The Control Portion similar. +0 FSM or PDA The PROGRAM Ek is deterministic Rutes of Operation - L Sears At each Step of he computation : o> Resd “the curate Srna} =P Opals Che. Wetted the game ces) > Move exactly one cell either LEFToR RIGHT. ing to move LEFT , then clo “IF we are ab the left end of the tere, aad ani not move - . Shy at He left end. Birection to Move LEFT of RIGHT LF you dosh wonk te tptate the call, ss dent - usr WRITE THE SAME SYMBOL Page opera > Conte! is witha sot of FSM > Taitiet State > Final stoves 2 (there are +euo Hae) steve) \) The Accepr cme ‘DThe REJECT stmE —> Computation can afer D HALT and AccepT 2 HALT and REevEcT 3) LOCP C-the machine fails to HAUT) A Turing Maching can be defined as a cer of Z tuples (GrE,7 6, 4%0,b,F) B—> Non empty set of states FS Non emphy cer oF Symbols [> Men empty sep of Tape synhols CTH) & 5 “TrentiFion funuton defined as Qx=E PT XCRID AG Yo —> ritial ste b > Bleak Syrbel eS sep of Final choles ( Accept stat & Reject Stake? thus. the producton me of Turing Machine will be varitien 45 6 (40,22 C4 ®) 's Thesis Tiiring’s “Thesis stares hak any computation that Can be carried enh by Mechanical means can be performed ley some Turing Machine Jepting iis “thesis Ont! Lo engements hr ace ; Fen eae cone on enicting ayinl Cammaie can ates Se done ¥y wy) Aartains ther cn Juring Machine one has 12h Igerithen, For whith @ Turing Machine Program cannok be t Leer, able to sagsek a problem solvable by Whak we Ne consider ano poriten: pe Recurstvety Enumemble Language A Language Land = is sag tobe Rewinively Fumeroble if there enists a “Turing Machine that acceph i++ “Turing Machine - Example (Pact 2) Design 9 Turing Machine Which recognizes the language L= o1*o | &=49,"5 bo “faving Machine -Examete (Fart “2 Turing Meine ; Nan Design a Turing Machine eohich recognizes the lequase Ls O° Algorithey © chonge “No” to "x" a = Move BIGHT +a Fink > If None : QETECT + change "4"! go My" » Move LEFT 40 LeFimost “o” + Repeat the abort steps until ne move "0" # Make Sun ne mere “b's remain ne

You might also like